二叉树

基本的概念问题：

  1. 二叉树：是指一个树节点最多有两个与之相连的节点（例如图1所示）
  2. 二叉排列树：一个节点的左侧叶子点数都小于该节点，右侧叶子节点都大于该节点（如图2所示）
  3. 满二叉树：所有的叶子结点都是在最后一层，其中节点的总数为(2^n-1)。（如图2所示）
  4. 完全二叉树：是指二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点左连续，倒数第二层的叶子结点右连续。（如图3所示）
  5. 第n层的最大节点数量为：2^(n-1)
    image-20201101111226684.png

    二叉树的遍历

    二叉树的遍历根据父节点的遍历顺序分为：前序遍历、中序遍历、后序遍历
  • 前序遍历：首先遍历父节点，然后在遍历左子树、右叶子树
  • 中序遍历：首先遍历左子树，父节点、遍历右子树
  • 后序遍历：首先遍历左子树、右子树，最后是父节点
  1. public class TreeNode {
  2.     public int value;
  3.     public TreeNode leftNode;
  4.     public TreeNode rightNode;
  6.     public TreeNode(int value) {
  7.         this.value = value;
  8.     }
  10.     @Override
  11.     public String toString() {
  12.         return "TreeNode [value=" + value + "]";
  13.     }
  15.     // 前序遍历
  16.     public void preOrder() {
  17.         System.out.println(this.value);
  18.         if(this.leftNode != null) {
  19.             this.leftNode.preOrder();
  20.         }
  22.         if(this.rightNode != null) {
  23.             this.rightNode.preOrder();
  24.         }
  25.     }
  27.     //中序遍历
  28.     public void midOrder() {
  29.         if(this.leftNode != null) {
  30.             this.leftNode.midOrder();
  31.         }
  33.         System.out.println(this.value);
  35.         if(this.rightNode != null) {
  36.             this.rightNode.midOrder();
  37.         }
  38.     }
  40.     // 后序遍历
  41.     public void lastOrder() {
  42.         if(this.leftNode != null) {
  43.             this.leftNode.lastOrder();
  44.         }
  46.         if(this.rightNode != null) {
  47.             this.rightNode.lastOrder();
  48.         }
  50.         System.out.println(this.value);
  51.     }
  53. }

二叉树的查找：

前序查找

思路：

  1. 首先判断当前节点的value是否为要找的内容。如果相等，返回当前节点
  2. 如果不等，则判断当前节点的左子节点是否为空，如果不为空，则进行左递归查找。
  3. 如果左递归中没有找到节点，则继续判断右节点是否为空，如果不为空，则执行右递归查找，如果找到，则返回节点。

  4. 如果右递归没有找到节点，则返回为空

    1. public TreeNode preOrderSearch(int value) {
    2.  if(this.value == value) {
    3.      return this;
    4.  }
    5.  TreeNode result = null;
    6.  if(this.leftNode != null) {
    7.      result = this.leftNode.preOrderSearch(value);
    8.  }
    9.  if(result != null) {
    10.      return result;
    11.  }
    13.  if(this.rightNode != null) {
    14.      result = this.rightNode.preOrderSearch(value);
    15.  }
    16.  return result;
    17. }

中序查找：

  1. 首先判断当前的左子节点是否为空，如果不为空，则左递归中序查找
  2. 如果左递归找到节点，则返回；如果没有找到，就和当前节点进行比较，如果相等，则返回当前节点；如果不相等，则需要右递归中序查找
  3. 如果右递归中序查找找到节点，则返回该节点，如果没有找到，则返回空
  1. //中序查找
  2. public TreeNode midOrderSearch(int value) {
  3.     TreeNode res = null;
  4.     if(this.leftNode != null) {
  5.         res = this.leftNode.midOrderSearch(value);
  6.     }
  8.     if(res != null) {
  9.         return res;
  10.     }
  11.     if(this.value == value) {
  12.         return this;
  13.     }
  14.     if(this.rightNode != null) {
  15.         res = this.rightNode.midOrderSearch(value);
  16.     }
  17.     return res;
  18. }

后序查找

  1. 首先判断左子节点是否为空，如果不为空，进行左递归的后序查找，如果找到，则返回该节点
  2. 如果左子节点为空或没有找到，则判断右子节点是否为空，如果不为空，则执行右递归的后序查找，如果找到节点就返回

  3. 如果右递归没有找到节点，就与当前节点进行比较，如果相等则返回当前节点；如果不相等，则返回为空。

    1. //后序查找
    2. public TreeNode lastOrderSearch(int value) {
    3.  TreeNode res = null;
    4.  if(this.leftNode != null) {
    5.      res = this.leftNode.lastOrderSearch(value);
    6.  }
    7.  if(res != null) return res;
    9.  if(this.rightNode != null) {
    10.      res = this.rightNode.lastOrderSearch(value);
    11.  }
    13.  if(res != null) return res;
    15.  if(this.value == value) return this;
    17.  return null;
    18. }

