2-3树特点，插入和查找操作图解

2-3树

2-3树是最简单的B树，其中2和3主要体现在每个非叶子节点有B树有2或3个子节点，是平衡树。平衡树应该解决不平衡树查询效率的问题。常见的二叉平衡树是AVL树。虽然提高了查询效率，但是插入操作效率并不高，因为每个节点插入后都要保持树的平衡。为了解决查询效率问题同时考虑插入效率，提出了2-3树。

2-3树的特点

• 2-3树是平衡树，但不是二叉平衡树。
• 对于2-3树和相同高度的二叉树，2-3树的节点数大于满二叉树的数量，因为有些节点可能有3个子节点。
• 2-3 树可以是空树。
• 对于2个节点，节点存储一个key和对应的value。另外，它还存储了指向左右两侧的子节点。子节点也是2-3节点。 左子节点的所有值都小于该键。真实子节点的所有值都大于键。
• 对于3个节点，节点存储两个键和对应的值。此外，还存储了指向左、中、右三个方向的子节点。子节点也是2-3节点，左子节点的所有值都小于两个键中较小的一个，中间节点的所有值都在两个键值之间，右子节点大于比两个键中较大的一个。
• 对2-3树进行顺序遍历，可以得到有序序列。

插入操作

一开始是一棵空树。插入节点“A”以创建根节点。

插入节点“B”，从根节点开始查找保存的节点位置。与“A”节点合并后将其放在同一叶子上。此时叶子只包含“AB”两个元素，不需要分裂，

继续插入节点“C”，从根节点开始寻找保存的节点位置，找到“AB”叶子节点。粘贴一下，

但是此时叶子节点包含了三个元素“ABC”，需要进行节点分裂。具体划分过程如下。找到节点三个元素中中间最大的元素，

向上移动成为最小节点和最大节点的父节点，而最小节点充当中间节点的左子节点，最大节点充当作为中期的右子节点。

从根节点开始继续插入“D”节点。

比“B”大，所以向右走，

找到“C”节点并将其合并到叶子节点，叶子节点只有两个元素，不需要分裂。

继续插入“E”，找到“CD”叶子节点。放置“E”节点后，发现叶子节点有3个元素，需要进行分裂。

将中间元素突出显示到父节点，并拆分剩余两个元素。在两个子节点中，“D”上升到父节点并向右存储，而父节点只有两个元素，因此不需要继续分裂。

继续插入“F”节点，

往下看，看到连续两次分裂的情况，继续插入“G”节点，比“B”大，继续比较，

大于“D”，走右子节点，

走到右子节点后，与“F”比较，发现大于“F”，放在右边。

原来“EFG”叶子节点有3个元素，需要进行分裂。

将中间元素“F”提升为父节点，“E”和“G”左右元素分别称为左子节点和右子节点。

晋升为父节点后，发现父节点中包含了“BDF”的三个元素也需要拆分，于是准备拆分中间的元素“F”晋升了，

发现“BDF”节点原本属于根节点，所以分裂后就没有根节点了，所以必须创建一个新节点作为根节点，即提升后的“D”节点作为新的根节点。 “B”和“F”的左元素和右元素分别作为左子节点和右子节点。

总结一下：当一个节点插入2-3树时，首先要找到该节点应该落在哪个叶子节点上。注意，它必须位于叶子节点。将新节点作为新元素添加到叶节点。此时，如果节点只有两个元素，则插入操作完成。但是，如果节点有三个元素，则必须执行拆分操作。左、中、右元素按大小排序，中间元素提升为父节点，左、右元素作为左、右子节点。那么它可能不完整，因为父节点Den可能还包含三个元素。如果是这种情况，就必须进行一次分割操作，直到父节点递归地只包含一两个元素为止。

搜索

2-3树搜索与二叉树搜索类似。它从根节点开始进行比较。如果相同，则查找成功。否则，搜索继续向下。对于只有两个子节点的节点，它位于其左右子树中。在中间递归搜索，对于具有三个子节点的节点，在左、中、右子树中递归搜索。

如下2-3树，查找“C”节点，

从根节点开始，与“D”比较，如果“C”小于“D”，则向左，

继续与“B”比较，“C”大于“B”，则向右走，

“C”等于“C”，找到。

如果要找“H”节点，就从根节点开始。如果“H”大于“D”，则向右走。

逐个比较“FH”节点中的元素，先与“F”元素比较，“H”大于“F”，继续比较下一个元素，

“H”等于“H” ”，查找，在“FH”节点中查找“H”。

要找到“G”节点，请从根节点开始。如果“G”大于“D”，则向右走。

将“G”和“FH”音符一一比较。如果大于“F”，则继续与下一个比较。对于主体来说，

“G”小于“H”，即“G”在“F”和“H”之间，那么走到中间，

“G”等于“G” “”，发现了。