1、非线性表之树-概述

  1. 1、树的概述：
  2.     1-1、树是由n(n>=1)个有限结点组成一个具有层次关系的集合，根节点在最上层，叶节点在下层。
  3.     1-2、树包含n(n>=1)个结点，(n-1)条边，除根结点之外的其余数据元素被分为个互不相交的集合，其中每一个集合本身也是一棵树，被称作原树的子树(subtree) ==> (树是由根结点和若干颗子树构成的。)
  4.     1-3、单个结点是一棵树，树根就是该结点本身、

1.1、树的特点

  1. 1、树的特点：
  2.     1-1、每个结点有零个或多个子节点。
  3.     1-2、没有父结点的结点称为根节点。
  4.     1-3、每个非根结点有且只有一个父结点。
  5.     1-4、除根节点外，每个子结点可以分为多个不相交的子树。

1.2、树的-相关术语-简介

  1. 1、树的术语：具体结合实例图：https://blog.csdn.net/weixin_41133154/article/details/80027285
  2.     1-1、空集合也是树，称为空树。空树中没有结点。
  3.     1-2、结点的度：一个结点含有的子结点的个数(节点的子树数目)。
  4.     1-3、树的度：选取所有结点中最大的度，就是树的度
  5.     1-4、叶子结点：结点的度为0的节点[没有子节点]，又称为终端节点。
  6.     1-5、分支结点：度大于0的结点为分支结点，显然除了叶子结点之外的结点都为分支结点
  7.     1-6、结点的层次/深度：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
  8.     1-7、节点高度：对任意节点x，叶子节点到x节点的路径长度就是节点x的高度
  9.     1-8、树的高度或深度：定义一棵树的根结点层次为1，其他结点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值。
  10.     1-9、树的路径长度：从树根到树中每一结点的路径长度之和。
  11.         1-9-1、在结点数目相同的二叉树中，完全二叉树的路径长度最短。
  12.     1-10、树的带权路径长度(Weighted Path Length of Tree，WPL)
  13.         1-10-1、结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。
  14.         1-10-2、结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
  15.         1-10-3、树的带权路径长度(WPL)：定义为树中所有叶结点的带权路径长度之和【权值*深度求和】
  16.     1-11、森林：由棵互不相交的树的集合称为森林；

1.2.1、三层树结构-示意图

image.png

1.3、树的-分类

  1. 4、树的种类：具体结合实例图：https://blog.csdn.net/u014532217/article/details/79118023
  2.     4-1、无序树：
  3.         4-1-1、树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;
  4.     4-2、有序树：
  5.         4-2-1、树中任意节点的子结点之间有顺序关系，这种树称为有序树；
  6.     4-3、二叉树：
  7.         4-3-1、每个节点最多含有两个子树的树称为二叉树；
  8.     4-4、满二叉树：
  9.         4-4-1、叶节点除外的所有节点均含有两个子树的树被称为满二叉树
  10.     4-5、完全二叉树：
  11.         4-5-1、有个节点的满二叉树称为完全二叉树
  12.     4-6、平衡二叉树(AVL)
  13.         4-6-1、它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树。
  14.     4-7、二叉查找树(二叉搜索树、Binary Search Tree,BST)
  15.         4-7-1、若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 
  16.         4-7-2、若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 
  17.         4-7-3、任意节点的左、右子树也分别为二叉查找树； 
  18.         4-7-4、没有键值相等的节点。
  19.     4-8、哈夫曼树(霍夫曼树、最优二叉树)：
  20.         4-8-1、带权路径最短的二叉树称为哈夫曼树或最优二叉树；
  21.     4-9、红黑树：是一颗特殊的二叉查找树，除了二叉查找树的要求外，其特性有：
  22.         4-9-1、每个节点或者是黑色，或者是红色。
  23.         4-9-2、根节点是黑色。
  24.         4-9-3、每个叶子节点(NIL)是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
  25.         4-9-4、如果一个节点是红色的，则它的子节点必须是黑色的。
  26.         4-9-5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
  28.     4-10、B-tree(B树/B-树)，一颗m阶B树的特性：
  29.         4-10-1、根结点至少有两个子女（如果B树只有一个根节点，这个根节点的key的数量可以为[1~m-1]）
  30.         4-10-2、每个非根节点所包含的关键字个数 j 满足：⌈m/2⌉ - 1 <= j <= m - 1，节点的值按非降序方式存放，即从左到右依次增加。
  31.         4-10-3、除根结点以及叶子节点以外的所有结点的度数正好是关键字总数加1，故内部节点的子树个数 k 满足：⌈m/2⌉ <= k <= m 
  32.         4-10-4、所有的叶子结点都位于同一层
  33.     4-11、B+树：是B-tree的变体，区别点有：
  34.         4-11-1、有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点，其中⌈m/2⌉ <= n <= m
  35.         4-11-2、所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
  36.         4-11-3、所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字
  37.         4-11-4、通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点
  38.     4-12、B*树：B+树的变体，除了B+树的要求之外，还有以下特性：
  39.         4-12-1、⌈m*2/3⌉ <= n <=m 这里的n是除根节点之外的内部节点的键
  40.         4-12-2、增加内部节点中兄弟节点的指针，由左边指向右边
  42.     4-13、2-3-4树
  43.         4-13-1、节点最多有4个子节点和3个数据项;叶节点同层;节点key值有序
  44.         4-13-2、在2-3树的基础上可以存储4-节点，4-节点由三个元素组成，有四个子树。
  45.     4-14、Trie树：字典树|前缀树|单词查找树
  46.         4-14-1、是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。
  47.     4-15、LSM树：日志结构合并树(Log-Structured Merge-Tree)
  48.         4-15-1、它并不属于一个具体的数据结构，它更多是一种数据结构的设计思想。大多NoSQL数据库核心思想都是基于LSM来做的，只是具体的实现不同。
  49.         4-15-2、LSM树由两个或以上的存储结构组成：
  50.             -- 一个存储结构常驻内存中，称为C0 tree；具体可以是任何方便健值查找的数据结构，比如红黑树、map之类，甚至可以是跳表。
  51.             -- 另外一个存储结构常驻在硬盘中，称为C1 tree；具体结构类似B树。C1所有节点都是100%满的，节点的大小为磁盘块大小。
  52.     4-16、哈希树：(hash tree|墨克树：Merkle tree)
  53.          4-16-1、每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签。
  54.         4-16-2、哈希树的顶部为顶部哈希(top hash)，亦称根哈希(root hash)或主哈希(master hash)。只要任一叶节点有变化，根哈希都会变。

