一、AVL
性质：
-
平衡因子为-1、0、1（左子树高度减去右子树高度，反过来也可以）
-
通过旋转操作来进行平衡：
1、如果是右右型的子树，则左旋
image.png
2、如果是左左型的子树，则右旋
image.png
3、如果是左右型的子树，则先左旋后右旋
image.png
image.png
4、如果是右左型的子树，则先右旋后左旋
image.png
image.png
- 附加：子树携带子树的情形（竖着看）
image.png
二、红黑树（一种近似平衡的二叉搜索树）
性质：
- 左右子树高度差小于两倍（如：左子树高度为2，右子树要小于等于4）
- 要么红要么黑
- 根节点是黑
- 叶子节点是黑（nil、空节点）
- 相邻两个节点不能都为红
- 每个节点到叶子节点经过到黑色节点数一定相同
示例：
1、
image.png
2、
image.png
三、两者对比
image.png
- AVL树提供更快的查询速率
- 因为有更宽松的平衡策略，红黑树提供更快的插入、删除操作速率
- AVL树因为要存储平衡因子从而导致内存占用较高（平衡因子需一个int类型存储），而红黑树只需要一个bit（0或1）来表示红或白即可。
- 红黑树更多地应用于高级语言中插入、删除操作较多的map、set等结构，而AVL更多用于数据库的数据存储（读多写少场景）。
网友评论