2019-10-09 09:33:30来源:博客园 阅读 ()

独享虚拟主机 新品上线,资源独享,建站优先!

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


二叉树

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


二叉查找树

在二叉树的基础上,增加限制条件:

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

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


平衡二叉树

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


红黑树

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

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

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


哈夫曼树

也称最优二叉树。

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

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


B树

BTree也称为平衡多路查找树

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

1569143287075


B+Tree

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

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

1569143297523


参考:

数据结构之树


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

标签:load时间应用数据数组ESET

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

上一篇:ping通谷歌后发送QQ邮件通知

下一篇:netty源码解解析(4.0)-23 ByteBuf内存管理:分配和释放