1.4、树的表示方法

  1. 1、树的表示方法
  2.     1-1、图像表示法(常用)：
  3.     1-2、符号表示法：(1(2(5(9,10)),3(6,7).4(8)))
  4.         1-2-1、用括号先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，
  5.         1-2-2、而对子树也采用同样的方法处理；
  6.         1-2-3、同层子树与它的根结点用圆括号括起来，
  7.         1-2-4、同层子树之间用逗号隔开，
  8.         1-2-5、最后用闭括号括起来。
  9.     1-3、遍历表示法：
  10.         1-3-1、其先序遍历(又称先根遍历)为ABDECF(根-左-右)
  11.         1-3-2、其中序遍历(又称中根遍历)为DBEAFC(左-根-右)(仅二叉树有中序遍历)
  12.         1-3-3、其后序遍历(又称后根遍历)为DEBFCA(左-右-根)
  13.         1-3-4、其层次遍历为ABCDEF(同广度优先搜索）

1.4.1、树的表示方法-遍历表示法-树结构示意图

image.png

2、非线性表之二叉树

  1. 1、二叉树-概述：
  2.     1-1、每个节点最多含有两个子树的树称为二叉树。
  3.     1-2、每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)。
  4.     1-3、二叉树的子树有左右之分，其次序不能任意颠倒。
  6. 2、二叉树-性质:
  7.     2-1.若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个结点(i>=0)。
  8.     2-2.高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)(空树的高度为-1)。
  9.     2-3.对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。
  11. 3、二叉树-分类：
  12.     3-1、完美二叉树：除叶子结点之外的每一个结点都有两个子结点
  13.     3-2、完全二叉树：除最后一层之外的每一层都被完全填充，并且所有结点都保持向左对齐。
  14.     3-3、完满二叉树：除叶子结点之外的每个结点都有两个子结点。
  15.     3-4、完美二叉树(满二叉树)：除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。
  17. 4、二叉树-实现Demo:
  18.      private static class TreeNode {
  19.         int val;
  20.         TreeNode left;
  21.         TreeNode right;
  22.         TreeNode(int x) { val = x; }
  23.      }
  25. 5、二叉树遍历有三种方式: 看输出父节点的顺序。
  26.     5-1、总的方法：对于给定的二叉树根，寻找其左子树；对于其左子树的根，再去寻找其左子树；递归遍历，直到寻找最左边的节点i，其必然为叶子，然后遍历i的父节点，再遍历i的兄弟节点。随着递归的逐渐出栈，最终完成遍历。
  27.     5-2、先序遍历：先访问根节点，然后访问左节点，最后访问右节点(根->左->右)
  28.     5-3、中序遍历：先访问左节点，然后访问根节点，最后访问右节点(左->根->右)
  29.     5-4、后序遍历：先访问左节点，然后访问右节点，最后访问根节点(左->右->根)
  31. 6、Java中常见的树结构：
  32.     6-1、二叉查找树：也称为有序二叉查找树,满足二叉查找树的一般性质。
  33.     6-2、AVL树：是带有平衡条件的二叉查找树。
  34.     6-3、红黑树：一种自[!!!]平衡二叉查找树。
  36. 7、详细解析blog
  37.     7-1、https://www.jianshu.com/p/912357993486
  38.     7-2、https://blog.csdn.net/yj201711/article/details/84288826
  39.     7-3、https://blog.csdn.net/wannuoge4766/article/details/83998377
  41. 8、树进行调整的规则：需要旋转最小失衡子树 【!!!】
  42.     8-1、平衡因子[BF]：
  43.         -- 左子树的高度减去右子树的高度【节点的左右子树的高度差】。
  44.     8-2、最小失衡子树：
  45.         -- 在新插入的节点向上查找，以第一个平衡因子的绝对值超过1的节点为根的子树称为最小失衡子树。
  46.         -- 一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树[以绝对值相比较]，就能够将不平衡的树调整为平衡的树。

