树

树

• 每个节点有零个或多个子节点
• 没有父节点的节点被称为根节点
• 每个非根节点只能有一个父节点

二叉树

在树的基础上，增加限制条件：每个节点最多含有两个子节点。

二叉查找树

在二叉树的基础上，增加限制条件：

• 左子树节点的值 > 根节点的值 > 右子树节点的值（对于任意节点来说）
• 没有键值相等的节点

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低为 O ( log ? n ) 。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

平衡二叉树

在二叉查找树的基础上，增加限制条件：每个节点的左子树和右子树高度差至多为1。

红黑树

在平衡二叉树的基础上，增加限制条件：

• 每个节点有红色，黑色两种选项
• 根节点和叶子节点必须是黑的
• 如果一个节点是红的，那么它的两个儿子都是黑的（红子黑）
• 任意节点到叶子节点NIL都包含相同数目的黑色节点

红黑树是一种应用很广的数据结构，如在Java集合类中TreeSet和TreeMap的底层，C++STL中set与map，以及linux中虚拟内存的管理。

哈夫曼树

也称最优二叉树。

最优体现在树的带权路径长度最小：（叶子节点的权值 和 叶子节点到根节点的路径长度的乘积 ）*所有叶子节点

哈夫曼树特征：权值小的节点远离根节点，权值大的节点靠近根节点。

B树

BTree也称为平衡多路查找树

B-Tree是为磁盘等外存储设备设计的一种平衡查找树。

B+Tree

B+Tree是在B-Tree基础上的一种优化

• 非叶子结点只存储键值信息，不存储数据
• 所有的叶子结点都有一个链指针
• 数据记录都存放在叶子结点中

参考：

数据结构之树

原文链接:https://www.cnblogs.com/noneplus/p/11641096.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有