树结构知识汇总

r囧r小猫 2021-09-18 07:24 386阅读 0赞

# 树结构 #

## 树的高度，深度，层 ##

![18721752-f612cf3e13471117.png][]

image.png

# 二叉树 #

二叉树每个节点只能有两个叉。

## 满二叉树 ##

![18721752-8c5629fe65467339.png][]

image.png

完全二叉树

![18721752-86adf420d28ad603.png][]

image.png

![18721752-9d685fd57a597a94.png][]

image.png

除最后一层，其它层节点个数都要达到最大，最后一层叶子节点靠左排列（如果只有一个叉那就靠左，即优先靠左排列）

## 二叉树的遍历 ##

*  前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
 *  中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
 *  后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

### 遍历口诀 ###

前序

先根节点 左顺 右顺

中序

左子树：左逆 根节点 右顺 最终到父节点 右子树：左逆 根节点 右顺

后续

左逆 右逆 根节点

![18721752-6aa4a922e0891d96.png][]

image.png

### code ###

递推公式

前序遍历的递推公式：
    preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
    
    中序遍历的递推公式：
    inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
    
    后序遍历的递推公式：
    postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

BinarySortTreeNode

package com.pl.arithmetic.binarySortTree;
 
 /**
 * 
 *
 * @Description: TODO
 * 
 * @ClassName BinarySortTreeNode
 * @Author pl
 * @Date 2020/10/13
 * @Version V1.0.0
 */
 public class BinarySortTreeNode {
 private int value;
 private String name;
 BinarySortTreeNode leftNode;
 BinarySortTreeNode rightNode;
 
 /**
 *前序排序
 * 
 * @param 
 * @return void
 * @exception 
 * @author silenter
 * @date 2020/10/13 7:04
 */
 public void preOrder(){
 System.out.println(this.value);
 if (this.leftNode!=null){
 this.leftNode.preOrder();
 }
 if (this.rightNode!=null){
 this.rightNode.preOrder();
 }
 }
 
 /**
 *中序排序
 * 
 * @param 
 * @return void
 * @exception 
 * @author silenter
 * @date 2020/10/13 7:04
 */
 public void infixOrder(){
 if (this.leftNode!=null){
 this.leftNode.infixOrder();
 }
 System.out.println(this.value);
 if (this.rightNode!=null){
 this.rightNode.infixOrder();
 }
 }
 
 /**
 *后续排序
 *
 * @param
 * @return void
 * @exception
 * @author silenter
 * @date 2020/10/13 7:05
 */
 public void postOrder(){
 if (this.leftNode!=null){
 this.leftNode.postOrder();
 }
 if (this.rightNode!=null){
 this.rightNode.postOrder();
 }
 System.out.println(this.value);
 }
 }

## 二叉树的存储 ##

二叉树的存储可以有两种方式存储

*  数组（顺序二叉树）
 *  链表

### 顺序二叉树（BinarySortTree） ###

二叉树的顺序存储是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中（数组），一般针对完全二叉树。

![18721752-049fa53adc723c41.png][]

image.png

![18721752-bf673e52e848176d.png][]

image.png

#### code ####

package com.pl.arithmetic.binaryTree.arrayBinaryTree;
 
 /**
 * 
 *
 * @Description: 数组二叉树，顺序二叉树
 * 
 * @ClassName ArrayBinaryTree
 * @Author pl
 * @Date 2020/11/6
 * @Version V1.0.0
 */
 public class BinarySortTree {
 private int arr[];
 public BinarySortTree(int[] arr) {
 this.arr = arr;
 }
 public void preOrder() {
 preOrder(0);
 }
 /**
 * 前序遍历
 *
 * @param index 数组索引，角标
 * @return void
 * @throws
 * @author silenter
 * @date 2020/11/6 21:57
 */
 public void preOrder(int index) {
 //@1 先判断是否数组越界 和数组是否为空
 if (index > arr.length) {
 System.out.println("无此节点");
 return;
 }
 if (arr == null && arr.length == 0) {
 System.out.println("数组为空");
 return;
 }
 System.out.println(arr[index]);
 //数组角标和数组大小永远是小于关系
 //@2 左子树
 if (index * 2 + 1 < arr.length) {
 preOrder(index * 2 + 1);
 }
 //@3 右子树
 if (index * 2 + 2 < arr.length) {
 preOrder(index * 2 + 2);
 }
 
 }
 }

BinarySortTreeDemo