2.1、非线性表之二叉树-种类-结构图

image.png

2.2、二叉树之二叉查找树

  1. 1、二叉查找树-概述
  2.     1-1、二叉查找树是二叉树的衍生概念，(Binary Search Tree)，也称二叉搜索树，有序二叉树(ordered binary tree)，排序二叉树(sorted binary tree)
  3.     1-2、对于二叉排序树的任何一个非叶子节点，要求：左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
  5. 2、二叉查找树的性质如下：
  6.     2-1、若左子树不空，则左子树上所有结点的值均小于|等于它的根结点/父节点的值；
  7.     2-2、若右子树不空，则右子树上所有结点的值均大于|等于它的根结点/父节点的值；
  8.     2-3、左、右子树也分别为二叉排序树；
  9.     2-4、没有键值相等的结点。
  11. 3、二叉查找树-查找步骤
  12.     3-1、小于往左，大于往右，相等则查找成功，子树为空不成功
  14. 4、二叉查找树-优点：
  15.     4-1、优势在于查找、插入的时间复杂度较低为 O ( log ⁡ n )
  16.     4-2、二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。
  18. 5、二叉查找树-缺点：
  19.     5-1、当插入的数据，一个比一个大时，由于二叉查找树的特性，会使左节点树全部为空
  20.         5-1-1、比如：一个队列[1,2,3,4,5,6]，转成二叉查找树，则会左节点树全部为空，更像一个单链表，插入和删除效率没影响，但查询访问效率降低。
  21.             1->2->3->4->5->6

2.3、二叉树之平衡二叉树[AVL树]

  1. 1、平衡二叉树-概述
  2.     1-1、平衡二叉树又叫AVL树、平衡二叉搜索树。
  4. 2、平衡二叉树-性质如下：
  5.     2-1、它是一颗空树或者它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度(也指树的层次)之差的绝对值不超过1。
  6.         2-1-1、即：任何节点的两棵子树的高度最大差为1(|BF|<=1)；
  7.         2-1-2、平衡因子(BF)：BF=左子树深度—右子树深度。
  8.     2-2、每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值)；
  10. 3、平衡二叉树常用实现方法有：
  11.     3-1、红黑树、
  12.     3-2、AVL、
  13.     3-3、伸展树等。
  15. 4、二叉树平衡性调整：
  16.     4-1、在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。
  17.     4-2、树进行调整的规则：需要旋转最小失衡子树
  18.         4-2-1、平衡因子[BF]：
  19.             -- 左子树的高度减去右子树的高度【节点的左右子树的高度差】。
  20.         4-2-2、最小失衡子树：
  21.             -- 在新插入的节点向上查找，以第一个平衡因子的绝对值超过1的节点为根的子树称为最小失衡子树。
  22.             -- 一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。
  24.     4-3、主要是依靠旋转来实现的：分为4种类型
  25.         -- 左旋：BF< -1时，父节点变为该节点的左节点
  26.         -- 右旋：BF> 1时，父节点变为该节点的右节点
  27.         4-3-1、LL型(左左旋)、
  28.         4-3-2、RR型(右右旋)、
  29.         4-3-3、LR型(左右旋)、
  30.         4-3-4、RL型(右左旋)、

