xingliuhua
文章 标签 分类
xingliuhua

目录

树结构

xingliuhua 收录于 笔记
   约 1652 字   预计阅读 4 分钟 

平衡二叉树

平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构。 ./pic1.png

特点

  • 非叶子节点只能允许最多两个子节点存在。
  • 每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值
  • 树的左右两边的层级数相差不会大于1;
  • 没有值相等重复的节点;

优势

层级越深，查找速度越慢。 为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如AVL、Treap、红黑树，使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找。

红黑树

红黑树是一颗二叉树。它有自己的特定的规则来保证树的深度比普通的二叉排序树小，但它不是完全的平衡二叉树。 ./pic2.png

特点

  • 每个结点或者为黑色或者为红色。
  • 根结点为黑色。
  • 每个叶结点(实际上就是NULL指针)都是黑色的。
  • 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）。
  • 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。

优势

红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高。

红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组。典型地，JDK 提供的集合类 TreeMap 本身就是一个红黑树的实现。

红黑树左旋

红黑树插入或删除后，以不满足条件，要进行旋转并着色。 左旋： ./pic3.png

红黑树右旋

./pic4.png

b树

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个）。

特点

  • 所有节点关键字是按递增次序排列，并遵循左小右大原则；
  • 非叶节点的子节点数>1，且<=M ，且M>=2。M就是叉路树。
  • 枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
  • 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

./pic5.png

查找流程

如上图我要从上图中找到E字母，查找流程如下

  1. 获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；

  2. 拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；

  3. 拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

优势

B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。

b+树

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。

特点

  • B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；

  • B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；

  • B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。

  • 非叶子节点的子节点数=关键字数

./pic6.png

优势

  • B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
  • B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
  • B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
  • B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描
更新于 2019-04-12
 数据结构
返回 | 主页