16.AVLTree.md

二叉查找树

相关概念：二叉查找树的中序遍历是有序的序列

性质：

1. 左子树 < 根节点
2. 右子树 > 根节点

用途：解决排名相关的检索需求

插入

递归比较节点值的大小

删除

1. 删除度为0的节点（叶子结点）：直接删除
2. 删除度为1的节点：直接提升其子树（因为度为1所以只有唯一子树）
3. 删除度为2的节点：找到前驱和后继替换之后转换为度为1的问题

前驱就是左子树中最右边的节点，就是左子树中最大的，也就是中序遍历在当前节点的前面的

E：删除20节点

找到20的前驱19，将20替换成19之后。再删除原来的19就行了。

因为他的前驱不可能是度为2的节点 WHY？

最优/平均 $O(nlogn)$

最差 $O(n)$ (退化成链表)

线索化二叉树

为什么

1. 递归遍历二叉树系统开销大
2. 二叉树有n + 1条边都没存储信息，可以用起来
3. 对于退化成链表的二叉树遍历速度快

怎么加-中序遍历

1. 左右孩子为空，左指前驱，右指后继
2. 不为空的，前驱为左子树最右边，后继为右子树最左边