平衡二叉搜索树

• 二叉搜索树查找最坏情况是根树的高度有关,当一个二叉树只有左子树或右子树的时候,它就退化成了链表,其搜索的时间复杂度最坏情况变成了
• 当我们从小到大(或者从大到小)往二叉搜索树中添加数据时,其就会退化成链表
• 当我们删除节点时也有可能会导致二叉搜索树退化成链表
• 那么有没有办法防止二叉搜索树退化成链表呢?, 让其添加、删除、搜索的复杂度维持在, 答案是有的,就是下面要说的平衡二叉搜索树

平衡二叉搜索树

• 何为平衡: 当节点数量固定时,左右子树的高度越接近,这颗二叉树就越平衡(高度约低)
• 最理想的平衡,就是完全二叉树、满二叉树那样,高度是最低的

如果改进二叉搜索树

• 首先,节点的添加、删除顺序是无法限制的,可以认为是随机的
• 所以改进方案是,在节点的添加、删除操作之后,想办法让二叉搜索树恢复平衡(减小树的高度)
• 如果一直调整节点的位置,完全可以达到理想平衡,但付出的代价可能会比较大。比如调整的次数会比较多,反而增加了事件复杂度
• 总结来说,比较合理的改进方案是,用尽量少的调整次数达到适度平衡既可
• 一颗达到适度平衡的二叉搜索树,可以称之为:平衡二叉树
• 平衡二叉搜索树简称:BBST (Balanced Binary Search Tree)
• 经典常见的平衡二叉搜索树有 AVL 树和 红黑树, 一般也称他们为自平衡的二叉搜索树(
  Self-balancing Binary Search Tree)

AVL 树

• AVL 树取自于两位发明者的名字 G.M. Adelson-Velsky 和 E.M.Landis
• AVL 树是最早发明的自平衡二叉搜索树之一,广泛应用于 Windows NT 内核中

平衡因子

• 某节点的左右子树的高度差

AVL 树特点

• 每个节点的平衡因子只可能是 1、0、-1(绝对值≤1,如果超过 1,称为失衡)
• 每个节点的左右子树高度差不超过 1
• 搜索、添加、删除的时间复杂度是

AVL 树导致失衡的两种情况

添加导致的失衡

• 最坏情况:可能会导致所有祖先节点都失衡
• 父节点、非祖先节点都不可能失衡,父节点不论之前有没有子节点,添加后其平衡因子绝对值都是≤1 的, 非祖先节点的子节点高度都没有变化,所以不可能会影响到非祖先节点
• 只要让高度最低的失衡节点恢复平衡,整棵树就恢复平衡(仅需 次调整)

删除导致的失衡

• 可能会导致父节点或祖先节点失衡(只有一个节点失衡),其他节点都不可能失衡。这种情况是删除的节点在较短的子树上,删除该节点后,其父节点高度没变
• 可能导致祖先节点失衡,需要再次恢复平衡,然后恢复后又可能导致更高层的祖先节点失衡,极端情况下,所有祖先节点都需要进行恢复平衡的操作,共次调整

恢复平衡的四种情况

LL 情况

RR 情况

LR 情况

RL 情况

红黑树(Red Black Tree)

• 主要应用于:
  1.C++ STL(比如 map、set)
  2.Java 的 TreeMap、TreeSet、HashMap、HashSet
  3.Linux 的进程调度
  4.Ngix 的 timer 管理