常见树形数据结构总结 有更新!

  |   0 评论   |   169 浏览

最近补了一些基础知识,发现jdk的集合、MySQL、Redis等,都离不开树相关的数据结构,因此这里把一些相关的树形数据结构做了下整体。
总体来说,树的结构主要是二叉树与多叉树,其中:BST、AVL、RBT是二叉树,B树、B+树、B*树是多叉树。

1. 二叉搜索树(BST)

特性

  1. 所有非叶子结点至多拥有两个儿子(Left和Right);
  2. 所有结点存储一个关键字;
  3. 非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

总结

  1. 二叉搜索树在二叉树的基础上,增加了如下特性:左子树<结点<右子树
  2. 由于没有规定节点的分布情况,同样的数据,以下是两种极端的分布情况:
    imagepng

这两种都是BST树,左侧的搜索性能要好于右侧,右侧的搜索性能已经是线性的;所以在使用BST时要尽量让其保持左侧的结构,即平衡状态。

2. 平衡树(AVL)

特性

平衡二叉树或为空树,或为如下性质的二叉排序树:

  1. 左右子树深度之差的绝对值不超过1;
  2. 左右子树仍然为平衡二叉树.

总结

AVL解决了BST的搜索性能问题。AVL对平衡的定义比较严格,因此在增加或者删除节点的时候,旋转的次数比较多。

3. 红黑树(RBT)

特性

红黑树上每个结点内含五个域,color,key,left,right,p。如果相应的指针域没有,则设为NIL。
一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:

  1. 每个结点要么是红的,要么是黑的。
  2. 根结点是黑的。
  3. 每个叶结点,即空结点(NIL)是黑的。
  4. 如果一个结点是红的,那么它的俩个儿子都是黑的。
  5. 对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
    imagepng

总结

  1. 红黑树也是BST,但相对于AVL来说,红黑树是一种弱平衡树,用非严格的平衡来换取增删节点时候旋转次数的降低;
  2. 搜索的次数远远大于插入和删除,那么选择AVL树,如果搜索,插入删除次数几乎差不多,应该选择RB树。

4. B树

特性

一棵最小度为t的B树是满足如下四个条件的平衡多叉树:

  1. 每个节点最多包含2t−1个关键字;除根节点外的每个节点至少有t−1个关键字(t≤2),根节点至少有一个关键字;
  2. 一个节点u中的关键字按非降序排列:u.key1≤u.key2≤…u.keyn;
  3. 每个节点的关键字对其子树的范围分割。设节点u有n+1个指针,指向其n+1棵子树,指针为u.p1,…u.pn,关键字ki为u.pi所指的子树中的关键字,有k1≤u.key1≤k2≤u.key2…成立;
  4. 所有叶子节点具有相同的深度,即树的高度h。这表明B树是平衡的。

imagepng

总结

  1. 对于一个包含n个关键字(n≥1),最小度数t≥2的B树T,其高度h满足如下规律:

imagepng

  1. 与普通的二叉平衡树(AVL/RBT)相比,由于单节点存储的Key值变多,可以有效降低节点的读取次数。

5. B+树

特性

B+树的定义如下:

  1. 除根节点外的内部节点,每个节点最多有m个关键字,最少有⌈m/2⌉个关键字。其中每个关键字对应一个子树(也就是最多有m棵子树,最少有⌈m/2⌉棵子树);
  2. 根节点要么没有子树,要么至少有2棵子树;
  3. 所有的叶子节点包含了全部的关键字以及这些关键字指向文件的指针,并且:
    1. 所有叶子节点中的关键字按大小顺序排列
    2. 相邻的叶子节点顺序链接(相当于是构成了一个顺序链表)
    3. 所有叶子节点在同一层
  4. 所有分支节点的关键字都是对应子树中关键字的最大值

imagepng

总结

  1. B+树是B树的一种变形,内部节点仅仅起到索引的作用。它更适合实际应用中操作系统的文件索引和数据库索引。
  2. B+树的磁盘读写代价更低
  3. B+树的查询效率更加稳定
  4. B+树更有利于对数据库的扫描

6. B*树

特性

B*树在B+树的基础,主要增加了以下特性:

  1. 非叶子结点也增加链表指针,直接指向数据节点
  2. B+树的非根和非叶子结点再增加指向兄弟的指针

总结

  1. B*树分配新结点的概率比B+树要低,空间使用率更高
  2. 目前没有找到B*树的具体应用

参考文献

https://blog.csdn.net/sup_heaven/article/details/39313731
http://www.cnblogs.com/skywang12345/p/3245399.html
https://blog.csdn.net/guoziqing506/article/details/64122287
http://www.cnblogs.com/yangecnu/p/Introduce-2-3-Search-Tree.html
https://blog.csdn.net/zhuanzhe117/article/details/78039692
https://blog.csdn.net/qq_26768741/article/details/53164202



---------------------------
本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处,尊重他人劳动。
转载请注明:文章转载自 xiajl.cn

评论

发表评论