删除树节点

规定：

  1. 如果删除的是叶子结点，则删除该节点
  2. 如果删除的是非叶子结点，则删除该树

思路：因为我们的二叉树是单向的，所以删除的时候不能到达该节点时在判断

  1. 删除时，首先判断该节点是否空，如果为空，直接返回。然后再判断是否为要删除的节点，如果是，则将root节点置空，并且返回。
  2. 如果删除的不是root节点，则判断左子节点是否为空。如果不为空，则递归左子节点
  3. 如果在左子节点中没有删除的节点，则继续递归右子节点。

顺序存储二叉树

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换为树，树也可以转换为数组。
image-20201108103931554 - 副本.png

要求：

  1. 二叉树节点以数组的形式进行存放
  2. 要求在遍历数组的时候，仍然可以以前序遍历、中序遍历和后序遍历的方式完成节点的遍历。

顺序二叉树的特点：

  1. 顺序二叉树通常只考虑完全二叉树
  2. 第n个元素的左子节点为 2*n + 1 （在数组中的位置）
  3. 第n个元素的右子节点为 2*n + 2 （在数组中的位置）
  4. 第n个元素的父节点为 (n-1)/2 （在数组中的位置）

n表示二叉树中第n个元素（从0开始）
具体的代码实现为：

  1. import java.util.Arrays;
  2. public class ArrBinaryTreeDemo {
  3.     public static void main(String[] args) {
  4.         // TODO Auto-generated method stub
  5.         int[] arr = {1, 2, 3, 4, 5 , 6, 7};
  6.         ArrBinaryTree tree = new ArrBinaryTree(arr);
  8.         System.out.println("打印原始数组：" + Arrays.toString(arr));
  9.         System.out.println("前序遍历：");
  10.         tree.preOrder(0);
  11.         System.out.println("中序遍历：");
  12.         tree.midOrder(0);
  13.         System.out.println("后序遍历：");
  14.         tree.lastOrder(0);
  15.     }
  16. }
  18. class ArrBinaryTree {
  19.     public int[] arr;
  20.     public ArrBinaryTree(int[] arr) {
  21.         // TODO Auto-generated constructor stub
  22.         this.arr = arr;
  23.     }
  25.     //进行前序遍历
  26.     public void preOrder(int index) {
  27.         if(arr == null || index < 0 ) {
  28.             System.out.println("输入的参数有问题");
  29.             return;
  30.         }
  31.         if(index >= arr.length) return;
  33.         System.out.println(arr[index]);
  34.         // 遍历左子树
  35.         preOrder(2 * index + 1);
  36.         // 遍历右子树
  37.         preOrder(2 * index + 2);
  38.     }
  40.     // 中序遍历
  41.     public void midOrder(int index) {
  42.         if(arr == null || index < 0 ) {
  43.             System.out.println("输入的参数有问题");
  44.             return;
  45.         }
  46.         if(index >= arr.length) return;
  48.         // 遍历左子树
  49.         midOrder(2 * index + 1);
  50.         System.out.println(arr[index]);
  51.         // 遍历右子树
  52.         midOrder(2 * index + 2);
  53.     }
  55.     // 后序遍历
  56.     public void lastOrder(int index) {
  57.         if(arr == null || index < 0 ) {
  58.             System.out.println("输入的参数有问题");
  59.             return;
  60.         }
  61.         if(index >= arr.length) return;
  62.         // 遍历左子树
  63.         lastOrder(2 * index + 1);
  64.         // 遍历右子树
  65.         lastOrder(2 * index + 2);
  66.         System.out.println(arr[index]);
  67.     }
  68. }

线索二叉树

基本的概念：

  1. n个节点的二叉链表中含有n+1（2n-(n-1)）个空指针域，利用二叉链表中的指针域，存放指向该节点在某种遍历次序下的前驱和后继节点的指针。这种附加的指针被称之为“线索”。
  2. 这种加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。根据线索的性质不同，线索二叉树可以分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
  3. 一个节点的前一个节点，称之为前驱节点
  4. 一个节点的后一个节点，称之为后继节点
  5. 线索二叉树后，Node的left节点与right节点有可能指向子树或者指向前驱与后继节点。需要在节点中添加标记，标记left指向左子树或前驱。

    平衡二叉树（AVL）

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树。

