数据结构(一)——树

数据结构(一)——树

前言

       在数据结构的学习当中,看到后面树,图,散列的时候已经有点难度,理解的较浅,学习完后面的知识,就发现,这些数据结构和经典算法都用在了一些常用工具的实现原理上,所以需要把这些知识总结一下,今天重点说下树。

       在算法题的做题当中就已经学习了简单的数据结构,hashmap中又用到散列,为了理解 TreeMap 的底层实现,必须先介绍排序二叉树和平衡二叉树,然后继续介绍红黑树。平衡二叉树和红黑树又是一种特殊的二叉排序树。二叉排序树是一种特殊结构的二叉树,可以非常方便地对树中所有节点进行排序和检索。mysql索引也是b+,b-树的原理。这里总结一下:

二叉排序树/二叉查找树/二叉搜索树/BST

       标题已经说明它的名称之多,我们先说下排序二叉树特性:

  1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值
  1. 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值
  1. 它的左、右子树也分别为排序二叉树

插入

       已知一个关键字值为key的结点s,若将其插入到二叉排序树中,只要保证插入后仍符合二叉排序树的定义即可。插入可以用下面的方法进行:

  1. 若二叉排序树是空树,则key成为二叉排序树的根;
  2. 若二叉排序树非空,则将key与二叉排序树的根进行比较。如果key的值等于根结点的值,则停止插入;如果key的值小于根结点的值,则将key插入左子树,如果key的值大于根结点的值,则将key插入右子树。
  3. 重复步骤2,直到找到合适的插入位置。

删除

       当程序从排序二叉树中删除一个节点之后,为了让它依然保持为排序二叉树,程序必须对该排序二叉树进行维护。维护可分为如下几种情况:

  1. 被删除的节点是叶子节点,则只需将它从其父节点中删除即可。
  2. 如果待删除节点左子树存在右子树不存在,或者左子树不存在右子树存在。直接将其子树中存在的一边候补上来即可。
  3. 若被删除节点 p 的左、右子树均非空,有两种做法:一:将 pL 设为 p 的父节点 q 的左或右子节点(取决于 p 是其父节点 q 的左、右子节点),将 pR 设为 p 节点的中序前趋节点 s 的右子节点(s 是 pL 最右下的节点,也就是 pL 子树中最大的节点)。二:以 p 节点的中序前趋或后继替代 p 所指节点,然后再从原排序二叉树中删去中序前趋或后继节点即可。(也就是用大于 p 的最小节点或小于 p 的最大节点代替 p 节点即可)。

       下面我们结合图例来说明。当是左子树右子树只有一个存在时如下图:

       如果左右子树都存在:

被删除节点左右子节点不为空的情形,采用到是第一种方式维护:

被删除节点左右子节点不为空的情形,采用到是第二种方式维护:

       TreeMap 删除节点采用上图第二种方式的情形进行维护——也就是用被删除节点的右子树中最小节点与被删节点交换的方式进行维护。

       在使用第二种方式进行维护时,如果使用前驱节点代替被删除的节点,则前驱节点可能还存在左子树(因为前驱节点是根节点左子树中最右边的节点),而如果是后继节点的话,这个后继节点可能还存在右子树。他们的处理方法相同,直接将子树移上去即可。

       一定要理解,无论是前驱还是后继节点,不可能同时具有左子树或右子树,这就为删除替代节点后的操作带来了方便。如下图:

tip:直接前驱后继是按中序序列化而来。

查找

       从二叉排序树中进行查找时,根据树的性质,节点的左子树必定小于根节点,右子树必定大于根结点。如果查找的节点值小于根节点,则进入左子树,大于进入右子树,重复这个比较步骤直到找到这个节点或者这个节点不存在。

总结

       二叉树以链式方式存储,保持了链接存储结构在执行插入或删除操作时不用移动元素的优点,只要找到合适的插入和删除位置后,仅需要修改链接指针节课。插入删除的时间性能比较好。而丢与二拆排序树的查找,走的就是从根节点到要查找的节点的路径,其比较次数等于给定值的节点在二叉排序树的层数。极端情况,最少为1次,即根节点就是要找的节点,最多也不会超过树的深度。也就是说,二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于,二叉排序树的形状是不确定的。可能出现以下情况,而二叉平衡树就不会:

二叉平衡树/AVL

       ALV树中左右子树的高度差值最大不超过1。树在查找、插入和删除时平均和最坏的情况下都是O(logn)。在一颗二叉搜索树查找一个值的平均时间复杂度为log(n),但是若查找树的所有的节点向一边倾斜,这时候的查找就退化为线性查找,复杂度为n。为了获得更高的查找效率,就有了AVL树的概念,对于一颗非平衡的AVL树,可以通过旋转变换为AVL树。

       由于平衡二叉树也是排序二叉树,所以使用二叉树的插入、删除和查找操作即可。只是在操作完成后,为了下次能够保持一个好的检索效率,也为了防止这个链表退化为普通链表,则需要对树进行旋转。旋转可以再次达到平衡。主要包括:左旋转、右旋转、左右旋转、右左旋转。

