常用树结构总结及其应用

一、红黑树

• 性质1：每个节点要么是黑色，要么是红色。
• 性质2：根节点是黑色。
• 性质3：每个叶子节点（NIL）是黑色。
• 性质4：每个红色结点的两个子结点一定都是黑色。
• 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
• 性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。

• 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
• 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
• 变色：结点的颜色由红变黑或由黑变红。

1)、30张图带你彻底理解红黑树
2)、五分钟搞懂什么是红黑树
3)、红黑树数据结构剖析
4)、漫画算法：什么是红黑树？（适合初学红黑树小白简单易懂）

二、AVL树

• 本质上还是一棵二叉搜索树
• 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
  也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
  1)、彻底搞懂AVL树
  2)、浅析AVL树

三、Trie树

Trie，又经常叫前缀树，字典树等等。它有很多变种，如后缀树，Radix Tree/Trie，PATRICIA tree，以及bitwise版本的crit-bit tree。

1)、Trie（前缀树/字典树）及其应用
2)、数据结构与算法（十一）Trie字典树
3)、Trie树

四、B树

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下:

• 每个结点至多有m个子女;
• 除根结点外,每个结点至少有[m/2]个子女，根结点至少有两个子女;
• 有k个子女的结点必有k个关键字。

B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时,并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。

1)、b+树图文详解
2)、B+树的原理
3)、B树、B-树、B+树、B*树介绍
4)、B树和B+树原理及在索引中的应用

五、各种树结构的用途简介

1)、AVL树，红黑树，B树，B+树，Trie树应用场景简介
2)、AVL树与红黑树（R-B树）的区别与联系
3)、深入理解红黑树与B+树应用场景