二叉查找树（二叉搜索树、BST）

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

霍夫曼树

带权路径最短的二叉树称为哈夫曼树或最优二叉树。
当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。

红黑树

红黑树是一颗特殊的二叉查找树，除了二叉查找树的要求外，它还具有以下特性：

  • 每个节点或者是黑色，或者是红色。
  • 根节点是黑色。
  • 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
  • 如果一个节点是红色的，则它的子节点必须是黑色的。
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

image.png

旋转

前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。

  • 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
  • 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
  • 变色：结点的颜色由红变黑或由黑变红。

查找

因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：

  1. 从根结点开始查找，把根结点设置为当前结点；
  2. 若当前结点为空，返回null；
  3. 若当前结点不为空，用当前结点的key跟查找key作比较；
  4. 若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；
  5. 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；
  6. 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；

2392382-07b47eb3722981e6.png

插入

插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。查找插入的父结点很简单，跟查找操作区别不大：

  1. 从根结点开始查找；
  2. 若根结点为空，那么插入结点作为根结点，结束。
  3. 若根结点不为空，那么把根结点作为当前结点；
  4. 若当前结点为null，返回当前结点的父结点，结束。
  5. 若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点的值，结束。
  6. 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；
  7. 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；

2392382-7521866b50683a24.png

删除

红黑树的删除操作也包括两部分工作：一查找目标结点；而删除后自平衡。查找目标结点显然可以复用查找操作，当不存在目标结点时，忽略本次操作；当存在目标结点时，删除后就得做自平衡处理了。删除了结点后我们还需要找结点来替代删除结点的位置，不然子树跟父辈结点断开了，除非删除结点刚好没子结点，那么就不需要替代。

二叉树删除结点找替代结点有3种情情景：

  • 情景1：若删除结点无子结点，直接删除
  • 情景2：若删除结点只有一个子结点，用子结点替换删除结点
  • 情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点

B-tree（B-树或者B树）

B树也称B-树,它是一颗多路平衡查找树。二叉树我想大家都不陌生，其实，B树和后面讲到的B+树也是从最简单的二叉树变换而来的，并没有什么神秘的地方，下面我们来看看B树的定义。

  • 每个节点最多有m-1个关键字（可以存有的键值对）。每个节点最多有m个子树。
  • 根节点最少可以只有1个关键字。
  • 非根节点至少有m/2个关键字。
  • 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
  • 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
  • 每个节点都存有索引和数据，也就是对应的key和value。

所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1。
另外，我们需要注意一个概念，描述一颗B树时需要指定它的阶数，阶数表示了一个节点最多有多少个孩子节点，一般用字母m表示阶数。
image-20210328144027517.png

插入

插入的时候，我们需要记住一个规则：判断当前结点key的个数是否小于等于m-1，如果满足，直接插入即可，如果不满足，将节点的中间的key将这个节点分为左右两部分，中间的节点放到父节点中即可。
例子：在5阶B树中，结点最多有4个key,最少有2个key（注意：下面的节点统一用一个节点表示key和value）。

  • 插入18，70，50,40

eb191e52c4af046dc6d858c793c8ddf3c8e.jpg

  • 插入22

0c6e169e37ff9643c46c72922f42bcb5d46.jpg

插入22时，发现这个节点的关键字已经大于4了，所以需要进行分裂，分裂的规则在上面已经讲了，分裂之后，如下。
1377e97a1160e07ffa600c0d8cba7cadf1e.jpg

  • 接着插入23，25，39

03e1e510bcd8672a98e1a67dd60a91d3aea.jpg
分裂，得到下面的。
1155825270844bbe53c9f2701395c3fa9af.jpg

删除

  1. 对于非叶子节点的删除，我们需要用后继key（元素）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。

  2. 如果删除叶子节点，如果删除元素后元素个数少于（m/2），并且它的兄弟节点的元素大于（m/2），也就是说兄弟节点的元素比最少值m/2还多，将先将父节点的元素移到该节点，然后将兄弟节点的元素再移动到父节点

    1. 如果删除后不满足B树的要求，，所以，我们需要考虑向兄弟节点借元素。
    2. 如果兄弟节点中没有多余的节点（2个），那么应该首先，还是将先将父节点的元素移到该节点，然后，将当前节点及它的兄弟节点中的key合并，形成一个新的节点。移动之后，跟兄弟节点合并。


    B树的删除操作相对于插入操作是相对复杂一些的，但是，你知道记住几种情况，一样可以很轻松的掌握的。

  • 现在有一个初始状态是下面这样的B树，然后进行删除操作。

