- 二叉搜索树查找最坏情况是根树的高度有关,当一个二叉树只有左子树或右子树的时候,它就退化成了链表,其搜索的时间复杂度最坏情况变成了
- 当我们从小到大(或者从大到小)往二叉搜索树中添加数据时,其就会退化成链表
- 当我们删除节点时也有可能会导致二叉搜索树退化成链表
- 那么有没有办法防止二叉搜索树退化成链表呢?, 让其添加、删除、搜索的复杂度维持在
, 答案是有的,就是下面要说的平衡二叉搜索树
平衡二叉搜索树
- 何为平衡: 当节点数量固定时,左右子树的高度越接近,这颗二叉树就越平衡(高度约低)
- 最理想的平衡,就是完全二叉树、满二叉树那样,高度是最低的
如果改进二叉搜索树
- 首先,节点的添加、删除顺序是无法限制的,可以认为是随机的
- 所以改进方案是,在节点的添加、删除操作之后,想办法让二叉搜索树恢复平衡(减小树的高度)
- 如果一直调整节点的位置,完全可以达到理想平衡,但付出的代价可能会比较大。比如调整的次数会比较多,反而增加了事件复杂度
- 总结来说,比较合理的改进方案是,用尽量少的调整次数达到适度平衡既可
- 一颗达到适度平衡的二叉搜索树,可以称之为:平衡二叉树
- 平衡二叉搜索树简称: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 管理
网友评论