树，二叉树，完全二叉树，二叉堆，二叉查找树、字典树、红黑树的联系与区别（图解）

た入场券 2023-09-24 22:27 61阅读 0赞

### 文章目录 ###

*   *  一、树的结构
     *  二、二叉树
     *  三、完全二叉树
     *  四、二叉堆
     *  五、二叉查找树
     *  六、字典树
     *  七、红黑树

## 一、树的结构 ##

![在这里插入图片描述][55c871e35d8244c5a429af7ff1652eb0.png]

## 二、二叉树 ##

二叉树在满足树的结构条件下，还增加了限制条件：  
每个节点最多有两个孩子，这两个子树有左右之分次序不可颠倒

![在这里插入图片描述][1326b83634734197b967e31b537cfd23.png]

## 三、完全二叉树 ##

完全二叉树是特殊的二叉树，除了最后一层，每一层都是填满的，最后一层会从第一个节点开始，依次向后增加节点

例如abc是完全二叉树def不是：

![在这里插入图片描述][e8ab0132bac5409b90d696c48c95dd1c.png]

## 四、二叉堆 ##

二叉堆在完全二叉树的基础上，增加了**节点取值**的限制条件

有两种堆， 最大堆和最小堆，最大堆各个父节点的值总是大于或者等于任何一个子节点的值，最小堆则各个父节点的值总是小于或者等于任何一个子节点的值；最大堆中最大的元素刚好存储在堆顶，最小堆中最小的元素刚好存储在堆顶

![在这里插入图片描述][86f4744cf36e437a91c1f4c6be6a9e2a.png]  
![在这里插入图片描述][25fa82e54bc8438d90e503c77d38410d.png]

## 五、二叉查找树 ##

二叉查找树是一种查找结构，它是一颗特殊的二叉树具有下面这3个性质：

1.  如果**左子树**不空则左子树上所有结点的值均**小于或等于**该结点的值
2.  如果**右子树**不空则右子树上所有结点的值均**大于或等于**该结点的值
3.  **左右子树也分别为二叉查找树**

另外，等于的情况一般只出现在左子树或右子树中的某一侧，二叉查找树中没有重复的节点，中序遍历二叉查找树，就会得到一个从小到大的序列，所以它也被称为二叉排序树

![在这里插入图片描述][34f49c680c17486d96e44763d44b6a1d.png]

## 六、字典树 ##

**tire树又称字典树或前缀树**，是一种**有序的，用于统计排序和存储字符串**的数据结构，它与二叉查找树不同，**关键字不是直接保存在节点中，而是由节点在树中的位置决定**  
![在这里插入图片描述][ed3630ba732647e7ae80115a5409ba98.png]

![在这里插入图片描述][2408b7b88bb44d86a8521c851ac740c1.png]

每个节点都代表了一个字符，从第一层孩子节点到中间的，某个标记的节点代表了存储的字符串，一般情况下不是所有的节点都有对应的字符串，只有叶子节点和部分内部节点进行了特殊的标记，才存储字符串  
![在这里插入图片描述][3cac188504254c5d99c5e588cfad0f0d.png]

例如将这些字符串存储到字典树中，被标记为红色的节点代表存储了，从根到该节点之间字符组成的字符串  
![在这里插入图片描述][0c1d1eec27024cd298ac5365760a90a7.png]

例如abcd这条路径中，c和d被标记说明存储abc和abcd  
![在这里插入图片描述][6c166d2ff21e420da37111357a6d1a7b.png]

**一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串**，例如abc、abcd、abd都有相同的前缀ab，在字典树中它们有相同的祖先节点a和b

![在这里插入图片描述][5c6b0f6be0784e06b026e25e6f148a4f.png]

trie树的最大优点就是利用字符串的公共前缀，来减少存储空间与查询时间，从而最大限度地减少无谓的字符串比较，是非常高效的字符串查找数据结构，查我和插入字符串都可达到 **O（1）** 算法复杂度  
![在这里插入图片描述][605e7f4f26344d3c8999063d12bc3d7a.png]

## 七、红黑树 ##