2.4、二叉树之红黑树

  1. 1、红黑树-概述：
  2.     1-1、红黑树是一种特殊的平衡二叉树，
  3.     1-2、确保从根到叶子节点的最长路径不会是最短路径的两倍。
  4.     1-3、用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决。
  5.     1-4、红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
  7. 2、红黑树-性质有：
  8.     2-1、每个结点要么是红色或黑色。
  9.     2-2、根节点是黑色。
  10.     2-3、每个叶节点（叶结点即指树尾端NIL指针或NULL结点）是黑色的。[NIL节点就是说这个节点不存在,想象的]
  11.     2-4、每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  12.     2-5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。[对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。]
  14. 3、红黑树-注意点：
  15.     3-1、黑色节点的父节点\子节点\兄弟节点既可以是黑色的,也可以是红色的;(红色节点的限制比较多)
  16.     3-2、一棵树可以全是黑色的;(这种情况就是一颗满二叉树)
  17.     3-3、在一棵树的所有路径中,最长的路径一定是红色节点最多的那条,最短的路径一定是红色节点最少的那条;(因为每条路径上的黑色节点数量一样呀)
  18.     3-4、自平衡的方式无外乎三种:左旋\右旋\变色。
  20. 4、红黑树-平衡化旋转：
  21.     4-1、单旋转：左旋转、右旋转、
  22.     4-2、双旋转：先左再右旋转、先右再左旋转、
  24. 5、红黑树-旋转原则：
  25.     5-1、在忽略颜色的前提下，可以看到旋转操作不会影响旋转结点的父结点，父结点以上的结构还是保持不变的。
  26.     5-2、左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了
  27.     5-3、右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
  29. 6、左旋转步骤：把新节点的左子节点树设置当前节点的左子节点树
  30.     6-1、创建一个新节点，值为当前根节点的值。
  31.     6-2、把新节点的左子节点树设置当前节点的左子节点树。
  32.     6-3、把新节点的右子节点树设置当前节点的右子节点树的左子节点树。
  33.     6-4、把当前节点的值换为右子节点的值。
  34.     6-5、把当前节点的右子节点树设置当前节点的右子节点树的右子节点树。
  35.     6-6、把当前节点的左节点树设置成新的节点。
  37. 7、旋转过程-伪代码
  38.     7-1、左旋-伪代码
  39.         LEFT-ROTATE(T, x)  
  40.          y ← right[x]            // 前提：这里假设x的右孩子为y。下面开始正式操作
  41.          right[x] ← left[y]      // 将 "y的左孩子" 设为 "x的右孩子"
  42.          p[left[y]] ← x          // 将 "x" 设为 "y的左孩子的父亲"
  43.          p[y] ← p[x]             // 将 "x的父亲" 设为 "y的父亲"
  44.          if p[x] = nil[T]       
  45.          then root[T] ← y                 // 情况1：如果 "x的父亲" 是空节点，则将y设为根节点
  46.          else if x = left[p[x]]  
  47.                    then left[p[x]] ← y    // 情况2：如果 x是它父节点的左孩子，则将y设为"x的父节点的左孩子"
  48.                    else right[p[x]] ← y   // 情况3：(x是它父节点的右孩子) 将y设为"x的父节点的右孩子"
  49.          left[y] ← x             // 将 "x" 设为 "y的左孩子"
  50.          p[x] ← y                // 将 "x的父节点" 设为 "y"
  52.      7-2、右旋-伪代码
  53.          RIGHT-ROTATE(T, y)  
  54.          x ← left[y]             // 前提：这里假设y的左孩子为x。下面开始正式操作
  55.          left[y] ← right[x]      // 将 "x的右孩子" 设为 "y的左孩子"
  56.          p[right[x]] ← y         // 将 "y" 设为 "x的右孩子的父亲"
  57.          p[x] ← p[y]             // 将 "y的父亲" 设为 "x的父亲"
  58.          if p[y] = nil[T]       
  59.          then root[T] ← x                 // 情况1：如果 "y的父亲" 是空结点，则将x设为根结点
  60.          else if y = right[p[y]]  
  61.                    then right[p[y]] ← x   // 情况2：如果 y是它父结点的右孩子，则将x设为"y的父结点的左孩子"
  62.                    else left[p[y]] ← x    // 情况3：(y是它父结点的左孩子) 将x设为"y的父结点的左孩子"
  63.          right[x] ← y            // 将 "y" 设为 "x的右孩子"
  64.          p[y] ← x                // 将 "y的父结点" 设为 "x"
  66. 8、红黑树-学习资料
  67.     [https://blog.csdn.net/weixin_42603382/article/details/109557980]
  68.     [https://www.cnblogs.com/nananana/p/10434549.html]

2.4.1、红黑树的左旋转(以S为旋转点)-动态示意图

非线性结构-树 - 图5

2.4.2、红黑树的右旋转(以E为旋转点)-动态示意图

非线性结构-树 - 图6

2.4.3、红黑树的左旋转(以P为旋转点)-静态示意图

非线性结构-树 - 图7

2.4.4、红黑树的右旋转(以P为旋转点)-静态示意图

非线性结构-树 - 图8

2.3.5、二叉树之红黑树-操作-查找

  1. 1、红黑树-查找步骤：
  2.     1-1、红黑树-查找步骤：
  3.         1-1-1、查找根节点,将根节点设为当前节点;
  4.         1-1-2、如果当前节点为空,返回null;
  5.         1-1-3、如果当前节点不为空,比较key是否相等,如果相等则返回对应的值;
  6.         1-1-4、如果当前节点大于要查找的节点,那么将当前节点的左子节点设为当前节点,然后从步骤2开始重新执行;
  7.         1-1-5、如果当前节点小,那么将当前节点的右子节点设为当前节点,然后从步骤2开始重新执行.
  9.        1-2、红黑树-查找步骤-注意点：
  10.         1-2-1. 这是个递归,退出条件在步骤2或步骤3;
  11.         1-2-2. 当这棵树是空树或不存在对应的key时都会返回null。
  13. 2、

2.3.6、二叉树之红黑树-操作-添加/插入

  1. 1、添加/插入-步骤：
  2.     1-1、查找插入节点的父节点
  3.     1-2、插入节点并自平衡。
  5. 2、添加/插入-算法：
  6.     2-1、添加/插入：
  7.         RB-INSERT(T, z)  
  8.          y ← nil[T]                        // 新建结点“y”，将y设为空结点。
  9.          x ← root[T]                       // 设“红黑树T”的根结点为“x”
  10.          while x ≠ nil[T]                  // 找出要插入的结点“z”在二叉树T中的位置（父结点），即“y”结点要存放的位置
  11.              do y ← x                      
  12.                 if key[z] < key[x]  
  13.                    then x ← left[x]  
  14.                    else x ← right[x]  
  15.          p[z] ← y                          // 设置 “z的父亲” 为 “y”
  16.          if y = nil[T]                     
  17.             then root[T] ← z               // 情景1：若y是空结点，则将z设为根结点
  18.             else if key[z] < key[y]        
  19.                     then left[y] ← z       // 情景2：若“z的key值” < “y的key值”，则将z设为“y的左孩子”
  20.                     else right[y] ← z      // 情景2：若“z的key值” >= “y的key值”，则将z设为“y的右孩子” 
  21.          left[z] ← nil[T]                  // z的左孩子设为空
  22.          right[z] ← nil[T]                 // z的右孩子设为空。至此，已经完成将“结点z插入到二叉树”中了。
  23.          color[z] ← RED                    // 将z着色为“红色”
  24.          RB-INSERT-FIXUP(T, z)             // 通过RB-INSERT-FIXUP对红黑树的结点进行颜色修改以及旋转，让树T仍然是一颗红黑树
  26.     2-2、添加/插入-修正算法：
  27.         RB-INSERT-FIXUP(T, z)
  28.          while color[p[z]] = RED                                            // 若“当前结点(z)的父结点是红色”，则进行以下处理。
  29.             do if p[z] = left[p[p[z]]]                                      // 若“z的父结点”是“z的祖父结点的左孩子”，则进行以下处理。
  30.                   then y ← right[p[p[z]]]                                   // 将y设置为“z的叔叔结点(z的祖父结点的右孩子)”
  31.                     if color[y] = RED                                       // 4.1情景：叔叔是红色
  32.                       then color[p[z]] ← BLACK                              //  (01) 将“父结点”设为黑色。
  33.                            color[y] ← BLACK                                 //  (02) 将“叔叔结点”设为黑色。
  34.                            color[p[p[z]]] ← RED                             //  (03) 将“祖父结点”设为“红色”。
  35.                            z ← p[p[z]]                                      //  (04) 将“祖父结点”设为“当前结点”(红色结点)
  36.                       else if z = right[p[z]]                               // 4.3.1情景：叔叔是黑色，且当前结点是右孩子
  37.                             then z ← p[z]                                   //  (01) 将“父结点”作为“新的当前结点”。
  38.                                 LEFT-ROTATE(T, z)                           //  (02) 以“新的当前结点”为支点进行左旋。
  39.                             color[p[z]] ← BLACK                             // 4.2.1情景：叔叔是黑色，且当前结点是左孩子。(01) 将“父结点”设为“黑色”。
  40.                             color[p[p[z]]] ← RED                            //  (02) 将“祖父结点”设为“红色”。
  41.                             RIGHT-ROTATE(T, p[p[z]])                        //  (03) 以“祖父结点”为支点进行右旋。
  42.                else (same as then clause with "right" and "left" exchanged) // 若“z的父结点”是“z的祖父结点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。
  43.          color[root[T]] ← BLACK                                             // 情景1：若y是空结点，则将z设为根结点
  45. 3、添加/插入-情况分析：
  46.     3-1、情况1-红黑树为空树：把插入结点作为根结点，并把结点设置为黑色。
  47.     3-2、情况2-插入结点的Key已存在：把z设为当前结点的颜色。更新当前结点的值为插入结点的值。
  48.     3-3、情况3-插入结点的父结点为黑结点：由于插入的结点是红色的，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。
  49.     3-4、情况4-插入结点的父结点为红结点：如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。
  50.     3-5、情况5-叔叔结点存在并且为红结点：祖父结点为黑结点，因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。

2.3.6.1、二叉树之红黑树-操作-添加/插入-自平衡脑图

非线性结构-树 - 图9

2.5、二叉树之最优二叉树

  1. 最优二叉树：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈/赫/霍夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
  2. 最优二叉树应用：
  3. 1、数据压缩、解压
  4. 将赫夫曼编码表存放在 Map<Byte,String> 形式，生成的赫夫曼编码表。
  5. 2、其他：https://blog.csdn.net/luo1454925298/article/details/106134198

2.6、非线性表之多叉树

  1. 1、B树：平衡多路查找树，
  2.     1-1、多路查找树（muitl-way search tree），其每一个结点的孩子数可以多于两个，且每个结点出可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
  3.      1-2、B-tree树即B树，B即Balanced,B-tree就是指的B树
  5. 2、树之B-树
  6.     2-1、B-树 中所有结点中孩子结点个数的最大值成为B-树的阶，通常用m表示
  7.     2-2、一棵m阶B-树或者是一棵空树，或者是满足以下条件的m叉树：
  8.         2-2-1、每个结点最多有m个分支（子树）；而最少分支数要看是否为根结点，如果是根结点且不是叶子结点，则至少要有两个分支，非根非叶结点至少有ceil(m/2)个分支，这里ceil代表向上取整。
  9.         2-2-2、如果一个结点有n-1个关键字，那么该结点有n个分支。这n-1个关键字按照递增顺序排列。
  10.            2-2-3、每个节点的结构为:节点个数：n；
  11.         2-2-4、每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
  13. 3、树之B+树
  14.     3-1、在B+树中，具有n个关键字的结点有n个分支，而在B-树中，具有n个关键字的结点含有n+1个关键字。
  15.     3-2、在B+树中，每个结点（除根结点外）中的关键字个数n的取值为ceil(m/2) <= n <=m,根结点的取值范围为1<=n<=m，b树他们的取值范围分别是ceil(m/2) -1<= n <=m-1和1<=n<=m-1。
  16.     3-3、3-1、在B+树中叶子结点包含信息，并且包含了全部关键字，叶子结点引出的指针指向记录。
  17.     3-4、在B+树中的所有非叶子结点仅起到一个索引的作用，即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针。
  19. 4、树之B*树
  20.     4-1、是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针(链表指针)；

2.6.1、树之B树

  1. 1、B树(B-tree)-概念
  2.     1-1、B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个)。
  4. 2、B树(B-tree)-规则
  5.     2-1、排序方式：
  6.           2-1-1、所有节点关键字是按递增次序排列，并遵循左小右大原则；
  7.       2-2、子节点数：
  8.           2-2-1、非叶节点的子节点数>1，且<=M ，且M>=2，空树除外。
  9.             -- 注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉；
  10.       2-3、关键字数：
  11.         2-3-1、枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个
  12.             -- 注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2;
  13.             -- < ceil(m/2)-1，则需要进行节点合并；比如：节点的删除
  14.             -- > M-1，则需要进行节点拆分；比如：节点插入
  15.     2-4、所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外，也有指向其子节点的指针，只不过其指针地址都为null，对应下图最后一层节点的空格子;

2.6.2、树之B树-查询流程-举例说明

  1. 1、B树-查询流程
  2.     1-1、从举例示意图中寻找E字母，查找流程，如下：
  3.         -- 获取根节点的关键字进行比较，当前根节点关键字为M，E<M(26个字母顺序)，所以往找到指向左边的子节点[二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点]；
  4.         -- 拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
  5.         -- 拿到E和F，因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null)；