public class BinarySortTreeDemo {
    
        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5, 6, 7};
            //创建一个 ArrBinaryTree
            ArrayBinaryTree arrBinaryTree = new ArrayBinaryTree(arr);
            arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
        }
    }

输出

![18721752-687680c4dd14ff03.png][]

image.png

### 二叉查找树 ###

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值

![18721752-5ec40f3828e3c1c0.png][]

image.png

#### 二叉查找树的查找，新增，删除 ####

package com.pl.arithmetic.binaryTree.binarySearchTree;
 
 /**
 * 
 *
 * @Description: TODO
 * 
 * @ClassName BinarySortTreeDemo
 * @Author pl
 * @Date 2020/11/14
 * @Version V1.0.0
 */
 public class BinarySortTreeDemo {
 private Node root;
 
 public BinarySortTreeDemo(Node root) {
 this.root = root;
 }
 
 public BinarySortTreeDemo() {
 }
 
 //添加结点的方法
 public void add(Node node) {
 if (root == null) {
 root = node;//如果root为空则直接让root指向node
 } else {
 root.addNode(node);
 }
 }
 
 //中序遍历
 public void infixOrder() {
 if (root != null) {
 root.infixOrder();
 } else {
 System.out.println("二叉排序树为空，不能遍历");
 }
 }
 
 //查找要删除的结点
 public Node search(int value) {
 Node temp = null;
 if (root == null) {
 throw new RuntimeException("根节点为空");
 } else {
 temp = root.searchNode(value);
 if (temp == null) {
 throw new RuntimeException("未查询到指定节点");
 }
 return temp;
 }
 }
 
 /**
 * 查询某一个节点的父节点，只有该节点为父节点时，才返回null，如果找不到该节点的父节点，则直接抛出异常
 *
 * @param value
 * @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
 * @throws
 * @author silenter
 * @date 2020/11/14 11:23
 */
 public Node searchParent(int value) {
 Node temp = null;
 if (root == null) {
 throw new RuntimeException("根节点为空");
 } else if (value == root.value) {
 System.out.println("当该节点为根节点时，返回null,且只有这一种情况返回null");
 return null;
 } else {
 temp = root.searchParentNode(value);
 if (temp == null) {
 throw new RuntimeException("该节点父节点为空");
 }
 return temp;
 }
 }
 
 /**
 * 查找右子树中最小的节点
 *
 * @param node
 * @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
 * @throws
 * @author silenter
 * @date 2020/11/14 10:53
 */
 public Node searchRightMixNode(Node node) {
 return this.root.searchRightMixNode(node);
 }
 
 /**
 * 删除节点
 * 有三种情况：
 * 1.要删除节点为叶子节点
 * 2.要删除节点有一个子节点
 * 3.要删除节点有两个节点
 *
 * @param value
 * @return void
 * @throws
 * @author silenter
 * @date 2020/11/14 10:26
 */
 public void delNode(int value) {
 //@1先查询出要删除节点是以上哪种情况的节点
 Node matchNode = this.search(value);
 //@2 若该节点不为空，查询该节点的父节点
 Node parentNode = this.searchParent(value);
 //@3 对该节点进行判断为三种情况中的哪种
 //@3.1 要删除节点为叶子节点
 if (matchNode.left == null && matchNode.right == null) {
 if (parentNode.left.value == matchNode.value) {
 parentNode.left = null;
 System.out.println("待删除节点无子节点，为左子树节点，已删除");
 return;
 }
 if (parentNode.right.value == matchNode.value) {
 parentNode.right = null;
 System.out.println("待删除节点无子节点，为右子树节点，已删除");
 return;
 }
 }
 //@3.2 要删除节点左右子树都不为空
 if (matchNode.left != null && matchNode.right != null) {
 Node rightTreeMixnode = this.searchRightMixNode(matchNode.right);
 delNode(rightTreeMixnode.value);
 //删除节点更确切的说是替换该节点的值，而不是替换该节点，如果替换该节点则会有改变整个树结构的可能
 matchNode.value = rightTreeMixnode.value;
 System.out.println("要删除节点左右子树都不为空，已删除");
 return;
 }
 //@3.3 要删除节点有一个子树
 if (matchNode.left != null) {
 if (parentNode.left.value == matchNode.value) {
 parentNode.left = matchNode.left;
 System.out.println("要删除节有左子树，该节点原为左子树节点，已删除");
 }
 if (parentNode.right.value == matchNode.value) {
 parentNode.right = matchNode.left;
 System.out.println("要删除节有左子树，该节点原为右子树节点，已删除");
 }
 } else if (matchNode.right != null) {
 if (parentNode.left.value == matchNode.value) {
 parentNode.left = matchNode.right;
 System.out.println("要删除节有右子树，该节点原为右子树节点，已删除");
 }
 if (parentNode.right.value == matchNode.value) {
 parentNode.right = matchNode.right;
 System.out.println("要删除节有右子树，该节点原为右子树节点，已删除");
 }
 }
 
 }
 
 public Node getRoot() {
 return root;
 }
 }

