2-3查找树

《算法》第4版 3.3 2-3 查找树

3.3.1 2-3 查找树

定义：一棵 2-3 查找树或为一棵空树，或由以下节点组成：

• 2- 节点，含有一个键（及其对应的值）和两条链接，左链接指向的 2-3 树都小于该节点，右链接指向的 2-3 树中的键都大于该节点。

• 3- 节点，含有两个键（及其对应的值）和三条链接，左链指向的 2-3 树中的键都小于该节点，中链接指向的 2-3 树中的键的都位于该节点的两个键之间，右链接指向的 2-3 树中的键都大于该节点。
  和以前一样，我们将指向一棵空树的链接成为空链接。

用于维护平衡的重要性质：一棵完美平衡的 2-3 查找树中的所有空链接到根节点的距离都应该是相同的。