数据结构：BST和AVL

本系列文章内容源自网络资源，并结合了本人的一些个人理解与观点。若你在阅读过程中产生熟悉之感，这属于正常现象。该系列文章主要目的在于便于本人今后的学习与回顾，同时我会在文章的开头或结尾处注明所参考的原始博客链接。

二叉查找树（BST）

二叉查找树，亦称作二叉搜索树（Binary Search Tree），是一种特定结构的二叉树。假设x为该树中的任意一个节点，该节点包含一个关键字key，记作key[x]。若y是x的左子树中的任意节点，则满足key[y] <= key[x]；若y是x的右子树中的任意节点，则满足key[y] >= key[x]。

具备以下特征：

1. 当左子树非空时，左子树中所有节点的关键字值均小于其根节点的关键字值；

2. 当右子树非空时，右子树中所有节点的关键字值均大于或等于其根节点的关键字值；

3. 左、右子树本身同样构成二叉排序树；

4. 树中不存在具有相同关键字值的节点。

【二叉查找树的特性：对二叉查找树实施中序遍历操作后，能够获得一个按照升序排列的序列。

二叉查找树的时间复杂度：其表现与二分查找类似，插入和查找操作的时间复杂度通