两种存储方式的对比

二叉树既可以用链式存储，也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。

## 支持重复数据的二叉查找树 ##

我们利用对象的某个字段作为键值（key）来构建二叉查找树。我们把对象中的其他字段叫作卫星数据。

针对的都是不存在键值相同的情况，有两种方式来解决：

### 1.同一个节点存储多个数据 ###

利用链表或者支持动态扩容的数组。

### 2.把这个新插入的数据当作大于这个节点的值来处理 ###

每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树。

![18721752-93cd19c1aed9b08d.png][]

image.png

#### 查找 ####

遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

![18721752-dbc94c56bfa61127.png][]

image.png

#### 删除 ####

对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

![18721752-80c82ab0f4a2b122.png][]

image.png

## 二叉树的时间复杂度 ##

二叉树的插入，查找，删除都和树的高度成正比，如果求出二叉树的层数公式，也就是求出二叉树数据操作的时间复杂度。

### 高度和节点的关系推导过程 ###

在包含 n 个节点的满二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点，依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2^(K-1)。

如果是完全二叉树中，最后一层节点小于2^(K-1)。

n表示节点个数，L表示层数
 n >= 1+2+4+8+...+2^(L-2)+1
 n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

这是一个等比数列求和。  
根据等比公式

![18721752-e127201476c10c7d.png][]

image.png

求L的取值范围为：

[log2(n+1), log2n +1]

完全二叉树的层数小于等于 log2n +1，也就是说，完全二叉树的高度小于等于 log2n  
通过大O理论可知其数据操作时间复杂度为:O(logn)。  
可以看出二叉树的数据操作时间复杂度很稳定且高效，但是这个时间复杂度只适用于完全二叉树，或者满二叉树，二叉树在极端情况下可能退化成链表，所以需要对二叉树这种数据结构进行升级，让他的数据操作的时间复杂度永远符合O(logn)。  
也就是在二叉查找树的基础上进行平衡，使之数据操作的时间复杂度永远符合时间复杂度公式O(logn)，这种升级版的二叉树结构为:  
**平衡二叉树**

## 二叉查找树和散列表的对比 ##

散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)。

### 二叉查找树的优势 ###

1.  散列表顺序输出困难，需要额外排序；  
    a. 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
2.  散列表扩容代价比较大；  
    a. 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
3.  散列表查询效率不一定比二叉树高；  
    a. 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
4.  散列表涉及更复杂；  
    a. 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
5.  由于装载因子，会浪费内存；  
    a. 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

## 平衡二叉查找树 ##

![18721752-9701ab2a01d93c8d.png][]

image.png

发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。

平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

### AVLTree(Adelson-Velsky-Landis Tree) ###

一种高度平衡二叉搜索树

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。

#### AVL树调整平衡的方式 ####

左旋转

![18721752-ea4b680b9ac85e11.png][]

image.png

右旋转

![18721752-4ae2531882992bff.png][]

image.png

双旋转

略

##### 左旋右旋口诀 #####

左旋动右给左

右旋动左给右

#### code ####

node