261678b789a5f4dac373093919ea6a41b8a.jpg

  • 删除15，这种情况是删除叶子节点的元素，如果删除之后，节点数还是大于m/2，这种情况只要直接删除即可。

0ed340c43b270b4a7932d7db15ebf0acc26.jpg
11e2970a52f2b9c73b2a30922b623d4e380.jpg

  • 接着，我们把22删除，这种情况的规则：22是非叶子节点，对于非叶子节点的删除，我们需要用后继key（元素）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。对于删除22，需要将后继元素24移到被删除的22所在的节点。

6343b9be4ff09d04096e9eac1d500ba0e9d-1627786907017.jpg
c60eb3ba1f5fac64515eccfc03192f40fdb.jpg

此时发现26所在的节点只有一个元素，小于2个（m/2），这个节点不符合要求，这时候的规则（向兄弟节点借元素）：如果删除叶子节点，如果删除元素后元素个数少于（m/2），并且它的兄弟节点的元素大于（m/2），也就是说兄弟节点的元素比最少值m/2还多，将先将父节点的元素移到该节点，然后将兄弟节点的元素再移动到父节点。这样就满足要求了。

我们看看操作过程就更加明白了。
853a8ead34267d029e8d984958c8d4dbea8.jpg

0ac5a97219474c5fc16270314e655bf0437-1627786959196.jpg

  • 接着删除28，删除叶子节点，删除后不满足要求，所以，我们需要考虑向兄弟节点借元素，但是，兄弟节点也没有多的节点（2个），借不了，怎么办呢？如果遇到这种情况，首先，还是将先将父节点的元素移到该节点，然后，将当前节点及它的兄弟节点中的key合并，形成一个新的节点。

e5845ae0ae2fe779a932aa452ce650a4b48.jpg
移动之后，跟兄弟节点合并。
2dfa4b4474986a121c404f2b7b89579616f.jpg

删除就只有上面的几种情况，根据不同的情况进行删除即可。

B+树

B+树其实和B树是非常相似的，我们首先看看相同点。

  • 根节点至少一个元素
  • 非根节点元素范围：m/2 <= k <= m-1

不同点。

  • B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。
  • 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
  • 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
  • 父节点存有右孩子的第一个元素的索引。

image-20210328143756798.png

插入

对于插入操作很简单，只需要记住一个技巧即可：当节点元素数量大于m-1的时候，按中间元素分裂成左右两部分，中间元素分裂到父节点当做索引存储，但是，本身中间元素还是分裂右边这一部分的。

下面以一颗5阶B+树的插入过程为例，5阶B+树的节点最少2个元素，最多4个元素。

  • 插入5，10，15，20

00114e18a748d2a453007a8b252a43ae8a4.jpg

  • 插入25，此时元素数量大于4个了，分裂

6869626e80377a560361d624f172e1e384f.jpg

  • 接着插入26，30，继续分裂

0a0428579676a0b2543433cafd702029a76.jpg
57e93e2184d5307f303a6f846cdf900345b.jpg

删除节点

叶子节点有指针的存在，向兄弟节点借元素时，不需要通过父节点了，而是可以直接通过兄弟节移动即可（前提是兄弟节点的元素大于m/2），然后更新父节点的索引；如果兄弟节点的元素不大于m/2（兄弟节点也没有多余的元素），则将当前节点和兄弟节点合并，并且删除父节点中的key。

  • 初始状态

365354deaff4bc75d16cf17c3255c46aca4.jpg

  • 删除10，删除后，不满足要求，发现左边兄弟节点有多余的元素，所以去借元素，最后，修改父节点索引

685a53344454eb37d664919a42dac30a45a.jpg

  • 删除元素5，发现不满足要求，并且发现左右兄弟节点都没有多余的元素，所以，可以选择和兄弟节点合并，最后修改父节点索引

f74ef5fff6f4489fbdcaa8d9c113eb48b26.jpg

  • 发现父节点索引也不满足条件，所以，需要做跟上面一步一样的操作

177f38002658f2edfb39a811fed992d58b0.jpg

与B树相比较

B+树相对于B树有一些自己的优势，可以归结为下面几点。

  • 单一节点存储的元素更多，使得查询的IO次数更少，所以也就使得它更适合做为数据库MySQL的底层数据结构了。
  • 所有的查询都要查找到叶子节点，查询性能是稳定的，而B树，每个节点都可以查找到数据，所以不稳定。
  • 所有的叶子节点形成了一个有序链表，更加便于查找。

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

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B*树

B-tree是B+-tree的变体，在B+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，**B树中非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）。给出了一个简单实例，如下图所示：

image-20210328143950718.png