查找（一）史上最简单清晰的红黑树解说 (5)

★一颗红黑树的构造全过程

平衡二叉树（AVL树）

定义：平衡二叉树(Balance Binary Tree)又称AVL树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树。且左子树和右子树的深度之差的绝对值不超过1。

若将二叉树上结点的平衡因子BF(BalanceFactor)定义为该结点的左子树深度减去它的右子树深度。则平衡因子的绝对值大于1。

其旋转操作 用2-3树的分裂来类比想象。

下半部分——散列表、B树、B+树、Trie树。