package com.pl.arithmetic.binaryTree.avl;
 
 /**
 * 
 *
 * @Description: TODO
 * 
 * @ClassName Node
 * @Author pl
 * @Date 2020/11/14
 * @Version V1.0.0
 */
 public class Node {
 int value;
 Node left;
 Node right;
 public Node(int value) {
 this.value = value;
 }
 // AVLTree ---------------------------------------
 public int leftHeight(){
 if (left == null){
 return 0;
 }
 return left.height();
 }
 public int rightHeight(){
 if (right == null){
 return 0;
 }
 return right.height();
 }
 /**
 * 计算当前节点的树高度
 *
 * @param
 * @return int
 * @exception
 * @author silenter
 * @date 2020/11/20 7:28
 */
 public int height(){
 return Math.max(left == null ?0:left.height(),right == null?0:right.height())+1;
 }
 
 /**
 * 左旋前提右子树高于左子树
 * 左旋右旋
 *
 * 创建新节点，代替当前根节点，左子树和当前节点一样，右子树变成右子树的左子树
 * 右子树等于当前节点右子树的右子节点，当前节点的值等于右子节点的值，当前节点左子树指向新节点，
 *
 * @param
 * @return void
 * @exception
 * @author silenter
 * @date 2020/11/20 8:13
 */
 public void leftRoute(){
 Node newNode = new Node(this.value);
 newNode.left = this.left;
 newNode.right = this.right.left;
 this.value = right.value;
 this.right = right.right;
 this.left = newNode;
 }
 
 /**
 * 右旋的前提，左子树高于右子树
 *
 * @param
 * @return void
 * @exception
 * @author silenter
 * @date 2020/11/20 8:14
 */
 public void rightRoute(){
 Node newNode = new Node(this.value);
 newNode.left = left.right;
 newNode.right = right;
 value = left.value;
 left = left.left;
 right = newNode;
 }
 /**
 * 添加节点 和bst相比，只有添加不同
 *
 * @param node
 * @return void
 * @exception
 * @author silenter
 * @date 2020/11/14 9:31
 */
 public void addNode(Node node){
 verifyNode(node);
 if (node.value<this.value){
 if (this.left!=null){
 this.left.addNode(node);
 }else if (this.left == null){
 this.left = node;
 }
 }
 if (node.value>this.value){
 if (this.right!=null){
 this.right.addNode(node);
 }else if (this.right == null){
 this.right = node;
 }
 }
 //左高右旋
 if (leftHeight()-rightHeight()>1){
 if (right != null && left.rightHeight()>left.leftHeight()){
 left.leftRoute();
 rightRoute();
 }else {
 rightRoute();
 }
 }
 //右高左旋
 if (rightHeight()-leftHeight()>1){
 if (right != null && right.leftHeight()>right.rightHeight()){
 right.rightRoute();
 leftRoute();
 }else {
 leftRoute();
 }
 }
 
 }
 // AVLTree ---------------------------------------
 public Node searchRightMixNode(Node node){
 Node tempNode = node;
 while (tempNode.left!=null){
 tempNode = tempNode.left;
 }
 return tempNode;
 }
 
 /**
 * 查找指定节点
 *
 * @param value
 * @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
 * @exception
 * @author silenter
 * @date 2020/11/14 10:18
 */
 public Node searchNode(int value){
 Node tempNode = null;
 if (this.value == value){
 tempNode = this;
 System.out.println("找到指定节点");
 return tempNode;
 }
 if (tempNode ==null){
 if (value<this.value && this.left!=null){
 tempNode = this.left.searchNode(value);
 }
 if (value>this.value&&this.right!=null){
 tempNode = this.right.searchNode(value);
 }
 }
 return tempNode;
 }
 
 /**
 * 查找当前节点的父节点
 *
 * @param value
 * @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
 * @exception
 * @author silenter
 * @date 2020/11/14 9:32
 */
 public Node searchParentNode(int value){
 if ((this.left !=null && this.left.value == value) || (this.right !=null && this.right.value == value)){
 System.out.println("找到该父节点"+this);
 return this;
 }else{
 if (value <this.value && this.left!=null){
 return this.left.searchParentNode(value);
 }else if (value>this.value && this.right!=null) {
 return this.right.searchParentNode(value);
 }
 }
 return null;
 }
 
 /**
 * 前序遍历
 *
 * @param
 * @return void
 * @exception
 * @author silenter
 * @date 2020/11/14 9:19
 */
 //中序遍历
 public void infixOrder() {
 if(this.left != null) {
 this.left.infixOrder();
 }
 System.out.println(this);
 if(this.right != null) {
 this.right.infixOrder();
 }
 }
 
 public void verifyNode(Node node){
 if (node ==null){
 throw new RuntimeException("node为空");
 }
 }
 
 
 @Override
 public String toString() {
 return "Node{" +
 "value=" + value +
 '}';
 }
 }

AVLTree

package com.pl.arithmetic.binaryTree.avl;
 
 /**
 * 
 *
 * @Description: TODO
 * 
 * @ClassName AVLTree
 * @Author pl
 * @Date 2020/11/20
 * @Version V1.0.0
 */
 public class AVLTree {
 private Node root;
 
 public Node getRoot() {
 return root;
 }
 
 // 添加结点的方法
 public void add(Node node) {
 if (root == null) {
 root = node;// 如果root为空则直接让root指向node
 } else {
 root.addNode(node);
 }
 }
 
 // 中序遍历
 public void infixOrder() {
 if (root != null) {
 root.infixOrder();
 } else {
 System.out.println("二叉排序树为空，不能遍历");
 }
 }
 }

