动画 | 什么是2-3树？（修改删除操作方式）

客官°小女子只卖身不卖艺 2023-06-25 10:12 7阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

我们回忆一下AVL树，它在插入和删除节点时，总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制，插入一个节点和删除一个节点都有可能调整多个节点的不平衡状态。频繁的左旋转和右旋转操作一定会影响整个AVL树的性能，除非是平衡与不平衡变化很少的情况下，否则AVL树所带来的搜索性能提升不足以弥补平衡树所带来的性能损耗。

那有没有绝对平衡的一种树呢？没有高度差也不会有平衡因子，没有平衡因子就不会调整旋转操作。2-3树正是一种绝对平衡的树，任意节点到它所有的叶子节点的深度都是相等的。

2-3树的数字代表一个节点有2到3个子树。它也满足二分搜索树的基本性质，但它不属于二分搜索树。

2-3树定义

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

2-节点，含有一个元素和两个子树（左右子树），左子树所有元素的值均小于它父节点，右子树所有元素的值均大于它父节点；

3-节点，还有两个元素和三个子树（左中右子树），左子树所有元素的值均小于它父节点，中子树所有元素的值都位于父节点两个元素之间，右子树所有元素的值均大于它父节点。

![format_png 1][]

2-3树查找元素

2-3树的查找类似二分搜索树的查找，根据元素的大小来决定查找的方向。要判断一个元素是否存在，我们先将待查找元素和根节点比较，如果它和其中任意一个相等，那查找命中；否则根据比较的结果来选择查找的方向。

![format_png 2][]

2-3树插入元素

插入元素首先进行查找命中，若查找命中则不予插入此元素，如果需要支持重复的元素则将这个元素对象添加一个属性count。若查找未命中，则在叶子节点中插入这个元素。

空树的插入很简单，创建一个节点即可。如果不是空树，插入的情况分为4种：

1. 向2-节点中插入元素；

2. 向一颗只含有一个3-节点的树中插入元素；

3. 向一个父节点为2-节点的3-节点中插入元素；

4. 向一个父节点为3-节点的3-节点中插入元素。

向2-节点中插入元素

如果未命中查找结束于2-节点，直接将2-节点替换为3-节点，并将待插入元素添加到其中。

![format_png 3][]

向一颗只含有一个3-节点的树中插入元素

如果命中查找结束于3-节点，先临时将其成为4-节点，把待插入元素添加到其中，然后将4-节点转化为3个2-节点，中间的节点成为左右节点的父节点。如果之前临时4-节点有父节点，就会变成向一个父节点为2-节点的3-节点中插入元素，中间节点与父节点为2-节点的合并。

![format_png 4][]

向一个父节点为3-节点的3-节点中插入元素

插入元素后一直向上分解临时的4-节点，直到遇到2-节点的父节点变成3-节点不再分解。如果达到树根节点还是4-节点，则进行分解根节点，此时树高+1（只有分解根节点才会增加树高），下面动画2-3树插入会出这个例子。

![format_png 5][]

动画：2-3树插入

2-3树删除

算法4红黑树删除最小键这一小结里没有特别详细地介绍，但给到了沿着左链接向下进行变换的三种情况：

1. 如果左子节点不是2-节点，完成；

2. 如果左子节点是2-节点，而兄弟节点不是2-节点，将兄弟节点的最小元素移到父节点，父节点的最小元素移到左子节点；

3. 如果左子节点是2-节点，而兄弟节点是2-节点，则左子结点、父节点中最小的元素和兄弟结点合并成4-结点。

![format_png 6][]

删除最小元素

我们注意到在叶子节点不是2-节点的时候，删除一个元素是很简单的，而且删除时不考虑自平衡处理。如果删除一个2-节点会留下一个空节点，破坏了2-3树的绝对平衡。所以，为了保证不会删除一个2-节点，可以设定最左边或者最右边进行向下变换节点。这里设置沿最左边的链接，进行向下变换的三种情况正是如上图中，左子节点的父节点除了根节点都会变换成3-节点或4-节点。

删除任意元素

删除任意元素需要进行命中查找。如果查找未命中则忽略之；如果查找命中则向二叉堆一样删除任意元素，将带删除元素右子树的最小元素替换到待删除元素上，然后对右子树进行删除最小元素。

动画：2-3树删除

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 7][]

**戳一下下方的小程序，24 小时一起学算法**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy95OHNTRUtOODJKbkZvdkZzMkxTMjFMdUxwYUlPZkJOcGliejBjaWFOaGFNcVFSSkw4QWZoeVBDTWFwSW9ZZWFXeUlwa05uWE1nMkwwaWFTem5kOUw5b1k4US82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbkZvdkZzMkxTMjFMdUxwYUlPZkJOcFY3MlRMd3N1czRhTmpiNmpNREs5b2JWNmliRktFbDF4bTBzUFRpYzNCVXhROHZNTVpNSTViYUNBLzY0MA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbkZvdkZzMkxTMjFMdUxwYUlPZkJOcHVwUTdpY0l6ZUVkMVVVeUtXWVVqWFhvU3R3Um9TbVFxazNTZGsybEFDWHdBRmlhZDlZaWNFNjVaZy82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbkZvdkZzMkxTMjFMdUxwYUlPZkJOcE01OXFzTUdya1pSa1V5bnhIZ3BJbjNGbzJwaWFyQ2M0aWNjUkQ2a0c1QWxUOWJ5bkt6aWNlMmxLZy82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbkZvdkZzMkxTMjFMdUxwYUlPZkJOcDZRUFVHTjF4WHdNVFBjaWI3RGlhZUY5R1pnUnFKdHV6M3hNSGtTeWcwbktqdmQzdmljbmlhMUhyeUEvNjQw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbkZvdkZzMkxTMjFMdUxwYUlPZkJOcFBuWThVYnN4U01SMUVCZDBPczhpY3p5YnZub1ViMmI0QnhtdVNDeHUzc0h4ZXpveDZMczBNRHcvNjQw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA?x-oss-process=image/format,png