2.6.2.1、举例示意图[直接用实际字母的大小来排列C>B>A]

非线性结构-树 - 图10

2.6.3、树之B树-插入流程-举例说明

  1. 1、B树-插入流程
  2.     1-1、需求：
  3.         1-1-1、要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;
  4.     1-2、分析：
  5.         1-2-1、节点拆分规则：
  6.             -- 当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）
  7.         1-2-2、排序规则：
  8.             -- 满足节点本身比左边节点大，比右边节点小的排序规则;
  9.     1-3、插入操作
  10.         1-3-1、先插入 3、8、31、11
  11.         1-3-2、再插入23、29
  12.         1-3-3、再插入50、28

2.6.3、树之B+树

  1. 1、B+树-概述
  2.     1-1、B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
  3.     1-2、B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到[叶子节点才会存储数据]。
  4.     1-3、B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
  5.     1-4、B+树初始化的关键字初始化非叶子节点个数是cei(m/2)；
  6.         -- 叶子结点：结点的度为0的节点[没有子节点]，又称为终端节点。

2.6.4、树之B*树

  1. 1、B*树-概述
  2.     1-1、B*树是B+树的变种，相对于B+树他们的不同之处：
  3.         1-1-1、B+树初始化的关键字初始化非叶子节点个数是cei(m/2)，b*树的初始化非叶子节点个数为(cei(2/3m))
  4.         1-1-2、在B+树的非根结点和非叶子结点增加指向兄弟的指针；
  5.         1-1-3、B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满：
  6.             -- 如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来。