AVLTreeDemo

package com.pl.arithmetic.binaryTree.avl;
 
 /**
 * 
 *
 * @Description: TODO
 * 
 * @ClassName AVLTreeDemo
 * @Author pl
 * @Date 2020/11/20
 * @Version V1.0.0
 */
 public class AVLTreeDemo {
 
 public static void main(String[] args) {
 //int[] arr = {4,3,6,5,7,8};
 //int[] arr = { 10, 12, 8, 9, 7, 6 };
 int[] arr = { 10, 11, 7, 6, 8, 9 };
 //创建一个 AVLTree对象
 AVLTree avlTree = new AVLTree();
 //添加结点
 for(int i=0; i < arr.length; i++) {
 avlTree.add(new Node(arr[i]));
 }
 
 //遍历
 System.out.println("中序遍历");
 avlTree.infixOrder();
 
 System.out.println("在平衡处理~~");
 System.out.println("树的高度=" + avlTree.getRoot().height()); //3
 System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
 System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
 System.out.println("当前的根结点=" + avlTree.getRoot());//8
 
 
 }
 }

### 红黑树（RB-Tree） ###

#### 为何要引入红黑树？ ####

AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。

红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。

#### 红黑树的应用 ####

红黑树（Red-Black Tree，以下简称RBTree）的实际应用非常广泛，比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等，各种语言的函数库如Java的TreeMap和TreeSet，C++ STL的map、multimap、multiset等。

RBTree也是函数式语言中最常用的持久数据结构之一，在计算几何中也有重要作用。值得一提的是，Java 8中HashMap的实现也因为用RBTree取代链表，性能有所提升。

#### 红黑树的定义 ####

1.  任何一个节点都有颜色，黑色或者红色
2.  根节点是黑色的
3.  任何相邻的节点都不能同时为红色
4.  任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等（据不平衡，从而保持整体平衡）
5.  空节点被认为是黑色的，即叶子节点是黑色的。

##### notice #####

###### 红黑树的高度 ######

红黑树是在原先的二叉查找树的基础上引入黑色节点来平衡二叉树高度，即如果将红色节点构成的树比作BSTree，其高度近似于㏒₂ⁿ  
，那么引入红色节点的红黑树，根据红黑树的定义3,4可知，红黑树中的的最长路径（从根节点到叶子节点）即此路径上红黑节点数量相等，那么红黑树最多比BSTree高一般，即红黑树的高度近似于2㏒₂ⁿ。  
所以，红黑树的高度只比高度平衡的 AVL 树的高度㏒₂ⁿ仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。

### 红黑树的插入 ###

红黑树的插入操作可以分为两步：

1.插入

2.插入后的平衡调整

#### 插入后的修复操作有三种情况 ####

1.  关注节点（a），父节点，叔叔节点均为红色。  
    a. 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；  
    b. 将关注节点 a 的祖父节点 c 的颜色设置成红色；  
    c. 关注节点变成 a 的祖父节点 c；  
    d. 跳到 CASE 2 或者 CASE 3。

![18721752-6637ae68aa998342.png][]

image.png

2.关注节点（a）和父节点均为红色，叔叔节点为黑色，且关注的节点是父节点的右子节点。  
a. 关注节点变成节点 a 的父节点 b；  
b. 围绕新的关注节点b 左旋；  
c. 跳到 CASE 3。

![18721752-0800207f4cdedb82.png][]

image.png

3.关注节点(a)和父节点均为红色，叔叔节点为黑色，关注节点 a 是其父节点 b 的左子节点  
a. 围绕关注节点 a 的祖父节点 c 右旋；  
b. 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。  
c. 调整结束。

![18721752-1eb74525f46681f5.png][]

image.png

#### code ####

