背景
我们认为线性数据结构包括：Vector（理解为数组）、List（理解为链表）、栈、队列，半线性结构包括：树、二叉树。
线性结构无法兼顾查找、插入操作，它们要么查找很慢、要么插入很慢，所以我们引入搜索树这种半线性结构，希望能兼顾查找和搜索操作。
| 数据结构 | 查找最差 | 插入最差 | 备注 |
|---|---|---|---|
| 无序数组 | O(N) | O(N) 或 O(1) | 注1 |
| 有序数组 | O(logN) | O(N) | |
| 链表 | O(N) | O(1) | |
| 二叉搜索树 | O(N) | O(N) | |
| 平衡二叉搜索树 | O(logN) | O(logN) |
注1：若采用翻倍扩容策略，则插入的分摊时间复杂度为O(1)，对本文来说可不必理解那么深入。
虽然二叉搜索树（BST）的查找、插入操作最坏时间复杂度为O(N)，不甚理想。但在BST的思想基础上稍加改进，就可以得到平衡二叉搜索树（BBST），BBST的查找、插入都是O(logN)。BBST有很多种：AVL、红黑树等，本文介绍其中最简单的AVL。
BST的定义和性质
BST的顺序性：
- 左子树的所有节点 <= 当前节点
- 右子树的所有节点 >= 当前节点
由BST的顺序性可以引申/推导出几个结论：
- BST的中序遍历序列必然单调，见图（copy自邓俊辉数据结构）
BST的中序遍历序列
BST的实现
BST的查找、插入操作是容易的，本文略去不介绍。
而对于BST的节点删除操作，并不是很简单，需要分几种情况。
- 待删节点为叶子
- 待删节点只有左孩子或右孩子
- 待删节点既有左孩子又有右孩子，通过将待删节点及其「直接后继」进行交换，从而转为情况2，直接后继是指中序遍历的下一个节点，如图（copy自邓俊辉数据结构）。
情况3转为情况2的处理方法
情况1、2虽然简单，但代码实现有点小麻烦。这里你会发现C、C++的指针、引用是那么好用啊！反倒是Python、Java实现起来很难受。不信我们以情况1为例考察下面不同语言的代码。
# Python语言
def remove(x):
if x.left is None and x.right is None: # 情况1
# 这里麻烦，不但要依赖parent，还要判断自己是左孩子or右孩子
if x == x.parent.left:
x.parent.left = None
else:
x.parent.right = None
// C++语言，让调用者传入指针的引用
void remove(TreeNode *&x) {
if (x->left == NULL && x->right == NULL) { // 情况1
x = NULL; // 这里就特别方便了
}
}
若不断插入已经升序/降序的元素，BST会达到最差情况，此时BST是极不平衡的。如图（copy自邓俊辉数据结构）。
image.png
平衡二叉搜索树：AVL
为了克服BST的最差情况，我们引入AVL。
todo：剩下内容后续补充，不过我有拖延症。
