数据结构-树

- 日理万妓 2022-12-06 01:18 9阅读 0赞

参考：[数据结构中各种树][Link 1]

# 二叉树 #

二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构。

**定义：** 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

**满二叉树：** 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。

**完全二叉树：** 若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

**二叉树遍历顺序**

> 前序遍历：根节点—>左子树—>右子树
> 
> 中序遍历：左子树—>根节点—>右子树
> 
> 后序遍历：左子树—>右子树—>根节点

# 二叉查找树 #

又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

*  若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
 *  若右子树不空，则右子树上所有结点的值均大于或等于它的根节点的值；
 *  左、右子树也分别为二叉排序树；
 *  没有键值相等的节点。

**二叉查找树的性质： 对二叉查找树进行中序遍历，即可得到有序的数列。**

**二叉查找树的时间复杂度：它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度(树的不合理，形成了一个链表状的树)。原因在于插入和删除元素的时候，树没有保持平衡。**

**二叉查找树的高度决定了二叉查找树的查找效率。**

为了查找保证不出现O(n)，实现平衡二叉树在插入和删除结点时动态保证树的平衡。

# 平衡二叉树 #

**平衡二叉树定义：** 平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。

最小二叉平衡树的节点的公式如下：

F(n)=F(n-1)+F(n-2)+1

这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

## 平衡查找树之AVL树 ##

**AVL树：** 每次插入和删除后可能需要通过一次或多次书的旋转来重新平衡这个数树，保证树的左右子树高度之差不超过1。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

![在这里插入图片描述][20200911163524486.png_pic_center]  
![在这里插入图片描述][20200911163558388.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70_pic_center 1]

**左左旋转：旋转一次，与右右情况对称**  
![在这里插入图片描述][20200911163804332.png_pic_center]  
**左右旋转：旋转两次与右左情况对称**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70_pic_center 3]

## 红黑树 ##

**红黑树：** 红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。**它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。**

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。

**红黑树性质：**

> 红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制的一般要求外，对于任何有效的红黑树增加了额外要求。
> 
>  *  性质(1)：节点是红色或黑色
>  *  性质(2)：根是黑色
>  *  性质(3)：所有叶子都是黑色（叶子是NIL节点）
>  *  性质(4)：每个红色节点必须有两个黑色的子节点(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
>  *  性质(5)：从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

这些约束 **确保了红黑树的关键特性：** 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。 结果是这个**树大致上是平衡**的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉树。

要知道为什么这些性质确保了这个结果，注意到`性质(4)` 导致路径不能有两个连续的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据`性质(5)` 所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

**红黑树的自平衡操作：**

> 因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉树上的只读操作相同。然而，\*\*在红黑树上进行插入操作和删除操作会导致不在符合红黑树的性质。\*\*恢复红黑树的性质需要少量( O(logn) )的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作时两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(logn) 次。
> 
> --------------------
> 
> 首先以二叉查找树的方法增加节点并标记它为红色。如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑色节点，这个是很难调整的(违背`性质(5)`)。但是设为红色节点后，可能会导致出现两个连接红色节点的冲突，可以通过颜色调换和树旋转来调整。

# B树 #

**B树也是一种查找的平衡树，但它并不是二叉树。**

**B树的定义：** B树是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉树不同，B-树为系统最优化大块数据的读和写操作。B tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

在B树中**查找给定关键字**的方法是，首先把根节点取来，在根节点所包含的关键字 K1,…,Kn 查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。

**B树作为一种多路搜索树（并不是二叉的）：**

> 1.  定义任意非叶子结点最多只有M个儿子；且M>2;
> 2.  根节点的儿子数为\[2, M\];
> 3.  除根节点以外的非叶子结点的儿子数为\[M/2, M\];
> 4.  每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
> 5.  非叶子结点的关键字个数=指向儿子的指针个数-1；
> 6.  非叶子结点的关键字：K\[1\]，K\[2\]，…，K\[M-1\]；且K\[i\] < K\[i+1\]；
> 7.  非叶子结点的指针：P\[1\]，P\[2\]，…，P\[M\]；其中P\[1\]指向关键字小于K\[1\]的子树，P\[M\]指向关键字大于K\[M-1\]的子树，其他P\[i\]指向关键字属于（K\[i-1\]，K\[i\]）的子树；
> 8.  所有叶子结点位于同一层；

下图为一个M=3的B树实例：

![在这里插入图片描述][20200911164342857.gif_pic_center]

# B+树 #

**B+树是B树的变体，也是一种多路搜索树；**

> 1.  其定义基本与B树相同，除了：
> 2.  非叶子结点的子树指针与关键字个数相同
> 3.  非叶子结点的子树指针P\[i\]，指向关键字值属于 \[ K\[i\], K\[i+1\] ) 的子树（B-树是开区间）；
> 4.  为所有叶子结点增加一个链指针；
> 5.  所有的关键字都在叶子结点出现；

**B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；**

**B+的性质：**

> 1.  所有关键字都出现叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
> 2.  不可能在非叶子结点命中；
> 3.  非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
> 4.  更适合文件索引系统。

**B+树创建的示意图：**  
![在这里插入图片描述][20200911164418487.gif_pic_center]

[Link 1]: https://www.cnblogs.com/jiangxin/p/11810772.html
[20200911163524486.png_pic_center]: /images/20221123/c807314c24bb4a7fb2b8835398ee08f1.png
[20200911163558388.png_pic_center]: /images/20221123/0db5d246816240d5b66ceedab4cc7792.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b47bc485c6794523bfaa1525fb987b93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/05aa50b0ae64408ea3cdec218b16cea8.png
[20200911163804332.png_pic_center]: /images/20221123/4a2f30d020aa4dd9ad636c66a58b66a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/3228db79896042e09d03b7c324bd9c87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/4ee0bc4e0d1d4b4d833659694e2107c3.png
[20200911164342857.gif_pic_center]: /images/20221123/8da48f35c19a41e39a3f64f708c91cec.png
[20200911164418487.gif_pic_center]: /images/20221123/d870b4aa29b04d9dae7f816ea75bd44d.png