LL

       插入一个新节点到根节点的左子树的左子树,导致根节点的平衡因子由1变为2.需要 右 旋转来解决。

LR

插入一个新节点到根节点的左子树的左子树,导致根节点的平衡因子由1插入一个新节点到根节点的左子树的右子树,导致根节点的平衡因子由1变为2.需要先左旋后右旋转来解决。

RR

       插入一个新节点到根节点的右子树的 右 子树,导致根节点的平衡因子由1变为2.需要 左 旋转来解决。

RL

       插入一个新节点到根节点的 右 子树的左子树,导致根节点的平衡因子由1变为2.需要先 右 旋后 左 旋转来解决。

总结

优点

       在最坏情况下仍有较好的性能。每个操作中处理每个结点的时间都不会超过一个很小的常数,且这两个操作都只会访问一条路径上的结点,所以任何查找或者插入的成本都肯定不会超过对数级别。
完美平衡的2-3树要平展的多。例如,含有10亿个结点的一颗2-3树的高度仅在19到30之间。我们最多只需要访问30个结点就能在10亿个键中进行任意查找和插入操作。

缺点

       我们需要维护两种不同类型的结点,查找和插入操作的实现需要大量的代码,而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。平衡一棵树的初衷是为了消除最坏情况,但我们希望这种保障所需的代码能够越少越好。

红黑树/RBT

       红黑树是一个更高效的检索二叉树,因此常常用来实现关联数组。典型地,JDK 提供的集合类 TreeMap 本身就是一个红黑树的实现。排序二叉树的深度直接影响了检索的性能,当插入节点本身就是由小到大排列时,排序二叉树将变成一个链表,这种排序二叉树的检索性能最低:N 个节点的二叉树深度就是 N-1。但是红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高,这样保证红黑树在最坏情况下都是高效的,不会出现普通排序二叉树的情况。
红黑树在原有的排序二叉树增加了如下几个要求:

性质 1:每个节点要么是红色,要么是黑色。

性质 2:根节点永远是黑色的。

性质 3:所有的叶节点都是空节点(即 nil),并且是黑色的。

性质 4:每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)。

性质 5:从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

       之前我们了解了二叉查找树的插入,接下来,咱们便来具体了解下红黑树的插入操作。红黑树的插入相当于在二叉查找树插入的基础上,为了重新恢复平衡,继续做了插入修复操作。
下面来看一下几个约定:

       (1)性质 3 中指定红黑树的每个叶子节点都是空节点,而且叶子节点都是黑色 Java 实现的红黑树将使用 null 来代表,因此遍历红黑树时将看不到黑色的叶子节点,反而看到每个叶子节点都是红色的。非叶子节点,也就是非null节点称为红黑树中的儿子节点。

       (2) 红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点,因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度”。

       对于给定的黑色高度为 N 的红黑树,从根到叶子节点的最短路径长度为 N-1,最长路径长度为 2 * (N-1)。

       假如有一棵黑色高度为 3 的红黑树:从根节点到叶节点的最短路径长度是 2,该路径上全是黑色节点(黑节点 - 黑节点 - 黑节点)。最长路径也只可能为 4,在每个黑色节点之间插入一个红色节点(黑节点 - 红节点 - 黑节点 - 红节点 - 黑节点),性质 4 保证绝不可能插入更多的红色节点。由此可见,红黑树中最长路径就是一条红黑交替的路径。

       红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。

B-Tree/平衡多路搜索树

       性质如下,图片显示M=3时的例子:

  1. 定义任意非叶子结点最多只有M个儿子;且M>2;
  2. 根结点的儿子数为[2, M];
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M];
  4. 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1;
  6. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
  7. 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
  8. 所有叶子结点位于同一层;

       B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;

B-树的特性:

  1. 关键字集合分布在整颗树中;
  2. 任何一个关键字出现且只出现在一个结点中;
  3. 搜索有可能在非叶子结点结束;
  4. 其搜索性能等价于在关键字全集内做一次二分查找;
  5. 自动层次控制;

       由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:

B+树

       B+树是B-树的变体,也是一种多路搜索树:

  1. 其定义基本与B-树同,除了:
  2. 非叶子结点的子树指针与关键字个数相同;
  3. 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
  4. 为所有叶子结点增加一个链指针;
  5. 所有关键字都在叶子结点出现;

       B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

B+的特性:

  1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
  2. 不可能在非叶子结点命中;
  3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
  4. 更适合文件索引系统;

       b+tree每层节点直接还有链表连接,增加局部和范围访问效率,尾部还有聚集和非聚集区别,这数据结构很适合存储引擎

坚持原创技术分享,您的支持将鼓励我继续创作!