2-3树的插入

阳光穿透心脏的1/2处 2022-08-07 09:41 11阅读 0赞

**2-3树所有叶子都在同一个层次,也就是说每一层的叶子数目都是相等的,如图:**

![Center][]

一:插入数据3,

插入的时候从根结点8发现,比8大往左走,到达4,发现比4小,继续往左走,然后发现比1大,并且此时1结点只有一个结点,所以可以插入,如图:

![20150329135558233][]

二.插入5

插入的时候从根结点8发现,比8大往左走,到达4,发现比4大,继续往右走,而6,7结点此时是满了无法插入,那么就往上找4结点,4结点可以插入,此时插入的时候需要将6结点与4结点合并起来,也就是将6,7结点分裂,7成为6的右结点,5成为6的左节点(4的右结点),如图:

![20150329140721343][]

三.插入11

插入的时候,从根节点8比较,比8大往右走,在12,14结点中发现比12小,继续往左走,找到了9,10,而此时9,10结点满了,根据往上找原则,找12,14,而12,14也满了,再继续往上找原则,找到了8,此时8还有位置,8指向的12进行分裂得到12,14,8和12结合,12的右结点指向14,而剩余的9,10,11组成10为根的结点,然后12的左结点连接10,如图:

![20150329143713146][]

四.插入2

插入的时候,从根节点8比较,比8大往左走,比4大往左走,走到最后一个叶子结点1,3,发现此时满了,无法插入,根据往上找的原则,找到4,6发现4,6结点也满了,继续往上找,8,12也满了,由于根节点都满了,所以就需要扩展树的高度,这就是2-3树的优势了,充分利用树高度达到查找的时候可以更快地找到!

此时从底部开始分裂(1,3)结点,2成为1,3的父节点,如果此时4的左边指向2则整棵树的高度不符合2-3树的定义,而此时发现右边的高度有问题,所以进行(4,6)结点分裂,将4的右边指向以6为5,7的父节点,此时以4为根节点的树就达到了平衡的效果了,但是呢(8,12)为根节点的树的左右高度不满足,所以将(8,12)结点进行分裂,8的右边指向12结点,(10,14以12为父节点),那么就搞定了,如图:

![20150329150840450][]

[Center]: /images/20220805/82349c6219b647e5bf870bf871d0e722.png
[20150329135558233]: /images/20220805/1db192877cbb4178b89df81acb8c854e.png
[20150329140721343]: /images/20220805/66281363cba34916874a0dc042be455a.png
[20150329143713146]: /images/20220805/6635b3fb636c4afd90fb1ab28f683792.png
[20150329150840450]: /images/20220805/76cb83f645a94876a9ad57e2b159a54d.png