在红黑树当中，节点被标记为红色和黑色两种颜色，并且它还具有下面这3点性质：

![在这里插入图片描述][9ba05350abac4ea3b5792fceedfb00e8.png]

其他：

![在这里插入图片描述][a399235b70f94ae98d9687e7ba06f928.png]

![在这里插入图片描述][1e765c7d79ee4420afcc3dd732d2f36d.png]

![在这里插入图片描述][cce3c625dd3a4ea9a62824e52bcf0963.png]

![在这里插入图片描述][c903869fe52c49f8a19f53a6804147b5.png]

![在这里插入图片描述][c07511ca9079409e86a56cef4614085d.png]

![在这里插入图片描述][b11240ade8a542ffa4989a0bee8500e0.png]

[55c871e35d8244c5a429af7ff1652eb0.png]: https://img-blog.csdnimg.cn/55c871e35d8244c5a429af7ff1652eb0.png
[1326b83634734197b967e31b537cfd23.png]: https://img-blog.csdnimg.cn/1326b83634734197b967e31b537cfd23.png
[e8ab0132bac5409b90d696c48c95dd1c.png]: https://img-blog.csdnimg.cn/e8ab0132bac5409b90d696c48c95dd1c.png
[86f4744cf36e437a91c1f4c6be6a9e2a.png]: https://img-blog.csdnimg.cn/86f4744cf36e437a91c1f4c6be6a9e2a.png
[25fa82e54bc8438d90e503c77d38410d.png]: https://img-blog.csdnimg.cn/25fa82e54bc8438d90e503c77d38410d.png
[34f49c680c17486d96e44763d44b6a1d.png]: https://img-blog.csdnimg.cn/34f49c680c17486d96e44763d44b6a1d.png
[ed3630ba732647e7ae80115a5409ba98.png]: https://img-blog.csdnimg.cn/ed3630ba732647e7ae80115a5409ba98.png
[2408b7b88bb44d86a8521c851ac740c1.png]: https://img-blog.csdnimg.cn/2408b7b88bb44d86a8521c851ac740c1.png
[3cac188504254c5d99c5e588cfad0f0d.png]: https://img-blog.csdnimg.cn/3cac188504254c5d99c5e588cfad0f0d.png
[0c1d1eec27024cd298ac5365760a90a7.png]: https://img-blog.csdnimg.cn/0c1d1eec27024cd298ac5365760a90a7.png
[6c166d2ff21e420da37111357a6d1a7b.png]: https://img-blog.csdnimg.cn/6c166d2ff21e420da37111357a6d1a7b.png
[5c6b0f6be0784e06b026e25e6f148a4f.png]: https://img-blog.csdnimg.cn/5c6b0f6be0784e06b026e25e6f148a4f.png
[605e7f4f26344d3c8999063d12bc3d7a.png]: https://img-blog.csdnimg.cn/605e7f4f26344d3c8999063d12bc3d7a.png
[9ba05350abac4ea3b5792fceedfb00e8.png]: https://img-blog.csdnimg.cn/9ba05350abac4ea3b5792fceedfb00e8.png
[a399235b70f94ae98d9687e7ba06f928.png]: https://img-blog.csdnimg.cn/a399235b70f94ae98d9687e7ba06f928.png
[1e765c7d79ee4420afcc3dd732d2f36d.png]: https://img-blog.csdnimg.cn/1e765c7d79ee4420afcc3dd732d2f36d.png
[cce3c625dd3a4ea9a62824e52bcf0963.png]: https://img-blog.csdnimg.cn/cce3c625dd3a4ea9a62824e52bcf0963.png
[c903869fe52c49f8a19f53a6804147b5.png]: https://img-blog.csdnimg.cn/c903869fe52c49f8a19f53a6804147b5.png
[c07511ca9079409e86a56cef4614085d.png]: https://img-blog.csdnimg.cn/c07511ca9079409e86a56cef4614085d.png
[b11240ade8a542ffa4989a0bee8500e0.png]: https://img-blog.csdnimg.cn/b11240ade8a542ffa4989a0bee8500e0.png