private void insert(RBTNode<T> node) {
 int cmp;
 RBTNode<T> parentNode = null;
 RBTNode<T> tempNode = this.mRoot;
 
 // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
 while (tempNode != null) {
 parentNode = tempNode;
 cmp = node.key.compareTo(tempNode.key);
 if (cmp < 0)
 tempNode = tempNode.left;
 else
 tempNode = tempNode.right;
 }
 
 node.parent = parentNode;
 if (parentNode!=null) {
 cmp = node.key.compareTo(parentNode.key);
 if (cmp < 0)
 parentNode.left = node;
 else
 parentNode.right = node;
 } else {
 this.mRoot = node;
 }
 
 // 2. 设置节点的颜色为红色
 node.color = RED;
 
 // 3. 将它重新修正为一颗二叉查找树
 insertFixUp(node);
 }
 
 /*
 * 红黑树插入修正函数
 *
 * 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
 * 目的是将它重新塑造成一颗红黑树。
 *
 * 参数说明：
 * node 插入的结点 
 */
 private void insertFixUp(RBTNode<T> node) {
 RBTNode<T> parent, gparent;
 
 // 若“父节点存在，并且父节点的颜色是红色”
 while (((parent = parentOf(node))!=null) && isRed(parent)) {
 gparent = parentOf(parent);
 
 //若“父节点”是“祖父节点的左孩子”
 if (parent == gparent.left) {
 // Case 1条件：叔叔节点是红色
 RBTNode<T> uncle = gparent.right;
 if ((uncle!=null) && isRed(uncle)) {
 setBlack(uncle);
 setBlack(parent);
 setRed(gparent);
 //每将一个节点变为红色节点，需要重新检查其是否有两个相连节点为红色，所以需要将当前节点变成新变为红色节点的gparent
 node = gparent;
 continue;
 }
 
 // Case 2条件：叔叔是黑色，且当前节点是右孩子
 if (parent.right == node) {
 RBTNode<T> tmp;
 leftRotate(parent);
 tmp = parent;
 parent = node;
 node = tmp;
 }
 
 // Case 3条件：叔叔是黑色，且当前节点是左孩子。
 setBlack(parent);
 setRed(gparent);
 rightRotate(gparent);
 } else { //若“z的父节点”是“z的祖父节点的右孩子”
 // Case 1条件：叔叔节点是红色
 RBTNode<T> uncle = gparent.left;
 if ((uncle!=null) && isRed(uncle)) {
 setBlack(uncle);
 setBlack(parent);
 setRed(gparent);
 node = gparent;
 continue;
 }
 
 // Case 2条件：叔叔是黑色，且当前节点是左孩子
 if (parent.left == node) {
 RBTNode<T> tmp;
 rightRotate(parent);
 tmp = parent;
 parent = node;
 node = tmp;
 }
 
 // Case 3条件：叔叔是黑色，且当前节点是右孩子。
 setBlack(parent);
 setRed(gparent);
 leftRotate(gparent);
 }
 }
 
 // 将根节点设为黑色
 setBlack(this.mRoot);
 }

### 红黑树的删除 ###

红黑树的删除也是分为两步：  
1.指定节点的删除  
2.删除节点后的平衡修复

#### 删除修复操作分为四种情况(删除黑节点后)： ####

1.  待删除的节点的兄弟节点是红色的节点。
2.  待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的。
3.  待调整的节点的兄弟节点是黑色的节点，且兄弟节点的左子节点是红色的，右节点是黑色的(兄弟节点在右边)，如果兄弟节点在左边的话，就是兄弟节点的右子节点是红色的，左节点是黑色的。
4.  待调整的节点的兄弟节点是黑色的节点，且右子节点是是红色的(兄弟节点在右边)，如果兄弟节点在左边，则就是对应的就是左节点是红色的。

#### 修复完毕标志： ####

删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。

#### notice： ####

##### 红黑树删除后的平衡实质是节点的借调 #####

删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。  
删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。

#### 删除操作-case 1 ####

由于兄弟节点是红色节点的时候，无法借调黑节点，所以需要将兄弟节点提升到父节点，由于兄弟节点是红色的，根据RBTree的定义，兄弟节点的子节点是黑色的，就可以从它的子节点借调了。

case 1这样转换之后就会变成后面的case 2，case 3，或者case 4进行处理了。上升操作需要对C做一个左旋操作，如果是镜像结构的树只需要做对应的右旋操作即可。

之所以要做case 1操作是因为兄弟节点是红色的，无法借到一个黑节点来填补删除的黑节点。

![18721752-c323934c28c5a3aa.png][]

image.png

#### 删除操作-case 2 ####

case 2的删除操作是由于兄弟节点可以消除一个黑色节点，因为兄弟节点和兄弟节点的子节点都是黑色的，所以可以将兄弟节点变红，这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点A变成新的节点，继续向上调整，直到整颗树的颜色符合RBTree的定义为止。

case 2这种情况下之所以要将兄弟节点变红，是因为如果把兄弟节点借调过来，会导致兄弟的结构不符合RBTree的定义，这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后，达到了局部的平衡了，但是对于祖父节点来说是不符合定义4的。这样就需要回溯到父节点，接着进行修复操作。

![18721752-2599fae8a57a3984.png][]

image.png