2.6.5、B+树与B*树的区别

  1. 1、B+树与B*树的区别：
  2.     1-1、B*树分配新结点的概率比B+树要低，空间使用率更高。
  3.         1-1-1、B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
  4.         1-1-2、当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了)；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

2.7、树-哈希树

  1. 1、哈希树[Hash Tree]-概述
  2.     1-1、是一种持久性数据结构，可用于实现集合和映射，旨在替换纯函数式编程中的哈希表。
  3.     1-2、又称墨克树[Merkle tree]，
  4.     1-3、每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 
  5.     1-4、哈希树不支持排序，没有顺序特性。
  6.     1-5、哈希树是一个单向增加的结构，即随着所需要存储的数据量增加而增大。即使数据量减少到原来的数量，但是哈希树的总节点数不会减少。

2.7.1、哈希树的理论基础

  1. 1、质数分辨定理
  2.     1-1、质数：即只能被 1 和 本身 整除的数。
  3.     1-2、n个不同的质数可以** 分辨 **的连续整数的个数和他们的乘积相等。** 分辨 **就是指这些连续的整数不可能有完全相同的余数序列。
  4.     1-3、同一节点中的子节点，从左到右代表不同的余数结果，同一节点中的子节点，从左到右代表不同的余数结果。
  5.     1-4、举例：
  6.         1-4-1、对于一个质数x，它的mod有[ 0 .. x - 1 ] x种；所以对于两个质数x和y，能存储的无一重复的数据有 x*y 个，其实也就是开一个x*y的二维数组。但是当数据极其多时，用两个质数去mod显然也是有不够的时候，就还要再加一个。为了便于查找，选取最小的十个质数，也就是2，3，5，7，11，13，17，23，29，31来mod，能包括的数就有10555815270个，已经远超出longint了。

