AVL树和2-3-4树详解

我会带着你远行 2024-04-08 11:36 110阅读 0赞

## 一、AVL树 ##

BST存在的问题是，树在插入的时候会导致倾斜，不同的插入顺序会导致数的高度不一样，而树的高度直接影响了树的查找效率。最坏的情况所有的节点都在一条斜线上，这样树的高度为N。基于BST存在的问题，平衡查找二叉树(Balanced BST)产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树（高度平衡树，具备二叉搜索树的全部特性，而且左右子树高度差不超过1)和红黑树。

AVL树是如何实现平衡的呢?，具体是通过左旋或者右旋来实现的。具体如下图:

![c0e6ba4645e94e58af1a2719ac3bcd3d.png][]

具体步骤:

![9d808be678464d378466036b25f3e05b.png][] ![ff2daa23775a4231ad7044a8b66b306a.png][]

![bbccb66503fc462fa65172bf52f82bc9.png][] ![b1b1d4db7e70499890cc19c89850a8c8.png][]

![02e62a525fad41aabab3d22808509ddc.png][] ![18ba89fefccb42e6b9042bf05d8483a6.png][]

![a327ca10917844bfb77ea18ee6576e5d.png][] ![ebd8cc0436234f6c9a4ae2fb935965e2.png][]

![95731a73808f4533af83c9add1bd142e.png][] ![387b74ab9ba0424e9c47c04226537264.png][]

![07d1abe03a4c42038319fd59045e9685.png][] ![fe220be36027457e9fac84285c042ee6.png][]

![2a9c1b64852d4a168328a6ec0b6357cc.png][]

这就是将一个链表转换成AVL树的整个过程, 过程还是挺繁琐的, 主要就是通过**左旋和右旋**来实现.

## 二、2-3-4树 ##

### 2.1、概念介绍 ###

2-3-4树是**四阶的B树**(Balance Tree)，他属于一种**多路查找树**，它的结构有以下限制:**所有叶子节点都拥有相同的深度。**

节点只能是2-节点、3-节点、4-节点之一。

*  2-节点:包含1个元素的节点，有2个子节点;
 *  3-节点:包含2个元素的节点，有3个子节点;
 *  4-节点:包含3个元素的节点，有4个子节点;

所有节点必须至少包含1个元素

元素始终保持**排序顺序**，**整体上保持二叉查找树的性质，即父结点大于左子结点，小于右子结点**;

而且结点有多个元素时，每个元素必须大于它左边的和它的左子树中元素。

下图是一个典型的2-3-4树

![917c8d27cfe04b07a6441a2b56e1a882.png][]

2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但由于其结点元素数不确定，在一些编程语言中实现起来并不方便，实现一般使用它的等同——红黑树。

### 2.2、生成的过程 ###

### ![09ba987050a1478e8ca38df8ebeea3e3.png][]   ![7d683557e4c44c9f84ede955a10a327f.png][] ![92b2606d65274d238fe668aaf5e41784.png][] ###

### ![d9ee9c84b0c5418fb9f7cfdff03436d3.png][]   ![593bd38284ea464eb00c2b54c9650a10.png][] ![f5560e307ad14abdb4f65627c274ddc2.png][] ###

![46d6b223405d4a6e81b77b5e3f5c5218.png][]

![6b393d3475da42929244ca84627f1903.png][]

![881e23f9da2d4c9ab2778dbbcb92faaa.png][]![f32bbbf2cdb540d2b005f61594527eca.png][]

[c0e6ba4645e94e58af1a2719ac3bcd3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1ca32462646c4b8ea0d2bc03a4c9f261.png
[9d808be678464d378466036b25f3e05b.png]: https://img-blog.csdnimg.cn/9d808be678464d378466036b25f3e05b.png
[ff2daa23775a4231ad7044a8b66b306a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c5d0f81fadb74a57b8fc39cbd73674ca.png
[bbccb66503fc462fa65172bf52f82bc9.png]: https://img-blog.csdnimg.cn/bbccb66503fc462fa65172bf52f82bc9.png
[b1b1d4db7e70499890cc19c89850a8c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/bd63d76aedd24730b99022b0b77e687f.png
[02e62a525fad41aabab3d22808509ddc.png]: https://img-blog.csdnimg.cn/02e62a525fad41aabab3d22808509ddc.png
[18ba89fefccb42e6b9042bf05d8483a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/9c3f3c01c1124078bf114874fd33daec.png
[a327ca10917844bfb77ea18ee6576e5d.png]: https://img-blog.csdnimg.cn/a327ca10917844bfb77ea18ee6576e5d.png
[ebd8cc0436234f6c9a4ae2fb935965e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/b926310589084b4692a7788994b2b934.png
[95731a73808f4533af83c9add1bd142e.png]: https://img-blog.csdnimg.cn/95731a73808f4533af83c9add1bd142e.png
[387b74ab9ba0424e9c47c04226537264.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/926e242ecd6d4d4aa01f217f7a613282.png
[07d1abe03a4c42038319fd59045e9685.png]: https://img-blog.csdnimg.cn/07d1abe03a4c42038319fd59045e9685.png
[fe220be36027457e9fac84285c042ee6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c4d6c49472a241bda8ee110f1836e9fc.png
[2a9c1b64852d4a168328a6ec0b6357cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/b53d1ff04f7f45d98b4baa52dfe7fbe8.png
[917c8d27cfe04b07a6441a2b56e1a882.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/ff51f7c27192481aaf6a426ec70da2ec.png
[09ba987050a1478e8ca38df8ebeea3e3.png]: https://img-blog.csdnimg.cn/09ba987050a1478e8ca38df8ebeea3e3.png
[7d683557e4c44c9f84ede955a10a327f.png]: https://img-blog.csdnimg.cn/7d683557e4c44c9f84ede955a10a327f.png
[92b2606d65274d238fe668aaf5e41784.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/8277a6e2e17c46dd982c78aafa456fe1.png
[d9ee9c84b0c5418fb9f7cfdff03436d3.png]: https://img-blog.csdnimg.cn/d9ee9c84b0c5418fb9f7cfdff03436d3.png
[593bd38284ea464eb00c2b54c9650a10.png]: https://img-blog.csdnimg.cn/593bd38284ea464eb00c2b54c9650a10.png
[f5560e307ad14abdb4f65627c274ddc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/810b7117649c47b0b6dcce99da957b3e.png
[46d6b223405d4a6e81b77b5e3f5c5218.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/706e291798b442289da718e8d83a6904.png
[6b393d3475da42929244ca84627f1903.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/90c2b7b742884093988a92a75d69c68c.png
[881e23f9da2d4c9ab2778dbbcb92faaa.png]: https://img-blog.csdnimg.cn/881e23f9da2d4c9ab2778dbbcb92faaa.png
[f32bbbf2cdb540d2b005f61594527eca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/28fe6a407a094656a85a0f9e02d3d388.png