搜索树：AVL Tree, 红黑树, B-Tree

• 二叉搜索树 - 数据有序
  • 平衡二叉树 - 高度差 = 0
  • AVL Tree - 高度差 <= 1
  • 红黑树 - 高度差 < 最小高度 x 2
• m 叉搜索树 - 多个分叉
  • B-树 - 内部节点至少 m/2 个子节点
  • B+ 树 - 叶子节点连成链表

不平衡的二叉树

不平衡的二叉树深度增加，搜索效率降低。

通过树的旋转可以调整左右平衡。

Tree Rotation

------------------------------------------------------
 Rotate Right              |  Rotate Left
     R            P        |     R               P
    / \          / \       |    / \             / \
   P   C   =>   A   R      |   A   P    =>     R   C
  / \              / \     |      / \         / \
 A   B            B   C    |     B   C       A   B
------------------------------------------------------

旋转像跷跷板一样，一边的高度升起的同时，另一边的高度下降。

AVL Tree

--------------------------------------------
    Case-A     =>    Result

        P              R
       / \            / \
      L   R          P   B
         / \        / \   \
        A   B      L   A   X
             \
              X
--------------------------------------------
    Case-B     =>    Failure

        P              R
       / \            / \
      L   R          P   B
         / \        / \
        A   B      L   A
       /              /
      X              X
--------------------------------------------
    Case-B     =>  Case-A        =>  Result

        P              P                A
       / \            / \              / \
      L   R          L   A            P   R
         / \            / \          / \   \
        A   B          X   R        L   X   B
       /                    \
      X                      B
--------------------------------------------