2.7.2、哈希树-构建

  1. 1、哈希树-构建
  2.     1-1、质数分辨算法来建立一棵哈希树
  3.         1-1-1、选择从2开始的连续质数来建立一个十层的哈希树。
  4.             -- 第一层结点为根结点，根结点下有2个结点；第二层的每个结点下有3个结点；依此类推，即每层结点的子节点数目为连续的质数。到第十层，每个结点下有29个结点。
  5.         1-1-2、同一结点中的子结点，从左到右代表不同的余数结果。
  6.             -- 例如：第二层结点下有三个子节点。那么从左到右分别代表：除3余0，除3余1，除3余2.对质数进行取余操作得到的余数决定了处理的路径。
  7.         1-1-3、结点结构：结点的关键字(在整个树中是唯一的)，结点的数据对象，结点是否被占据的标志位(标志位为真时，关键字才被认为是有效的)，和结点的子结点数组。

2.8、树-Trie[traɪ]树

  1. 1、树-Trie[traɪ]树-概述
  2.     1-1、是一种有序树，用于保存关联数组，其中的键通常是字符串。
  3.     1-2、键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。
  4.     1-3、键通常是字符串，但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。
  5.     1-4、它有很多变种，如后缀树，Radix Tree/Trie，PATRICIA tree，以及bitwise版本的crit-bit tree。
  6.     1-5、trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针

2.8.1、树-Trie[traɪ]树-基本性质

  1. 1、树-Trie[traɪ]树-基本性质
  2.     1-1、根节点不包含字符，除根节点以外，每个节点只包含一个字符。
  3.     1-2、从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。 
  4.     1-3、每个节点的所有子节点包含的字符串不相同。

2.8.2、树-Trie[traɪ]树-应用场景

  1. 1、字符串检索：
  2.     1-1、事先将已知的一些字符串(字典)的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。
  3.     1-2、举例
  4.         -- 给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
  5.         -- 给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。
  6.         -- 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。
  8. 2、文本预测、自动完成，词典(see also[si: ˈɔ:lsəu] )，拼写检查
  10. 3、词频统计
  11.     3-1、举例：
  12.         -- 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
  14. 4、排序
  15.     4-1、Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。
  16.     4-2、举例：
  17.         -- 给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。
  19. 5、字符串搜索的前缀匹配
  20.     5-1、trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。
  21.     5-2、Trie树检索的时间复杂度可以做到n，n是要检索单词的长度，