#### 删除操作-case 3 ####

case 3的删除操作是一个中间步骤，它的目的是将左边的红色节点借调过来，这样就可以转换成case 4状态了，在case 4状态下可以将D，E节点都阶段过来，通过将两个节点变成黑色来保证红黑树的整体平衡。

之所以说case-3是一个中间状态，是因为根据红黑树的定义来说，下图并不是平衡的，他是通过case 2操作完后向上回溯出现的状态。之所以会出现case 3和后面的case 4的情况，是因为可以通过借用侄子节点的红色，变成黑色来符合红黑树定义4.

![18721752-72a964cb544c4b58.png][]

image.png

#### 删除操作-case 4 ####

Case 4的操作是真正的节点借调操作，通过将兄弟节点以及兄弟节点的右节点借调过来，并将兄弟节点的右子节点变成红色来达到借调两个黑节点的目的，这样的话，整棵树还是符合RBTree的定义的。

Case 4这种情况的发生只有在待删除的节点的兄弟节点为黑，且子节点不全部为黑，才有可能借调到两个节点来做黑节点使用，从而保持整棵树都符合红黑树的定义。

![18721752-66caea16a18eef93.png][]

image.png

实际上这张图是错误的，最终需要将C节点变成黑色节点，因为原先关注节点的兄弟节点是黑色，如果变成红色则影响局部平衡了。

#### code ####

/*
 * 删除结点(node)，并返回被删除的结点
 *
 * 参数说明：
 * node 删除的结点
 */
 private void remove(RBTNode<T> node) {
 RBTNode<T> child, parent;
 boolean color;
 
 // 被删除节点的"左右孩子都不为空"的情况。
 if ( (node.left!=null) && (node.right!=null) ) {
 // 被删节点的后继节点。(称为"取代节点")
 // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
 RBTNode<T> replace = node;
 // 获取后继节点
 replace = replace.right;
 while (replace.left != null)
 replace = replace.left;
 // "node节点"不是根节点(只有根节点不存在父节点)
 if (parentOf(node)!=null) {
 if (parentOf(node).left == node)
 //这里直接替换了
 parentOf(node).left = replace;
 else
 parentOf(node).right = replace;
 } else {
 // "node节点"是根节点，更新根节点。
 this.mRoot = replace;
 }
 
 // child是"取代节点"的右孩子，也是需要"调整的节点"。
 // "取代节点"肯定不存在左孩子！因为它是一个后继节点。
 child = replace.right;
 parent = parentOf(replace);
 // 保存"取代节点"的颜色
 color = colorOf(replace);
 // "被删除节点"是"它的后继节点的父节点"
 //以下调整取代节点的右子树
 if (parent == node) {
 parent = replace;
 } else {
 // child不为空
 if (child!=null)
 setParent(child, parent);
 //这里替换取代节点的右子树到其父节点下，将取代节点的右子树赋值为删除节点的右子树，此时取代节点已经被删除了
 parent.left = child;
 replace.right = node.right;
 setParent(node.right, replace);
 }
 replace.parent = node.parent;
 replace.color = node.color;
 replace.left = node.left;
 node.left.parent = replace;
 //只有取代节点是黑色才修复，将取代节点的右子树当做当前关注的节点进行调整（虽然是删除节点，但是真正删除的是取代节点）
 if (color == BLACK)
 removeFixUp(child, parent);
 
 node = null;
 return ;
 }
 
 if (node.left !=null) {
 child = node.left;
 } else {
 child = node.right;
 }
 
 parent = node.parent;
 // 保存"取代节点"的颜色
 color = node.color;
 
 if (child!=null)
 child.parent = parent;
 
 // "node节点"不是根节点
 if (parent!=null) {
 if (parent.left == node)
 parent.left = child;
 else
 parent.right = child;
 } else {
 this.mRoot = child;
 }
 
 if (color == BLACK)
 removeFixUp(child, parent);
 node = null;
 }
 
 /*
 * 红黑树删除修正函数
 *
 * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
 * 目的是将它重新塑造成一颗红黑树。
 *
 * 参数说明：
 * node 待修正的节点(原取代节点的子节点，此时这个节点已经替换了取代节点的位置，但是此时不影响此节点原先兄弟节点和和父节点的状态)
 */
 private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
 RBTNode<T> other;
 
 while ((node==null || isBlack(node)) && (node != this.mRoot)) {
 if (parent.left == node) {
 other = parent.right;
 if (isRed(other)) {
 // Case 1: x的兄弟w是红色的
 setBlack(other);
 setRed(parent);
 leftRotate(parent);
 other = parent.right;
 }
 //Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
 if (isBlack(other.left)&&isBlack(other.right)) {
 //这种情况，其兄弟节点保持局部平衡，所以不动其兄弟节点，将关注节点换成取代节点的父节点，向上追溯
 setRed(other);
 node = parent;
 parent = parentOf(node);
 } else {
 if (other.right!=null && isBlack(other.right)) {
 // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
 setBlack(other.left);
 setRed(other);
 rightRotate(other);
 //兄弟节点调整为右悬置后的兄弟节点
 other = parent.right;
 }
 // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
 setColor(other, colorOf(parent));
 setBlack(parent);
 setBlack(other.right);
 leftRotate(parent);
 node = this.mRoot;
 break;
 }
 } else {
 
 other = parent.left;
 if (isRed(other)) {
 // Case 1: x的兄弟w是红色的
 setBlack(other);
 setRed(parent);
 rightRotate(parent);
 other = parent.left;
 }
 
 if (isBlack(other.left) && isBlack(other.right)) {
 // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
 setRed(other);
 node = parent;
 parent = parentOf(node);
 } else {
 if (other.left!=null && isBlack(other.left)) {
 // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
 setBlack(other.right);
 setRed(other);
 leftRotate(other);
 other = parent.left;
 }
 // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
 setColor(other, colorOf(parent));
 setBlack(parent);
 setBlack(other.left);
 rightRotate(parent);
 node = this.mRoot;
 break;
 }
 }
 }
 //最后都是让根节点为黑色节点
 if (node!=null)
 setBlack(node);
 }

