2-3树特点、插入与查找操作图解

2018-09-1322:17:55数据结构与算法Comments3,514 views1字数 1727阅读模式

2-3树

2-3树，是最简单的B-树，其中2、3主要体现在每个非叶子节点都有2个或3个子节点，B-树即是平衡树，平衡树是为了解决不平衡树查询效率问题，常见的二叉平衡书有AVL树，它虽然提高了查询效率，但是插入操作效率不高，因为它需要再每次插入节点后维护树的平衡，而为了解决查询效率同时有兼顾插入效率，于是提出了2-3树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

2-3树特点

2-3树是一棵平衡树，但不是二叉平衡树。
对于高度相同的2-3树和二叉树，2-3树的节点数要大于满二叉树，因为有些节点可能有三个子节点。
2-3树可以是一棵空树。
对于2节点来说，该节点保存了一个key及对应的value，除此之外还保存了指向左右两边的子节点，子节点也是一个2-3节点，左子节点所有值小于key，右子节点所有值大于key。
对于3节点来说，该节点保存了两个key及对应的value，除此之外还保存了指向左中右三个方向的子节点，子节点也是一个2-3节点，左子节点的所有值小于两个key中较小的那个，中节点的所有值在两个key值之间，右子节点大于两个key中较大的那个。
对2-3树进行中序遍历能得到一个排好序的序列。

插入操作

刚开始是空树，插入节点“A”，创建根节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

插入节点“B”，从根节点开始寻找存放的节点位置，与“A”节点合并后放到同一个叶子上，此时该叶子只包含“AB”两个项目，无需分裂，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

继续插入节点“C”，从根节点开始寻找存放的节点位置，找到“AB”叶子节点，将其放进去，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

但此时该叶子节点包含了“ABC”三个项目，需要将该节点进行分裂操作，分裂的具体过程如下，找到该节点三个项目中中间大的项，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

上移成为最小项和最大项的父节点，而最小项作为中间项的左子节点，最大项作为中间项的右子节点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

继续插入“D”节点，从根节点开始寻找，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

大于“B”，所以往右，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

找到“C”节点，并合并到该叶子节点，该节点只有两个项目，不必分裂。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

继续插入“E”，查找到“CD”叶子节点，放入“E”节点后发现该叶子节点有三个项目，需要分裂，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

将中间项提升到父节点，其余两项分裂成两个子节点，“D”上升到父节点后存放在右边，而且父节点只有两个项目，不必再继续分裂。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

继续插入“F”节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

往下看连续分裂两次的情况，继续插入“G”节点，大于“B”，继续比较，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

大于“D”，往右子节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

到右子节点后与“F”比较，发现大于“F”，放到右边，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

发现“EFG”叶子节点有三个项目，必须分裂，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

将中间项“F”提升到父节点，“E”和“G”左右两项分别称为左右子节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

提升到父节点后发现父节点包含了“BDF”三项，也需要分裂，于是准备将中间项“F”提升，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

发现“BDF”节点本来属于根节点，那么分裂后就没有根节点了，于是需要创建一个新节点作为根节点，即提升的“D”节点作为新的根节点。“B”和“F”左右两项分别作为左右子节点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

总结起来就是：一个节点插入到一棵2-3树中，先寻找该节点应该落到哪个叶子节点上，注意一定是在叶子节点。将新节点作为一个新项加入到叶子节点中，此时如果该节点只有两个项目，则完成插入操作。但如果该节点有三个项目，则需要进行分裂操作，左中右三项按大小排序，将中间项提升到父节点中，而左右两项作为左右子节点，然后可能还没完，因为父节点上可能又包含了三个项目，如果是这样还得做分裂操作，一直递归到父节点只包含一个或两个项目。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

查找

2-3树的查找与二叉树的查找类似，从根节点开始比较，如果相等则查找成功，否则往下继续查找，对于只有两个子节点的节点则在其左右子树中递归查找，而对于有三个子节点的节点则需要在左中右子树中递归查找。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html

如下2-3树，查找“C”节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4620.html