2.9、树-LSM树

  1. 1、LSM树-概述
  2.     1-1、日志结构合并树(Log-Structured Merge-Tree)
  3.     1-2、它并不属于一个具体的数据结构，它更多是一种数据结构的设计思想。大多NoSQL数据库核心思想都是基于LSM来做的，只是具体的实现不同。
  5. 2、树-LSM树-原理
  6.     2-1、把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。
  7.     2-2、LSM树由两个或以上的存储结构组成：
  8.         2-2-1、一个存储结构常驻内存中，称为C0 tree，具体可以是任何方便健值查找的数据结构，比如红黑树、map之类，甚至可以是跳表。
  9.         2-2-2、另外一个存储结构常驻在硬盘中，称为C1 tree，具体结构类似B树。C1所有节点都是100%满的，节点的大小为磁盘块大小。
  11. 3、LSM树-应用
  12.     3-1、它其实是一种存储结构，目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。

2.9.1、LSM树-组成部分

  1. 1、LSM树有以下三个重要组成部分：
  2.     1-1、MemTable：
  3.         1-1-1、在内存中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据。
  4.         1-1-2、LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义；例如Hbase使跳跃表来保证内存中key的有序。
  5.         1-1-3、数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过WAL(Write-ahead logging，预写式日志)的方式来保证数据的可靠性。
  6.     1-2、Immutable MemTable
  7.         1-2-1、当 MemTable达到一定大小后，会转化成Immutable MemTable。
  8.         1-2-2、Immutable MemTable是将转MemTable变为SSTable的一种中间状态。
  9.         1-2-3、写操作由新的MemTable处理，在转存过程中不阻塞数据更新操作。
  10.     1-3、SSTable(Sorted String Table)
  11.         1-3-1、有序键值对集合，是LSM树组在磁盘中的数据结构。
  12.         1-3-2、为了加快SSTable的读取，可以通过建立key的索引以及布隆过滤器来加快key的查找。

2.9.2、LSM树-操作

  1. 1、插入操作
  2.     1-1、插入一条新纪录时，首先在日志文件中插入操作日志，以便后面恢复使用，日志是以append形式插入。
  3.     1-2、将新纪录的索引插入到C0中，这里在内存中完成，不涉及磁盘IO操作；
  4.     1-3、当C0大小达到某一阈值时或者每隔一段时间，将C0中记录滚动合并到磁盘C1中；
  5.     1-4、对于多个存储结构的情况，当C1体量越来越大就向C2合并，以此类推，一直往上合并Ck。
  7. 2、合并操作：合并过程中会使用两个块：emptying block和filling block。
  8.     2-1、从C1中读取未合并叶子节点，放置内存中的emptying block中。
  9.     2-2、从小到大找C0中的节点，与emptying block进行合并排序，合并结果保存到filling block中，并将C0对应的节点删除。
  10.     2-3、不断执行第2步操作，合并排序结果不断填入filling block中，当其满了则将其追加到磁盘的新位置上；        2-3-1、注意：是追加而不是改变原来的节点。
  11.     2-4、合并期间如果emptying block使用完了则再从C1中读取未合并的叶子节点。
  12.     2-5、C0和C1所有叶子节点都按以上合并完成后即完成一次合并。

2.10、树-R树

  1. 1、树-R树[R tree]-概述
  2.     1-1、R树是B树在高维空间的扩展，是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。
  3.     1-2、R树是用来做空间数据存储的树状数据结构。例如: 给地理位置，矩形和多边形这类多维数据建立索引。
  4.     1-3、R树表示由二维或者更高维区域组成的数据，我们把它们称为数据区。一个R树的内结点对应于某个内部区域，或称"区域"，它不是普通的数据区。【区域可以是任意形状】

99、深度优先搜索与广度优先搜索-简介

  1. 1、深度优先搜索(DFS)与广度优先搜索(BFS)
  2.     1-1、深度优先搜索，(Depth First Search), 针对图和树的遍历算法，可以产生目标图的相应拓扑排序表，一般用堆数据结构来辅助实现DFS算法。
  3.     1-2、广度优先搜索，又称宽度优先搜索，属于一种盲目搜寻法，并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
  5. 2、两者过程：
  6.     2-1、深度优先搜索，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
  7.     2-2、广度优先搜索，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。
  9. 3、两者实现：
  10.     3-1、dfs=栈，压栈，出栈 一次访问多条路径。
  11.     3-2、bfs＝队列，入队列，出队列 一次访问一条路径；
  13. 4、两者关系：
  14.     4-1、用DFS解决的问题都可以用BFS解决。DFS易于编写(递归)，时间消耗较少但是容易发生爆栈，而BFS可以控制队列的长度。
  16. 5、两者-具体基本步奏：    
  17.     5-1、https://www.jianshu.com/p/bff70b786bb6