红黑树

B树

定义

性质

• 只有在根节点超载时B树才会增加深度
• B树一定是茂盛、平衡的

AVL树

用旋转维持平衡

<aside> 💡

可以使用旋转操作，在O(N)的时间复杂度下平衡任意一颗二叉搜索树

</aside>

AVL树的性质

平衡因子

• 一个节点的平衡因子 = 右子树高度 - 左子树高度

AVL树的插入与删除操作

动态演示：https://www.cs.usfca.edu/~galles/visualization/AVLtree.html