[18721752-f612cf3e13471117.png]: /images/20210918/0215b80382094d5384bc126a3b481c1e.png
[18721752-8c5629fe65467339.png]: /images/20210918/684179aabd684c4b896d9b43812f9cb9.png
[18721752-86adf420d28ad603.png]: /images/20210918/ea89610d97b24c7d8cfbd25a20374cac.png
[18721752-9d685fd57a597a94.png]: /images/20210918/51199ff4bdfc46dfb8218eedd629f235.png
[18721752-6aa4a922e0891d96.png]: /images/20210918/3ccb6c60b7314c029d9b700c5e536314.png
[18721752-049fa53adc723c41.png]: /images/20210918/46519e4ea0bd41f282d7a76eef26f401.png
[18721752-bf673e52e848176d.png]: /images/20210918/6c80571b115644f096fadc119254300d.png
[18721752-687680c4dd14ff03.png]: /images/20210918/b1b6c1a215c64cc68d2ece41e0d1a5bd.png
[18721752-5ec40f3828e3c1c0.png]: /images/20210918/242b2d2457eb482692b9748ec061b2fe.png
[18721752-93cd19c1aed9b08d.png]: /images/20210918/3c8ab07182444fb0a76da97d2f0e69b6.png
[18721752-dbc94c56bfa61127.png]: /images/20210918/ff93080d1cb24cab8a76d5e7b0cdb430.png
[18721752-80c82ab0f4a2b122.png]: /images/20210918/3f70ffa56e8242b69295166ff8a56932.png
[18721752-e127201476c10c7d.png]: /images/20210918/e2b4b166f36149aa86f8ab7ff4e8adaf.png
[18721752-9701ab2a01d93c8d.png]: /images/20210918/7d56b1e9b6e249a2b2470d2181af5b9e.png
[18721752-ea4b680b9ac85e11.png]: /images/20210918/2ac7c80412924450b9b1e8f63f7feccc.png
[18721752-4ae2531882992bff.png]: /images/20210918/9ff699ec394a4ab6bce2c0a43dfa0232.png
[18721752-6637ae68aa998342.png]: /images/20210918/e7905b82e34540b19c3ef125548c8730.png
[18721752-0800207f4cdedb82.png]: /images/20210918/dce769978bec4d6189cfefc7f6af98d8.png
[18721752-1eb74525f46681f5.png]: /images/20210918/e13a6b250aca48a68ab0d92187bd8779.png
[18721752-c323934c28c5a3aa.png]: /images/20210918/f67aa79527b84c39bf296789c759dfb7.png
[18721752-2599fae8a57a3984.png]: /images/20210918/2c61b750b162487d90b4a01a1e253cea.png
[18721752-72a964cb544c4b58.png]: /images/20210918/4651c0e11b5d4407a8288f0a65743f0e.png
[18721752-66caea16a18eef93.png]: /images/20210918/4db1049775264c09a65925b5b3bbf42d.png