一、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更多用于数据库的数据存储（读多写少场景）。