2-3 查找树的个人理解以及Java实现

由于二叉查找树在理想状态下的高效的性能以及无法保证性能下限的缺点，如何去优化它就十分有意义。优化的思路很自然的想到：只要在插入过程中尽量使树保持平衡，就能保证它的性能下限。如何实现这一点，幸运的我们已经由前人想到了非常聪明的解决办法：2-3 查找树。

什么是 2-3 查找树

一颗2-3 查找树或为空树，或为以下节点组成：

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

一颗完美平衡的2-3查找树的所有空连接到根节点的距离都是相等的

插入

• 和二叉查找树类似的地方在于，插入前需要按照2-3树的性质（左子树都比根节点小，右子树都比根节点大，中间的子树介于根节点的连个节点之间）找到键值对的插入位置

• 如果插入位置是一个 2- 节点，那么新插入的键值对就和这个节点构成一个新的 3- 节点

• 如果插入位置是一个 3- 节点，那么可以这么做：

  • 和 3- 节点构成一个临时的 4- 节点
  • 将 4- 节点中 居中的节点作为这颗树新的根节点
  • 将 4- 节点中 居左的节点作为新的根节点的左子树
  • 将 4- 节点中 居右的节点作为新的根节点的右子树
  • 将这颗新树递归的插入到原有2-3树中

以 123456789 1 2 3 4 5 6 7 8 9 123456789 插入到空的 2-3 树为例子：

关于实现

​ 尽管可以使用不同的数据类型标识 2- 节点和 3- 节点并写出变换所需的代码，但是使用这种直白的标识方法实现大多数的操作并不方便，因为需要处理的情况实在太多。实现这些不仅需要大量的代码，而且他们所产生的额外开销可能回事算法比标注你的二叉查找树更慢。

且他们所产生的额外开销可能回事算法比标注你的二叉查找树更慢。

​ 更为简单的实现： 红黑二叉查找树