数据结构：树基础

短命女 2022-11-12 02:48 180阅读 0赞

### 目录 ###

*  第一章 树
 *   *  1.1、树的定义
     *  1.2、树的术语
 *  第二章 二叉树
 *   *  2.1、二叉树的定义
     *  2.2、二叉树的术语
     *  2.3、二叉树的性质
 *  第三章 二叉查找树
 *   *  3.1、BST的定义
     *  3.2、BST的结构
     *  3.3、BST的添加
     *  3.4、BST的获取
     *   *  3.4.1、获取指定值
         *  3.4.2、获取最小键
         *  3.4.3、获取最大键
         *  3.4.4、获取树深度
     *  3.5、BST的删除
     *   *  3.5.1、删除最小结点
         *  3.5.2、删除最大结点
         *  3.5.3、删除指定结点
     *  3.6、BST的遍历
     *   *  3.6.1、前序遍历
         *  3.6.2、中序遍历
         *  3.6.3、后序遍历
         *  3.6.4、层序遍历
     *  3.7、BST的问题
 *  第四章 红黑树
 *   *  4.1、2-3-4树的定义
     *  4.2、2-3-4树的插入
     *  4.3、2-3-4树转RBT
     *  4.4、RBT的定义
     *  4.5、RBT的性质
     *  4.6、RBT的结构
     *  4.7、RBT的操作
     *   *  4.7.1、左旋操作
         *  4.7.2、右旋操作
         *  4.7.3、变色操作
     *  4.8、RBT的添加
     *   *  4.8.1、添加操作
         *  4.8.2、如何修正
         *  4.8.3、修正操作
         *  4.8.4、添加测试
     *  4.9、RBT的获取
     *   *  4.9.1、获取指定结点
         *  4.9.2、获取最小结点
         *  4.9.3、获取最大结点
         *  4.9.4、获取前驱结点
         *  4.9.5、获取后继结点
     *  4.10、RBT的删除
     *   *  4.10.1、删除操作
         *  4.10.2、如何修正
         *  4.10.3、修正操作
         *  4.10.4、删除测试
 *  第五章 AVL树
 *   *  5.1、AVL树的定义
     *  5.2、AVL树的性质
     *  5.3、AVL树的结构
     *  5.4、AVL树的操作
     *   *  5.4.1、左旋操作（RR）
         *  5.4.2、右旋操作（LL）
         *  5.4.3、左右双旋（LR）
         *  5.4.4、右左双旋（RL）
     *  5.5、AVL树的添加
     *   *  5.5.1、添加操作
         *  5.5.2、如何修正
         *  5.5.3、修正操作
         *  5.5.4、添加测试
     *  5.6、AVL树的获取
     *   *  5.6.1、获取指定结点
         *  5.6.2、获取最小结点
         *  5.6.3、获取最大结点
         *  5.6.4、获取前驱结点
         *  5.6.5、获取后继结点
     *  5.7、AVL树的删除
     *   *  5.7.1、删除操作
         *  5.7.2、如何删除
         *  5.7.3、修正操作
         *  5.7.4、删除测试

--------------------

> 项目地址：https://gitee.com/caochenlei/data-structures

# 第一章 树 #

## 1.1、树的定义 ##

树（Tree）是一种数据结构，他是由n(n>=1)个有限结点组成一个具有层次关系的集合。

把他叫做“树”是因为他看起来像一棵倒挂的树，也就是说他是根朝上，而叶朝下的。

![665cf9558ee9e9986ad46ed72e9fb5f0.png][]

他具有以下的特点：

*  每个结点有零个或多个子结点；
 *  没有父结点的结点称为根结点；
 *  每一个非根结点有且只有一个父结点；
 *  除了根结点外，每个子结点可以分为多个不相交的子树。

## 1.2、树的术语 ##

![665cf9558ee9e9986ad46ed72e9fb5f0.png][]

**度数（Degree）：** 每个结点所拥有子树的个数。结点B的度数为2，结点C的度数为1，结点D的度数为3，结点K、L、F、G、M、I、J等的度数为0。

**层数（Level）：** 树的层数。假设树根A为第一层，结点B、C、D等所在层数为第二层，然后依次向下累加。

**高度（Height）：** 树的最大层数。 上图树的高度为4。

**终端结点（Terminal Nodes）：** 度数为零的结点就是树叶（叶子结点）也叫做终端结点。结点K、L、F、G、M、I、J等都是终端结点。

**非终端结点（Nonterminal Nodes）：** 终端结点以外的所有结点都是非终端结点。结点A、B、C、D、E、H等都是非终端结点。

**祖先结点（Ancestor Nodes）：** 祖先结点是指从树根到该结点路径上所包含的结点。结点B就是结点K的祖先结点之一。

**子孙结点（Descendent Nodes）：** 子孙结点是指该结点往下追溯子树中的任意一个结点。结点K、L就是结点B的子孙结点。

**父亲结点（Parent Nodes）：** 每个结点所指向的上一层结点就是父结点。结点B的父结点就是A结点。

**儿子结点（Children Nodes）：** 每个结点所指向的下一层结点就是子结点。结点B、C、D都是结点A的子结点。

**兄弟结点（Siblings Nodes）：** 有共同父结点的结点为兄弟结点。结点B、C、D的父结点都是A结点，因此，他们三个结点就是兄弟结点。

**叔叔结点（Uncle Nodes）：** 父亲结点的兄弟结点就是叔叔结点。结点K的叔叔结点就是结点F。

**同代结点（Generation Nodes）：** 在同一棵树中具有相同层数的结点。结点E、F的层数相同，因此，他们两个结点就是同代结点。

**森林（Forest）：** 0个或多个不相交的树组成。对森林加上一个根，森林即成为树。删去根，树即成为森林。

# 第二章 二叉树 #

## 2.1、二叉树的定义 ##

二叉树（Binary Tree）就是度不超过2的树，也就是每个结点最多有两个子结点。

![eb6090687332a30999831a5a8fd55d59.png][]

## 2.2、二叉树的术语 ##

**满二叉树（Full Binary Tree）：** 除最后一层无任何子结点外，其余每一层上的所有结点都有两个子结点的二叉树，就是满二叉树，满二叉树外观上是一个三角形。深度为h的满二叉树必有2h\-1个结点，第i层上有2i-1结点，具有n个结点的满二叉树的深度为 log2(n+1)。

![f46601ba4647455497942c6ec2b60393.png][]

**完全二叉树（Complete Binary Tree）：** 如果该二叉树的所有叶子结点都在最后一层或者倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续，我们称为完全二叉树。一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

![a6cc1c8793d2335420149a1f33d6f9c4.png][]

## 2.3、二叉树的性质 ##

*  在任意一棵二叉树中，深度为h的二叉树中至多含有2h\-1个结点，其中h≥1。
 *  在任意一棵二叉树中，第i层上至多有2i-1个结点，其中i≥1。
 *  在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则必有n0=n2\+1。
 *  在任意一棵二叉树中，包含n个结点的二叉树的高度至少为log2(n+1)。
 *  若采用连续储存（数组）的方式存放二叉树，则结点与下标之间的关系：
    
     *  若某个结点的下标为 i ，则这个结点的父结点的下标为 i / 2。
     *  若某个结点的下标为 i ，且结点的度为2，则这个结点的左子结点的下标为 2 \* i + 1。
     *  若某个结点的下标为 i ，且结点的度为2，则这个结点的右子结点的下标为 2 \* i + 2。

# 第三章 二叉查找树 #

## 3.1、BST的定义 ##

二叉查找树（Binary Search Tree）又称二叉搜索树，还称二叉排序树（Binary Sort Tree），简称BST。

![f03d4bd02ef4fa43c8bfe60d5be34189.png][]

二叉查找树所特有的术语：

*  **前驱结点：** 小于当前结点的最大值，例如上图的结点5的前驱结点就是结点4。
 *  **后继结点：** 大于当前结点的最小值，例如上图的结点5的后继结点就是结点6。

二叉查找树具有以下性质：

（1）若左子树不空，则左子树上所有结点的值均小于或等于他的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于他的根结点的值；

（3）左、右子树也分别为二叉排序树；

二叉查找树在线演示网站：https://www.cs.usfca.edu/~galles/visualization/BST.html

## 3.2、BST的结构 ##

public class BinarySearchTree<Key extends Comparable<Key>, Value> { 
        private class Node {     //结点类
            public Key key;     //存储键
            public Value value; //存储值
            public Node left;   //指向左子结点
            public Node right;  //指向右子结点
    
            public Node(Key key, Value value) { 
                this.key = key;
                this.value = value;
            }
    
            @Override
            public String toString() { 
                return "Node{" + "key=" + key + ", value=" + value + "}";
            }
        }
    
        private Node root;      //根结点
        private int N;          //结点数
    
        //获取当前树的结点数
        public int size() { 
            return N;
        }
    
        //判断当前树是否为空
        public boolean isEmpty() { 
            return N == 0;
        }
    
        //以下方法请写在这里
    }

## 3.3、BST的添加 ##

*  如果当前树中没有任何一个结点，则直接把新结点当做根结点使用。
 *  如果当前树不为空，则从根结点开始：
    
     *  如果新结点的key小于当前结点的key，则继续找当前结点的左子结点；
     *  如果新结点的key大于当前结点的key，则继续找当前结点的右子结点；
     *  如果新结点的key等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值即可。

--------------------

//向当前树中添加结点
    public void put(Key key, Value value) { 
        root = put(root, key, value);
    }
    
    //向指定树中添加结点
    private Node put(Node x, Key key, Value value) { 
        //如果x子树为空，直接返回新结点
        if (x == null) { 
            N++;
            return new Node(key, value);
        }
        //如果x子树不空，根据情况来插入
        int cmp = key.compareTo(x.key);
        if (cmp < 0) { 
            x.left = put(x.left, key, value);
        } else if (cmp > 0) { 
            x.right = put(x.right, key, value);
        } else { 
            x.value = value;
        }
        return x;
    }

## 3.4、BST的获取 ##

### 3.4.1、获取指定值 ###

*  如果当前树中没有任何一个结点，则直接返回null。
 *  如果当前树不为空，则从根结点开始：
    
     *  如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；
     *  如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；
     *  如果要查询的key等于当前结点的key，则树中返回当前结点的value。

--------------------

//在当前树中根据Key获取Value
    public Value get(Key key) { 
        return get(root, key);
    }
    
    //在指定树中根据Key获取Value
    private Value get(Node x, Key key) { 
        //如果x子树为空，直接返回null
        if (x == null) { 
            return null;
        }
        //如果x子树不空，根据情况返回
        int cmp = key.compareTo(x.key);
        if (cmp < 0) { 
            return get(x.left, key);
        } else if (cmp > 0) { 
            return get(x.right, key);
        } else { 
            return x.value;
        }
    }

### 3.4.2、获取最小键 ###

从根结点开始，递归向左不停查找，直到最后一个结点的左结点指向null结束。

//在当前树中获取最小的Key
    public Key min() { 
        return min(root).key;
    }
    
    //在指定树中获取最小的结点
    private Node min(Node x) { 
        if (x.left == null) { 
            return x;
        }
        return min(x.left);
    }

### 3.4.3、获取最大键 ###

从根结点开始，递归向右不停查找，直到最后一个结点的右结点指向null结束。

//在当前树中获取最大的Key
    public Key max() { 
        return max(root).key;
    }
    
    //在指定树中获取最大的结点
    private Node max(Node x) { 
        if (x.right == null) { 
            return x;
        }
        return max(x.right);
    }

### 3.4.4、获取树深度 ###

*  如果根结点为空，则最大深度为0。
 *  如果根结点不空，计算左子树的最大深度，计算右子树的最大深度，当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1。

--------------------

//获取当前树最大深度
    public int maxDepth() { 
        return maxDepth(root);
    }
    
    //获取指定树最大深度
    private int maxDepth(Node x) { 
        if (x == null) { 
            return 0;
        }
        // x结点的最大深度
        int max = 0;
        //左子树的最大深度
        int maxL = 0;
        //右子树的最大深度
        int maxR = 0;
        //计算x结点左子树的最大深度
        if (x.left != null) { 
            maxL = maxDepth(x.left);
        }
        //计算x结点右子树的最大深度
        if (x.right != null) { 
            maxR = maxDepth(x.right);
        }
        //比较左子树和右子树最大深度
        max = maxL > maxR ? maxL + 1 : maxR + 1;
        return max;
    }

## 3.5、BST的删除 ##

### 3.5.1、删除最小结点 ###

![bbe030af54ffc3bda0c6822cd8b14d2e.png][]

//删除当前树中最小的结点
    public void deleteMin() { 
        root = deleteMin(root);
    }
    
    //删除指定树中最小的结点
    private Node deleteMin(Node x) { 
        if (x.left == null) { 
            N--;
            return x.right;
        }
        x.left = deleteMin(x.left);
        return x;
    }

### 3.5.2、删除最大结点 ###

![866f2b03282b5942928310e36ab360d8.png][]

//删除当前树中最大的结点
    public void deleteMax() { 
        root = deleteMax(root);
    }
    
    //删除指定树中最大的结点
    private Node deleteMax(Node x) { 
        if (x.right == null) { 
            N--;
            return x.left;
        }
        x.right = deleteMin(x.right);
        return x;
    }

### 3.5.3、删除指定结点 ###

*  如果当前树中没有任何一个结点，则不进行任何处理。
 *  如果当前树并不为空，我们要是想要删除指定结点，首先需要递归找到这个结点，然后对删除的结点分为两种情况探讨：
    
     *  删除的结点的度为0或者1：
        
         *  判断该结点的左结点指向是否为空，如果为空，让其父结点指向该结点的右结点，核心代码：`if (x.left == null) { N--; return x.right; }`
         *  判断该结点的右结点指向是否为空，如果为空，让其父结点指向该结点的左结点，核心代码：`if (x.right == null) { N--; return x.left; }`
     *  删除的结点的度为2：
        
         *  将要删除的结点先缓存起来，以备用。
         *  获取该结点右子树中最小的一个结点。
         *  删除该结点右子树中最小的一个结点。
         *  让最小结点的left指向缓存结点的左子树。
         *  让最小结点的right指向缓存结点的右子树。

--------------------

//删除当前树中指定Key对应的结点
    public void delete(Key key) { 
        root = delete(root, key);
    }
    
    //删除指定树中指定Key对应的结点
    private Node delete(Node x, Key key) { 
        //如果x子树为空，直接返回null
        if (x == null) { 
            return null;
        }
        //如果x子树不空，根据情况删除
        int cmp = key.compareTo(x.key);
        if (cmp < 0) { 
            x.left = delete(x.left, key);
        } else if (cmp > 0) { 
            x.right = delete(x.right, key);
        } else { 
            //删除左叶子结点或有一个孩子的情况
            if (x.left == null) { 
                N--;
                return x.right;
            }
            //删除右叶子结点或有一个孩子的情况
            else if (x.right == null) { 
                N--;
                return x.left;
            }
            //删除非叶子结点
            else { 
                Node t = x;
                x = min(t.right);
                x.right = deleteMin(t.right);
                x.left = t.left;
            }
        }
        return x;
    }

## 3.6、BST的遍历 ##

### 3.6.1、前序遍历 ###

![59dc8a1de587b1b7f42ec58f79ecabe0.png][]

**核心：** 先访问根结点，再访问左子树，最后访问右子树。

*  从根结点开始，首先访问根结点，再访问左子树，最后访问右子树，访问顺序：`EBG`
 *  从B 结点开始，首先访问B 结点，再访问左子树，最后访问右子树，访问顺序：`E BAD G`
 *  从G 结点开始，首先访问G 结点，再访问左子树，最后访问右子树，访问顺序：`E BAD GFH`
 *  从D 结点开始，首先访问D 结点，再访问左子树，最后访问右子树，访问顺序：`E BADC GFH`
 *  最终访问次序为：`E, B, A, D, C, G, F, H`

--------------------

//前序遍历当前树
    public void preErgodic() { 
        preErgodic(root);
    }
    
    //前序遍历指定树
    private void preErgodic(Node x) { 
        if (x == null) { 
            return;
        }
        //输出根结点
        System.out.println(x);
        //遍历左子树
        if (x.left != null) { 
            preErgodic(x.left);
        }
        //遍历右子树
        if (x.right != null) { 
            preErgodic(x.right);
        }
    }

### 3.6.2、中序遍历 ###

![59dc8a1de587b1b7f42ec58f79ecabe0.png][]

**核心：** 先访问左子树，再访问根结点，最后访问右子树。

*  从根结点开始，首先访问左子树，再访问根结点，最后访问右子树，访问顺序：`BEG`
 *  从B 结点开始，首先访问左子树，再访问B 结点，最后访问右子树，访问顺序：`ABD E G`
 *  从G 结点开始，首先访问左子树，再访问G 结点，最后访问右子树，访问顺序：`ABD E FGH`
 *  从D 结点开始，首先访问左子树，再访问D 结点，不用输出右子树，访问顺序：`ABCD E FGH`
 *  最终访问次序为：`A, B, C, D, E, F, G, H`

--------------------

//中序遍历当前树
    public void midErgodic() { 
        midErgodic(root);
    }
    
    //中序遍历指定树
    private void midErgodic(Node x) { 
        if (x == null) { 
            return;
        }
        //遍历左子树
        if (x.left != null) { 
            midErgodic(x.left);
        }
        //输出根结点
        System.out.println(x);
        //遍历右子树
        if (x.right != null) { 
            midErgodic(x.right);
        }
    }

### 3.6.3、后序遍历 ###

![59dc8a1de587b1b7f42ec58f79ecabe0.png][]

**核心：** 先访问左子树，再访问右子树，最后访问根结点。

*  从根结点开始，首先先访问左子树，再访问右子树，最后访问根结点，访问顺序：`BGE`
 *  从B 结点开始，首先先访问左子树，再访问右子树，最后访问B 结点，访问顺序：`ADB G E`
 *  从G 结点开始，首先先访问左子树，再访问右子树，最后访问G 结点，访问顺序：`ADB FHG E`
 *  从D 结点开始，首先先访问左子树，再访问右子树，最后访问D 结点，访问顺序：`ACDB FHG E`
 *  最终访问次序为：`A, C, D, B, F, H, G, E`

--------------------

//后序遍历当前树
    public void postErgodic() { 
        postErgodic(root);
    }
    
    //后序遍历指定树
    private void postErgodic(Node x) { 
        if (x == null) { 
            return;
        }
        //遍历左子树
        if (x.left != null) { 
            postErgodic(x.left);
        }
        //遍历右子树
        if (x.right != null) { 
            postErgodic(x.right);
        }
        //输出根结点
        System.out.println(x);
    }

### 3.6.4、层序遍历 ###

![cd91427725ae7305c1af1e4f0d565332.png][]

//层序遍历当前树
    public void layerErgodic() { 
        layerErgodic(root);
    }
    
    //层序遍历指定树
    private void layerErgodic(Node x) { 
        //创建一个队列
        Queue<Node> nodes = new LinkedList<>();
        //加入指定结点
        nodes.offer(x);
        //循环弹出遍历
        while (!nodes.isEmpty()) { 
            //从队列中弹出一个结点，输出当前结点的信息
            Node n = nodes.poll();
            System.out.println(n);
            //判断当前结点还有没有左子结点，如果有，则放入到nodes中
            if (n.left != null) { 
                nodes.offer(n.left);
            }
            //判断当前结点还有没有右子结点，如果有，则放入到nodes中
            if (n.right != null) { 
                nodes.offer(n.right);
            }
        }
    }

## 3.7、BST的问题 ##

BST存在的问题是，树在插入的时候会导致倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接影响了树的查找效率。最坏的情况所有的结点都在一条斜线上，这样树的高度为N。基于BST存在的问题，自平衡查找二叉树（Balanced BST）产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在LogN。

![e83f93513329aed45f93b647255b9520.png][]

平衡查找二叉树最具有代表的两种树结构分别是：红黑树和AVL树，这两种树的平衡机制不一样。

# 第四章 红黑树 #

## 4.1、2-3-4树的定义 ##

在学习红黑树（又叫红黑二叉查找树）之前，我们首先需要学习2-3-4树，因为红黑树是由2-3-4树演变过来的，所以，我们不仅要学习所以，还要学习因为。

2-3-4树是四阶的B树（Balance Tree），他属于一种多路查找树，他的结构有以下限制：

*  所有叶子结点都拥有相同的深度。
 *  结点只能是 2-结点、3-结点、4-结点之一。
    
     *  2-结点：包含 1 个元素的结点，有 2 个子结点；
     *  3-结点：包含 2 个元素的结点，有 3 个子结点；
     *  4-结点：包含 3 个元素的结点，有 4 个子结点；
 *  元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子结点，小于右子结点； 而且结点有多个元素时，每个元素必须大于他左边的和他的左子树中元素。

下图是一个典型的2-3-4树：

![09ca09fa9b4464ffd49408a562b850df.png][]

## 4.2、2-3-4树的插入 ##

我们要依次插入：`2、3、4、5、6、7、8、9、10、11、12、1`

我们先插入2，如下图：

![39663bd7eddcaffeb1c6e4c7dfe87b2d.png][]

然后再插入3，这时候就已经有了两个结点，所以直接往2后边按顺序排就行了，如下图：

![c0983fb0060c47c6291d95d332d609a5.png][]

然后再插入4，这时候就已经有了三个结点，所以直接往3后边按顺序排就行了，如下图：

![f8f7f09887e6422fb585b255a224a19b.png][]

然后再插入5，这时候就已经有了四个结点，2-3-4树最多能存储3个键，此时不符合2-3-4树结构，如下图：

![37eb516cdf887776d2ebc194cebf75ef.png][]

我们需要把最中间的那个结点3往上提，提上来之后，再分别指向左右子树，此时右子树又可以放结点了，如下图：

![0031b98953ebbe0c78f8ca06e1df0589.png][]

然后再插入6，这时候就已经有了三个结点，所以直接往5后边按顺序排就行了，如下图：

![a29ab0d0d701d2e1a33f8a39529eb502.png][]

然后再插入7，这时候就已经有了四个结点，2-3-4树最多能存储3个键，此时不符合2-3-4树结构，如下图：

![c7d49ea2a3da0e6708f1fe1635b2f191.png][]

我们需要把最中间的那个结点5往上提，提上来之后，再分别指向左右子树，此时右子树又可以放结点了，如下图：

![3a17d2adbe9dbeb3437a114b22041e02.png][]

但是我们需要把刚才提出来的5与第一次提出来的3进行合并，合并之后就已经有了3、5这两个元素，可以合并，如下图：

![a33d421221bd7a1c327d426602ab84dd.png][]

然后再插入8，这时候就已经有了三个结点，所以直接往7后边按顺序排就行了，如下图：

![285c439212c59bc18771881841a095bc.png][]

然后再插入9，这时候就已经有了四个结点，2-3-4树最多能存储3个键，此时不符合2-3-4树结构，如下图：

![abc2d59b29fbf9fba4e1d668fbdc1349.png][]

我们需要把最中间的那个结点7往上提，提上来之后，再分别指向左右子树，此时右子树又可以放结点了，如下图：

![147b8fd1a70462d9725f40951c5e544b.png][]

但是我们需要把刚才提出来的7与第一次提出来的3和第二次提出来的5进行合并，合并之后就已经有了3、5、7这三个元素，可以合并，如下图：

![a936c16d614762c859f9e4e2c1d046f6.png][]

然后再插入10，这时候就已经有了三个结点，所以直接往9后边按顺序排就行了，如下图：

![b833ca182c67c88f1f1ee0addec661ba.png][]

然后再插入11，这时候就已经有了四个结点，2-3-4树最多能存储3个键，此时不符合2-3-4树结构，如下图：

![8276a201cc00b6cd7eb1abaeeabe0fe9.png][]

我们需要把最中间的那个结点9往上提，提上来之后，再分别指向左右子树，此时右子树又可以放结点了，如下图：

![a5afdc87dc8984b04bfb94f5262e59d4.png][]

但是我们需要把刚才提出来的9与第一次提出来的3和第二次提出来的5和第三次提出来的7进行合并，合并之后就已经有了3、5、7、9这四个元素，2-3-4树最多能存储3个键，此时不符合2-3-4树结构，不可以合并，如下图：

![eb39438fef97f376ad29e98c412c2845.png][]

我们需要把最中间的那个结点5往上提，提上来之后，再分别指向左右子树，此时右子树又可以放结点了，如下图：

![f261c474137c452125c3f04568793540.png][]

然后再插入12，这时候就已经有了三个结点，所以直接往11后边按顺序排就行了，如下图：

![d6b75d503e39d6829d93b5beade03c6a.png][]

然后再插入1，这时候就已经有了2个结点，所以直接往2前边按顺序排就行了，如下图：

![fa0bb4fbd6204571f16a2a0f126bf514.png][]

最终我们将得到这棵2-3-4树，如下图：

![5a2652bec698bb730f983064e703ecd4.png][]

在构建2-3-4树的过程中，我们不难发现，这棵树是从底往上生长的，一旦遇到键放不进去，我们就需要将最中间的那个结点往上提，提完以后再看能不能合并，就这样，一步一步，将这个2-3-4树构建完成。2-3-4树的查询操作像普通的二叉查找树一样，非常简单，但由于其结点元素数不确定，在一些编程语言中实现起来并不方便，所以一般使用红黑树来代替。

## 4.3、2-3-4树转RBT ##

![111856749c223cd385a52408580bac5e.png][]

以上是2-3-4树中各种结点与红黑树中各种结点的对比关系图，这样定义完全是为了，将2-3-4树中不确定的结点全部转换为2结点，以此统一树中的结点。

观察上图会发现，2-3-4树中的3结点对应红黑树中两种不同的结构，由此我们可知道，一棵2-3-4树可以转化为多棵红黑树，而一棵红黑树只能转化一棵2-3-4树。

![5a2652bec698bb730f983064e703ecd4.png][]

将上图2-3-4树转化为红黑树，第一种情况（3结点 -> 左倾）：

![3e59b69e0e8b821a93a4945aba4787a7.png][]

将上图2-3-4树转化为红黑树，第二种情况（3结点 -> 右倾）：

![8df7d84574e6636063eb8ecd0b8fca9d.png][]

## 4.4、RBT的定义 ##

红黑树（Red Black Tree） 是一种自平衡二叉查找树，又叫红黑二叉查找树。红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（Symmetric Binary B-trees）。后来，在1978年被Leo J. Guibas和Robert Sedgewick修改为如今的“红黑树”。

红黑树是一种AVL树（平衡二叉树）的变体，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，他的左右子树高度差有可能大于1，所以红黑树不是严格意义上的AVL树（平衡二叉树），但对之进行平衡的代价较低，并且其平均统计性能要强于AVL树（平衡二叉树） 。他虽然是复杂的，但他的最坏情况运行时间也是非常良好的，并且在实践中是高效的。他可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。

由于每一棵红黑树都是一颗BST树（二叉查找树），除了结点信息、添加和删除操作有些特殊外，其余操作几乎不用修改，可以直接使用。

下图是一棵红黑树，每个叶子结点所指向的`NULL LEAF`结点不可以忽略。

![fe9dde082206687cb37d2d130a8ef07f.png][]

但是直接显示会让我们感觉很乱，所以画图的时候会忽略`NULL LEAF`结点，但是心中不可忽略。

![1cff4ba3ce2cdfed5421c521c52dc124.png][]

看到了上边的这一棵红黑树，好像和咱们之前用2-3-4树转化的不太一样，所以在这里一定要清楚，由于红黑树实现的方式不一样，所造成的结果也有可能不是唯一的，如何判断红黑树是否正确，请根据红黑树的性质进行判断，符合性质的都是正确的。

在这里再推荐一个红黑树演示的网站：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

为了大家方便测试，我们接下来代码实现的效果将会和上述网站演示的效果一样。

## 4.5、RBT的性质 ##

红黑树是一种结点带有颜色属性的二叉查找树，但他在二叉查找树之外，还有以下5大性质：

*  根是黑色。
 *  结点是红色或黑色。
 *  所有叶子结点都是黑色。（不要忘了还有`NULL LEAF`结点）
 *  每个红色结点必须有两个黑色的子结点。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
 *  从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。（任一结点开始的路径上黑色结点数平衡）

## 4.6、RBT的结构 ##

public class RedBlackTree<Key extends Comparable<Key>, Value> { 
        public class Node {                          //结点类
            public Key key;                         //存储键
            public Value value;                     //存储值
            public Node parent;                     //指向父亲结点
            public Node left;                       //指向左子结点
            public Node right;                      //指向右子结点
            public boolean color;                   //指向结点颜色
    
            public Node(Key key, Value value) { 
                this.key = key;
                this.value = value;
            }
    
            @Override
            public String toString() { 
                return "Node{" + "key=" + key + ", value=" + value + ", color=" + color + "}";
            }
        }
    
        private Node root;                          //根结点
        private int size;                           //结点数
    
        private static final boolean RED = false;   //红色结点
        private static final boolean BLACK = true;  //黑色结点
    
        //获取当前树的根结点
        public Node getRoot() { 
            return root;
        }
    
        //获取当前树的结点数
        public int size() { 
            return size;
        }
    
        //判断当前树是否为空
        public boolean isEmpty() { 
            return size == 0;
        }
    
        //获取当前结点的父亲结点
        private Node parentOf(Node node) { 
            return node != null ? node.parent : null;
        }
    
        //获取当前结点的左子结点
        private Node leftOf(Node node) { 
            return node != null ? node.left : null;
        }
    
        //获取当前结点的右子结点
        private Node rightOf(Node node) { 
            return node != null ? node.right : null;
        }
    
        //获取当前结点颜色
        private boolean colorOf(Node node) { 
            return node != null ? node.color : BLACK;
        }
    
        //设置当前结点颜色
        private void setColor(Node node, boolean color) { 
            if (node != null) { 
                node.color = color;
            }
        }
    
        //接下来的方法请写在这里...
    }

## 4.7、RBT的操作 ##

### 4.7.1、左旋操作 ###

![8738265b8eae749fd6175e8f2d3b2611.png][]

**核心描述：**

*  获取当前结点h
 *  获取当前结点h的右子结点x
 *  让h的右子结点指向x的左子结点
 *  让x的左子结点指向h结点

**动画演示：**

![dbf9bcfa3fd409eb7bbacf45644b2849.gif][]

**代码实现：**

//左旋操作
    private void rotateLeft(Node h) { 
        if (h != null) {                     //判断当前结点h是否为null
            Node x = h.right;               //获取当前结点h的右子结点x
            h.right = x.left;               //让h的右子结点指向x的左子结点
            if (x.left != null)             //判断x的左子结点是否为null
                x.left.parent = h;          //让x的左子结点的父结点指向h
            x.parent = h.parent;            //让x的父结点指向h的父结点
            if (h.parent == null)           //判断h的父结点是否为null
                root = x;                   //如果是，说明是根结点
            else if (h.parent.left == h)    //判断当前h子树是否为父结点的左子树
                h.parent.left = x;          //如果是，则修正他为新的x子树
            else                            //判断当前h子树是否为父结点的右子树
                h.parent.right = x;         //如果是，则修正他为新的x子树
            x.left = h;                     //让x的左子结点指向h结点
            h.parent = x;                   //让h结点的父结点指向x结点
        }
    }

### 4.7.2、右旋操作 ###

![35a541327b49f6e9722f5d8a5cbb94f7.png][]

**核心描述：**

*  获取当前结点h
 *  获取当前结点h的左子结点x
 *  让h的左子结点指向x的右子结点
 *  让x的右子结点指向h结点

**动画演示：**

![370fbbe367457fe0d6dcc0ccea4fb00e.gif][]

**代码实现：**

//右旋操作
    private void rotateRight(Node h) { 
        if (h != null) {                     //判断当前结点h是否为null
            Node x = h.left;                //获取当前结点h的左子结点x
            h.left = x.right;               //让h的左子结点指向x的右子结点
            if (x.right != null)            //判断x的右子结点是否为null
                x.right.parent = h;         //让x的右子结点的父结点指向h
            x.parent = h.parent;            //让x的父结点指向h的父结点
            if (h.parent == null)           //判断h的父结点是否为null
                root = x;                   //如果是，说明是根结点
            else if (h.parent.right == h)   //判断当前h子树是否为父结点的右子树
                h.parent.right = x;         //如果是，则修正他为新的x子树
            else                            //判断当前h子树是否为父结点的左子树
                h.parent.left = x;          //如果是，则修正他为新的x子树
            x.right = h;                    //让x的右子结点指向h结点
            h.parent = x;                   //让h结点的父结点指向x结点
        }
    }

### 4.7.3、变色操作 ###

*  红色变为黑色。
 *  黑色变为红色。

## 4.8、RBT的添加 ##

### 4.8.1、添加操作 ###

//添加操作
    public void put(Key key, Value value) { 
        //获取根结点
        Node t = root;
        //判断根结点
        if (t == null) { 
            root = new Node(key, value);
            root.color = BLACK;
            size++;
            return;
        }
        //找指定位置
        Node parent;
        int cmp;
        do { 
            parent = t;
            cmp = key.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                t.value = value;
        } while (t != null);
        //添加新结点
        Node e = new Node(key, value);
        e.parent = parent;
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        //添加后修正
        fixAfterPut(e);
        //添加后加一
        size++;
    }

### 4.8.2、如何修正 ###

*  1、新增一个结点，现在有1结点，不用合并

![cacf5b81c0efd9cdc26fac169d2d6822.png][]

*  2、新增一个结点，与2结点合并，直接合并

![7fd62b556c5cfa3eb95d272e92c755e5.png][]

*  3、新增一个结点，与3结点合并，直接合并

![5738722ade0b14c2fc4489240dc07641.png][]

**当插入0.5后，需要调整，我们怎么调整呢？此时2-3-4树由3-结点变为4-结点，对比`4.3章`对比表。**

修正思路：设0.5结点为x，让其父结点1变为黑色，让其爷爷结点2变为红色，然后按爷爷结点右旋。

setColor(parentOf(x), BLACK);
    setColor(grandpa, RED);
    rotateRight(grandpa);

但是什么时候我需要调整呢？也就是插入0.5以后的这种结构我如何判断呢？

判断思路：x结点的父结点是爷爷结点的左子结点，并且其叔叔结点是黑色，现在爷爷结点的右结点为null，null就是黑色。但是这种判断最终通过的是插入0.5后、插入1.5后的这两种结构都能通过，这就是这段代码的巧妙之处，这里姑且先这样，继续往下看。

if (parentOf(x) == leftOf(grandpa))
        if (colorOf(uncle) == BLACK)

--------------------

**当插入1.5后，需要调整，我们怎么调整呢？此时2-3-4树由3-结点变为4-结点，对比`4.3章`对比表。**

修正思路：设1.5结点为x，此时，我们只需要按照其父结点1左旋，左旋后就变成插入0.5那种结构了，然后**再按照插入0.5那种结构进行修正** 。

x = parentOf(x);
    rotateLeft(x);

但是什么时候我需要调整呢？也就是插入1.5以后的这种结构我如何判断呢？

判断思路：x结点的父结点是爷爷结点的左子结点，并且其叔叔结点是黑色，现在爷爷结点的右结点为null，null就是黑色，并且还是其父结点的右子结点。这样一来，对于插入1.5后这种结构可以单独处理，处理完以后，又变成了上边那个插入0.5后的结构了，因此，上边插入0.5后的判断能判断出两种也不用怕了，因为这里会单独进行处理。把插入0.5后的那种结构变成了一种默认执行状态，为什么要这么设计呢？最主要的原因就是插入1.5后的结构需要转变为插入0.5后的结构。

if (parentOf(x) == leftOf(grandpa))
        if (colorOf(uncle) == BLACK)
            if (x == rightOf(parentOf(x)))

--------------------

**至于剩下的两种插入2.5、插入4这两种情况，这里其实不用讨论了，原因很简单，这两种情况和上边那两种情况是对称的，把左变成右，把右变成左就行了。**

*  4、新增一个结点，与4结点合并，此时分裂

![79c171b824b1de7c995a86af21e13ab0.png][]

**当插入1后，需要调整，我们怎么调整呢？此时不用对比`4.3章`对比表。**

修正思路：由于一个红结点下必是两个黑结点，因此设1结点为x，让其父结点2、叔叔结点4变为黑色，让其爷爷结点3变为红色即可。

setColor(parentOf(x), BLACK);
    setColor(uncle, BLACK);
    setColor(grandpa, RED);

但是什么时候我需要调整呢？也就是插入1以后的这种结构我如何判断呢？

判断思路：x结点的父结点是爷爷结点的左子结点，并且其叔叔结点是红色。但是这种判断最终通过的是插入1后、插入2.5后的这两种结构都能通过，这就是这段代码的巧妙之处，这里姑且先这样，继续往下看。

if (parentOf(x) == leftOf(grandpa))
        if (colorOf(uncle) == RED)

--------------------

**当插入2.5后，需要调整，我们怎么调整呢？此时不用对比`4.3章`对比表。**

修正思路：由于一个红结点下必是两个黑结点，因此设2.5结点为x，让其父结点2、叔叔结点4变为黑色，让其爷爷结点3变为红色即可。

setColor(parentOf(x), BLACK);
    setColor(uncle, BLACK);
    setColor(grandpa, RED);

但是什么时候我需要调整呢？也就是插入2.5以后的这种结构我如何判断呢？

判断思路：x结点的父结点是爷爷结点的左子结点，并且其叔叔结点是红色。此时判断不判断是其父结点的右子结点都无所谓，因为不用调整结构，只需变色。

所以插入1和插入2.5这两种情况的判定是一样的，因为不涉及旋转操作，只涉及变色，而且都需要变色，所以不用区别的很清楚。

if (parentOf(x) == leftOf(grandpa))
        if (colorOf(uncle) == RED)

--------------------

**至于剩下的两种插入3.5、插入5这两种情况，这里其实不用讨论了，原因很简单，这两种情况和上边那两种情况是对称的，把左变成右，把右变成左就行了。**

### 4.8.3、修正操作 ###

//修正操作
    private void fixAfterPut(Node x) { 
        x.color = RED;//每次添加必须是红结点
    
        //因为root没有父结点，所以不能让x上移循环到root
        while (x != null && x != root && x.parent.color == RED) { 
            Node grandpa = parentOf(parentOf(x));
            if (parentOf(x) == leftOf(grandpa)) { 
                Node uncle = rightOf(grandpa);
                if (colorOf(uncle) == RED) { //这个是判断的：4、新增一个结点，与4结点合并，此时分裂
                    setColor(parentOf(x), BLACK);
                    setColor(uncle, BLACK);
                    setColor(grandpa, RED);
                    x = grandpa;//因为x结点、x的父结点、x的爷爷结点都修正过了，该让x的爷爷结点往上继续修正了
                } else { //这里是判断的：3、新增一个结点，与3结点合并，直接合并
                    if (x == rightOf(parentOf(x))) { 
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(grandpa, RED);
                    rotateRight(grandpa);
                }
            } else { 
                Node uncle = leftOf(grandpa);
                if (colorOf(uncle) == RED) { //这个是判断的：4、新增一个结点，与4结点合并，此时分裂
                    setColor(parentOf(x), BLACK);
                    setColor(uncle, BLACK);
                    setColor(grandpa, RED);
                    x = grandpa;//因为x结点、x的父结点、x的爷爷结点都修正过了，该让x的爷爷结点往上继续修正了
                } else { //这里是判断的：3、新增一个结点，与3结点合并，直接合并
                    if (x == leftOf(parentOf(x))) { 
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(grandpa, RED);
                    rotateLeft(grandpa);
                }
            }
        }
    
        root.color = BLACK;//根结点必须是黑结点
    }

### 4.8.4、添加测试 ###

添加层序遍历代码：

创建红黑树的测试：`RedBlackTreeTest`

public class RedBlackTreeTest { 
        public static void main(String[] args) { 
            RedBlackTree<Integer, Integer> rbt = new RedBlackTree<>();
            rbt.put(1, 1);
            rbt.put(2, 2);
            rbt.put(3, 3);
            rbt.put(4, 4);
            rbt.put(5, 5);
            rbt.put(6, 6);
            rbt.put(7, 7);
            rbt.put(8, 8);
            rbt.put(9, 9);
            rbt.put(10, 10);
            rbt.put(11, 11);
            rbt.put(12, 12);
            rbt.layerErgodic();
        }
    }

最终测试效果对比：

![8391d78fdaa00a934e26a7bbef404d72.png][]

## 4.9、RBT的获取 ##

### 4.9.1、获取指定结点 ###

//获取树指定结点
    public Node getNode(Key key) { 
        Node p = root;
        while (p != null) { 
            int cmp = key.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

### 4.9.2、获取最小结点 ###

//获取树最小结点
    public Node getMinNode() { 
        Node p = root;
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

### 4.9.3、获取最大结点 ###

//获取树最大结点
    public Node getMaxNode() { 
        Node p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }

### 4.9.4、获取前驱结点 ###

![9c7ecefb7879e11c208c5ae653a82fc3.png][]

**前驱结点：** 小于当前结点的最大值，在一棵树中，判断前驱结点分为三种情况。

*  第一种情况：要查询的结点为null，此时直接返回null。
 *  第二种情况：要查询的结点不为null，并且左子树不为null，在其左子树中找到最大的那个结点即可。如上图所示：结点4的前驱结点是结点3。
 *  第三中情况：要查询的结点不为null，并且左子树为null，我们就需要循环向上查询其父结点，直到当前结点是父结点的右子结点为止。如上图所示：结点5的前驱结点是结点4，操作顺序：首先结点5是结点6的左子结点，结点6是结点8的左子结点，结点8是结点4的右子结点，此时停止，结点4就是前驱结点。

--------------------

//获取指定结点的前驱结点
    public Node predecessor(Node t) { 
        if (t == null)//第一种情况
            return null;
        else if (t.left != null) { //第二种情况
            Node p = t.left;
            while (p.right != null)
                p = p.right;
            return p;
        } else { //第三种情况
            Node p = t.parent;
            Node ch = t;
            while (p != null && ch == p.left) { 
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

### 4.9.5、获取后继结点 ###

![9c7ecefb7879e11c208c5ae653a82fc3.png][]

**后继结点：** 大于当前结点的最小值，在一棵树中，判断后继结点分为三种情况。

*  第一种情况：要查询的结点为null，此时直接返回null。
 *  第二种情况：要查询的结点不为null，并且右子树不为null，在其右子树中找到最小的那个结点即可。如上图所示：结点4的后继结点是结点5。
 *  第三中情况：要查询的结点不为null，并且右子树为null，我们就需要循环向上查询其父结点，直到当前结点是父结点的左子结点为止。如上图所示：结点3的后继结点是结点4，操作顺序：首先结点3是结点2的右子结点，结点2是结点4的左子结点，此时停止，结点4就是后继结点。

--------------------

//获取指定结点的后继结点
    public Node successor(Node t) { 
        if (t == null)//第一种情况
            return null;
        else if (t.right != null) { //第二种情况
            Node p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else { //第三种情况
            Node p = t.parent;
            Node ch = t;
            while (p != null && ch == p.right) { 
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

## 4.10、RBT的删除 ##

### 4.10.1、删除操作 ###

关于红黑树的删除操作，这时候你不能使用BST的那种递归删除，因为我们当前的红黑树的结点有父结点指向，这点比较麻烦，具体删除规则一共分为4种：

*  1、要删除的结点是叶子结点，此时直接删除即可。（叶子结点可黑可红，由于RBT是黑色平衡，如果删除的是黑色结点，我们要先调整，然后再删除）
 *  2、要删除的结点是树根结点，此时直接删除即可。（树根结点永远黑色，删除完了就完了，树就空了，还保持啥平衡）
 *  3、要删除的结点有1个孩子，可能有左孩子，可能有右孩子，只需让左 / 右孩子指向 **要删除结点** 的父亲结点即可。
 *  4、要删除的结点有2个孩子，肯定有左孩子，肯定有右孩子，只需让该结点的前驱或后继结点的值覆盖 **要删除结点** 的值，然后删除前驱或后继结点即可。

我们探讨了红黑树删除的4种情况，关于第3种、第4种情况比较特殊，由于第4种情况的前驱或者后继结点要么是叶子结点、要么就是第3种的有1个孩子的情况。

如下图所示：4的前驱结点是3.5、6的后继结点是6.5，此时的问题就变成了第1种的删除规则了；5的前驱结点是4、5的后继结点是6，这两种情况都有1个孩子，此时的问题就变成了第3种的删除规则了。

![7ad85da7e61812f968cd6227c892f1da.png][]

因此，我们在进行删除操作的时候，首先从第4种规则开始判断，第4种规则虽然要删除前驱或者后继结点，但是因为和第3种情况和第1种情况重复，所以，删除的动作全部交给第3种情况和第1种情况来处理，又因为，第1、2种情况比较固定，所以，我们的处理顺序是：处理第4种、处理第3种、处理第2种、处理第1种。

当然了，在第3种中，如果删除的时候也是黑结点，那么删除后也是需要修正的，以此来保持红黑树的平衡。

> Q：第4种情况，我到底是用前驱结点的值来覆盖要删除结点的值，还是用后继结点的值来覆盖要删除结点的值？
> 
> A：两种都可以，选用的情况不同可能会造成最终的树结构不同，但是都正确。TreeMap的作者 `Josh Bloch` and `Doug Lea` 采用的是后继结点（successor），而`www.cs.usfca.edu`网站上的操作则是选用的前驱结点（predecessor），我们这里采用前驱结点，以方便验证树的结果。

//删除操作
    public Value delete(Key key) { 
        Node p = getNode(key);
        if (p == null)
            return null;
        Value oldValue = p.value;
        deleteNode(p);
        return oldValue;
    }
    
    //真正删除
    private void deleteNode(Node p) { 
        size--;
    
        //4、要删除的结点有2个孩子，肯定有左孩子，肯定有右孩子
        if (p.left != null && p.right != null) { 
            //找到前驱结点，然后替换要删除结点的键值
            Node s = predecessor(p);
            p.key = s.key;
            p.value = s.value;
            //替换完成以后，指向前驱结点为删除做准备
            p = s;
        }
    
        //3、要删除的结点有1个孩子，可能有左孩子，可能有右孩子
        Node replacement = (p.left != null ? p.left : p.right);
        if (replacement != null) { 
            //让左右子结点连接到p的父结点上
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left = replacement;
            else
                p.parent.right = replacement;
    
            //释放当前p结点所有指向等待回收
            p.left = p.right = p.parent = null;
    
            //如果当前删除的是黑结点需修正
            if (p.color == BLACK)
                fixAfterDelete(replacement);
        }
        //2、要删除的结点是树根结点，此时直接删除即可。（树根结点永远黑色，删除完了就完了，还保持啥平衡）
        else if (p.parent == null) { 
            root = null;
        }
        //1、要删除的结点是叶子结点，此时直接删除即可。（如果删除的是黑色结点，我们要先调整，然后再删除）
        else { 
            //先调整
            if (p.color == BLACK)
                fixAfterDelete(p);
    
            //再删除
            if (p.parent != null) { 
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

> Q：为什么第1种情况是先调整再删除，而第3种情况是先删除再调整？
> 
> A：第1种情况删除的是叶子结点，你如果先删除的话，删除完了，你还有办法再调整吗？显然结点都没了，这是无法调整，那为什么第3种可以呢？因为第3种调整的是`replacement`被替换的那个结点。

### 4.10.2、如何修正 ###

通过上一小节的删除操作，我们会发现删除规则的4种情况中，第2种删除后不用调整，排除他，第4种删除，虽然删除的是有2个孩子的结点，但是我们通过前驱或者后继结点的赋值，然后删除前驱或者后继结点，转化为删除只有1个孩子或者删除叶子结点的情况，因此，我们删除结点时，其实一直都在删除树的倒数第一层和倒数第二层中的结点。我们还会知道，如果你删除的是红色的叶子结点，那么将会直接删除，根本就不会进入到`fixAfterDelete(p);`修正的方法中。

我们把目光放到上一小节的代码块41-42行，这里`fixAfterDelete(replacement);`中的`replacement`结点一定是红色的叶子结点，我为什么这么肯定，请你对比`4.3章`对比表，你就会发现`3-结点`转换为红黑树的结点以后，就是上黑下红，你看41行的判断条件`if (p.color == BLACK)`，这就说明了，当前要删除的结点是黑色，并且当前判断的就是有1个孩子（左/右）的情况，那么这个孩子结点必定是红色叶子结点，如下图：

![c4d3bb3e9adfa50358b385030243100c.png][]

*  当要删除的结点是1时，会让结点3的左子结点指向结点2，此时，树中少了一个黑结点，导致不平衡，为了保证平衡，需要把结点2变为黑色。
 *  当要删除的结点是11时，会让结点9的右子结点指向结点10，此时，树中少了一个黑结点，导致不平衡，为了保证平衡，需要把结点10变为黑色。

因此，上一小节的代码块41-42行，就是为了修正这两种情况，他的实现代码非常简单：

private void fixAfterDelete(Node x) { 
        //那么在此之前要处理的必定是 x != root && colorOf(x) == BLACK
    
        //如果当前结点是红色，那么立即修改为黑色
        //还有一种情况就是为了保证根结点root始终是黑色，因为replacement最后有可能成为根结点
        setColor(x, BLACK);
    }

好了，上一小节的代码块42行`fixAfterDelete(replacement);`处的修正就完成了。接下来，重点说上一小节的代码块52行`fixAfterDelete(p);`的修正。

首先你一定要明确，上一小节的代码块52行`fixAfterDelete(p);`的修正，他只是修正删除的是黑色叶子结点的情况，其余情况在上边都已经完整的讨论过了。

![65e812f33cb42ccaf5733b969cb36ebd.png][]

因为上边已经说了，我们现在实际上删除的一直都是红黑树中的倒数第一层和倒数第二层的结点，他映射到上图1的2-3-4树中是最后一层，也就是说，我们实际上也是在一直删除2-3-4树的倒数第一层，在倒数第一层无非就那几种情况：

*  `2-结点`：4、5、6
 *  `3-结点`：1和2
 *  `4-结点`：10和11和12

`3-结点`和`4-结点`是不是就不用考虑了，因为现在修正的是黑色叶子结点，对应到2-3-4树也就是`2-结点`，这其中，结点还分左右，我们只探讨当要删除的黑色结点是左结点的情况，那么当要删除的结点是右结点的情况也就出来了。

//x是左孩子的情况
    if (x == leftOf(parentOf(x)))

请看图1的结点6和结点8对比到图3中，都是黑色的叶子结点，并且都是左结点，我们重点考虑如何删除他俩。

我们的红黑树是在2-3-4树的基础上演变过来的，因此关于删除的操作，也应该符合2-3-4树的一些特性：除了叶子结点外，其余每层必须要满足相对应的结点数。

*  1、删除结点6，得第一种结论：自己删不掉，找别人，别人管不了，那就一起少

看下图1，当我们删除结点6的时候，这个时候就破坏了2-3-4树的平衡了，原因是7和9所在的`3-结点`要求必须有3个孩子，但是，你把6这个左孩子给删除掉了，他就少了一个孩子，因此就不平衡了。想要保持平衡，自己（也就结点6）他没有办法，他肯定找最亲近的父亲结点7帮忙，把父亲结点直接拉下水，那此时，父亲结点的位置也就空了，然后让结点6最近的兄弟结点8去帮父亲结点的忙，最终变为下图2。你观察，是不是发现此时还是不平衡的，原因是8和9所在的`3-结点`要求必须有3个孩子，但是，现在只有左孩子7和右孩子`10 11 12`这两个孩子，显然不平衡，这就是典型的自己删不掉，找别人，别人还管不了，这里的管不了最终出现问题的地方是在兄弟结点8上，因为兄弟结点8只有1个，借出去了，他就自身难保了。有人可能会问，你咋不找`10 11 12`，`10 11 12`属于远房兄弟，不亲近，根本就过不来，假设你把10要到父亲结点处，就打乱顺序了，此时就变成了`10 9`，所以不行，只能最近的兄弟结点8来帮老父亲结点7的忙；这里还要重申一点，当要删除的结点6是左孩子的时候，只能向右边找人，不能向左边找人。

![58738f410c9ce9300fd9168defb120cd.png][]

经过上图的推论之后，我们再来对比一下下图的图1和图3，你会发现图1中结点6的和结点8是兄弟关系，而图3中结点6和结点9是兄弟关系，这显然存在一定的问题，对应不上了，这个时候，我们就需要对红黑树进行调整，调整到结点6和结点8是兄弟关系，而调整无外乎左旋、右旋和变色。

![65e812f33cb42ccaf5733b969cb36ebd.png][]

而6、7、8、9、11所在的结构明显是需要左旋的，那什么时候左旋呢？看下图1，显然是红黑树中结点6的兄弟结点9是红色的时候进行左旋，假设结点6为x，旋转完以后还需要进行变色，看下图2，旋转完以后，`6 7 8`组成了一个新的2-3-4树的`4-结点`，而`4-结点`对应红黑树结点应该是上红下黑，忘了的看`4.3章`对比表，而9是2-3-4树中的`2-结点`，对应到红黑树中是黑色，因此需要变色。经过调整后就找到了结点6的真正兄弟结点8，然后修改兄弟结点的指向就行了。

//获取当前的兄弟结点
    Node brother = rightOf(parentOf(x));
    
    //找到真正的兄弟结点
    if (colorOf(brother) == RED) { 
        setColor(brother, BLACK);
        setColor(parentOf(x), RED);
        rotateLeft(parentOf(x));
        brother = rightOf(parentOf(x));
    }

![14b28d7738c2994dc7caa2ede158ee36.png][]

那如何判断我的兄弟结点帮不了忙呢？不要忘了叶子结点还有左右指向的`NULL LEAF`结点，这两个结点也是黑色，只不过平时不画出来，那么代码就出来了。

//这个兄弟结点帮不了
    if (colorOf(leftOf(brother)) == BLACK && colorOf(rightOf(brother)) == BLACK) { 
    
    }
    //这个兄弟结点帮得了
    else { 
    
    }

既然别人管不了你，你自己删除以后，那么这棵树中肯定就少了一个黑结点，为了保持平衡，你应该让你的兄弟也删除一个黑结点，也就是大家一起少，那这样还是会保持平衡，但是，你兄弟能删除吗？肯定不能真的删除，那只能假删除，怎么办？把兄弟结点变成红色，红色不影响树的平衡，所以一旦兄弟结点变成了红色，就意味着少了一个黑色结点。此时，以你的父结点为根的左右子树就已经平衡了，但是你的父结点之上还有其他结点，此时就需要循环向上依次平衡左右子树，直到当前结点为root的时候，就已经完成了调整。

*  2、删除结点8，得第二种结论：自己删不掉，找别人，别人管得了，别人来帮你

我们通过上边的分析，已经解决了帮不了的问题，那剩下的就是帮得了的问题，所以也就不用判断了，在帮得了的问题中，又细分为两类：在2-3-4树中兄弟结点为`3-结点`和`4-结点`都能提供帮助，并且不破坏当前2-3-4树的平衡。

![fc0dde869a61e3e5d056ae1064a0b23c.png][]

当删除结点8的时候，上图两种情况都可以继续保持平衡，删除完以后如下图：

![d192da9e7b2efd4ade4ae2aa2b1223f3.png][]

由此可见，如果兄弟结点是`3-结点`或者`4-结点`，那么他是可以在老父亲走后，去顶替老父亲的位置而不造成树的失衡。

但是我们现在实际上操纵的是红黑树，`3-结点`对应的红黑树结点可能有两种情况，左倾、右倾，而`4-结点`则只有一种。

对于`3-结点`来说，就有可能有两种情况：

![258ecf0f2de99699e2de17a61dc38610.png][]

对于上图2来说，画圈的地方可以直接左旋，这样就能让结点9替代被删除的结点8，结点10替代老父亲结点，最终如下图：

![0b36ef25391de7ffcdbc7eff893ad5bf.png][]

旋转完成以后，我们需要变色，这个变色是根据什么呢？是根据你删除后当前结点在所对应2-3-4树中的类型，如上图4，结点9和结点11都是`2-结点`，所以必然是黑色，而结点10替代了原来结点9也就是老父亲的位置，那他的颜色就应该是老父亲的颜色才对，因此最终代码：

setColor(brother, colorOf(parentOf(x)));
    setColor(parentOf(x), BLACK);
    setColor(rightOf(brother), BLACK);
    rotateLeft(parentOf(x));

> ps：先变色，还是先旋转不影响最终结果。

> ps：上图3中的结点8根本就没有删除掉，这是正常的，我们是先修正，然后再删除，`fixAfterDelete(p);`只负责修正。

--------------------

对于`3-结点`来说，就有可能有两种情况，已经分析完了下图2这种情况了。

![258ecf0f2de99699e2de17a61dc38610.png][]

接下来继续分析上图3这种情况，很明显，结点8的结点所对应的兄弟结点并不是结点10，因此，我们需要调整结构，此时需要右旋然后变色即可。

![8c96e68cc2a3f1ba4029bd0d0cfefb41.png][]

现在会发现，上图2就变成了右倾的情况了，此时再重新找人帮忙就没问题了。

//判断当前结构是不是需要调整，找到真正的兄弟结点
    if (colorOf(rightOf(brother)) == BLACK) { 
        setColor(leftOf(brother), BLACK);
        setColor(brother, RED);
        rotateRight(brother);
        brother = rightOf(parentOf(x));
    }
    //让老父亲去顶替被删除结点，让亲兄弟去顶替老父亲
    setColor(brother, colorOf(parentOf(x)));
    setColor(parentOf(x), BLACK);
    setColor(rightOf(brother), BLACK);
    rotateLeft(parentOf(x));

到此，`3-结点`的情况就分析完了，`4-结点`就不用分析了，因为`3-结点`已经包括了左右的情况了，直接复用上边的代码块中的代码就行了。

### 4.10.3、修正操作 ###

private void fixAfterDelete(Node x) { 
        //那么在此之前要处理的必定是 x != root && colorOf(x) == BLACK
        while (x != root && colorOf(x) == BLACK) { 
            //x是左孩子的情况
            if (x == leftOf(parentOf(x))) { 
                //获取当前的兄弟结点
                Node brother = rightOf(parentOf(x));
    
                //找到真正的兄弟结点
                if (colorOf(brother) == RED) { 
                    setColor(brother, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    brother = rightOf(parentOf(x));
                }
    
                //这个兄弟结点帮不了
                if (colorOf(leftOf(brother)) == BLACK && colorOf(rightOf(brother)) == BLACK) { 
                    setColor(brother, RED);
                    x = parentOf(x);
                }
                //这个兄弟结点帮得了
                else { 
                    //判断当前结构是不是需要调整，找到真正的兄弟结点
                    if (colorOf(rightOf(brother)) == BLACK) { 
                        setColor(leftOf(brother), BLACK);
                        setColor(brother, RED);
                        rotateRight(brother);
                        brother = rightOf(parentOf(x));
                    }
                    //让老父亲去顶替被删除结点，让亲兄弟去顶替老父亲
                    setColor(brother, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(brother), BLACK);
                    rotateLeft(parentOf(x));
                    //这种情况，调整一次即可，x=root代表跳出当前循环
                    x = root;
                }
            }
            //x是右孩子的情况
            else { 
                //获取当前的兄弟结点
                Node brother = leftOf(parentOf(x));
    
                //找到真正的兄弟结点
                if (colorOf(brother) == RED) { 
                    setColor(brother, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    brother = leftOf(parentOf(x));
                }
    
                //这个兄弟结点帮不了
                if (colorOf(rightOf(brother)) == BLACK && colorOf(leftOf(brother)) == BLACK) { 
                    setColor(brother, RED);
                    x = parentOf(x);
                }
                //这个兄弟结点帮得了
                else { 
                    //判断当前结构是不是需要调整，找到真正的兄弟结点
                    if (colorOf(leftOf(brother)) == BLACK) { 
                        setColor(rightOf(brother), BLACK);
                        setColor(brother, RED);
                        rotateLeft(brother);
                        brother = leftOf(parentOf(x));
                    }
                    //让老父亲去顶替被删除结点，让亲兄弟去顶替老父亲
                    setColor(brother, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(brother), BLACK);
                    rotateRight(parentOf(x));
                    //这种情况，调整一次即可，x=root代表跳出当前循环
                    x = root;
                }
            }
        }
    
        //如果当前结点是红色，那么立即修改为黑色
        //还有一种情况就是为了保证根结点root始终是黑色，因为replacement最后有可能成为根结点
        setColor(x, BLACK);
    }

### 4.10.4、删除测试 ###

修改红黑树的测试：`RedBlackTreeTest`

最终测试效果对比：

![fe720f078d8e145dff83a43a9ddcd0c2.png][]

# 第五章 AVL树 #

## 5.1、AVL树的定义 ##

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

在这里再推荐一个AVL树演示的网站：https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

为了大家方便测试，我们接下来代码实现的效果将会和上述网站演示的效果一样。

## 5.2、AVL树的性质 ##

AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树），具体特点是：

*  本身首先是一棵二叉查找树。
 *  带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

## 5.3、AVL树的结构 ##

public class AdelsonVelskyLandisTree<Key extends Comparable<Key>, Value> { 
        public class Node {                          //结点类
            public Key key;                         //存储键
            public Value value;                     //存储值
            public Node parent;                     //指向父亲结点
            public Node left;                       //指向左子结点
            public Node right;                      //指向右子结点
            public int height;                      //指向结点高度
    
            public Node(Key key, Value value) { 
                this.key = key;
                this.value = value;
                this.height = 1;
            }
    
            @Override
            public String toString() { 
                return "Node{" + "key=" + key + ", value=" + value + ", height=" + height + "}";
            }
        }
    
        private Node root;                          //根结点
        private int size;                           //结点数
    
        //获取当前树的根结点
        public Node getRoot() { 
            return root;
        }
    
        //获取当前树的结点数
        public int size() { 
            return size;
        }
    
        //判断当前树是否为空
        public boolean isEmpty() { 
            return size == 0;
        }
    
        //获取当前结点的父亲结点
        private Node parentOf(Node node) { 
            return node != null ? node.parent : null;
        }
    
        //获取当前结点的左子结点
        private Node leftOf(Node node) { 
            return node != null ? node.left : null;
        }
    
        //获取当前结点的右子结点
        private Node rightOf(Node node) { 
            return node != null ? node.right : null;
        }
    
        //获取当前结点高度
        private int heightOf(Node node) { 
            return node != null ? node.height : 0;
        }
    
        //获取最高的子结点
        private Node tallerOf(Node node) { 
            Node parent = parentOf(node);
            Node left = leftOf(node);
            Node right = rightOf(node);
            if (heightOf(left) > heightOf(right)) return left;
            if (heightOf(left) < heightOf(right)) return right;
            return (left == leftOf(parent)) ? left : right;
        }
    
        //更新当前结点高度
        private void updateHeight(Node node) { 
            if (node != null) { 
                node.height = Math.max(heightOf(leftOf(node)), heightOf(rightOf(node))) + 1;
            }
        }
        
        //接下来的方法请写在这里...
    }

## 5.4、AVL树的操作 ##

### 5.4.1、左旋操作（RR） ###

![13040399241a66db8af91bf39760de85.png][]

**失衡描述：**

当向`node`结点下添加左右子结点时：

*  `node`结点，左子树高度-右子树高度=1-1=0，平衡
 *  `parent`结点，左子树高度-右子树高度=1-2=-1，平衡
 *  `grandpa`结点，左子树高度-右子树高度=1-3=-2，失衡

由于在`grandpa`结点处失衡，因此需要按照`grandpa`结点进行左旋操作。

**核心描述：**

*  获取当前结点h
 *  获取当前结点h的右子结点x
 *  让h的右子结点指向x的左子结点
 *  让x的左子结点指向h结点
 *  调整完成以后，只有h结点和x结点的高度有变化，需要更新高度

**动画演示：**

![dbf9bcfa3fd409eb7bbacf45644b2849.gif][]

**代码实现：**

### 5.4.2、右旋操作（LL） ###

![a76705ee89b91d731fd446153133cac3.png][]

**失衡描述：**

当向`node`结点下添加左右子结点时：

*  `node`结点，左子树高度-右子树高度=1-1=0，平衡
 *  `parent`结点，左子树高度-右子树高度=2-1=1，平衡
 *  `grandpa`结点，左子树高度-右子树高度=3-1=2，失衡

由于在`grandpa`结点处失衡，因此需要按照`grandpa`结点进行右旋操作。

**核心描述：**

*  获取当前结点h
 *  获取当前结点h的左子结点x
 *  让h的左子结点指向x的右子结点
 *  让x的右子结点指向h结点
 *  调整完成以后，只有h结点和x结点的高度有变化，需要更新高度

**动画演示：**

![370fbbe367457fe0d6dcc0ccea4fb00e.gif][]

**代码实现：**

### 5.4.3、左右双旋（LR） ###

![14e1b0d8cc0dcc671e7ae64afc97be1c.png][]

**失衡描述：**

当向`node`结点下添加左右子结点时：

*  `node`结点，左子树高度-右子树高度=1-1=0，平衡
 *  `parent`结点，左子树高度-右子树高度=1-2=-1，平衡
 *  `grandpa`结点，左子树高度-右子树高度=3-1=2，失衡

由于在`grandpa`结点处失衡，因此先按照`parent`结点进行左旋操作，然后再按照`grandpa`结点进行右旋操作。

### 5.4.4、右左双旋（RL） ###

![08cfb68e1fd08578c9735fd426ad9444.png][]

**失衡描述：**

当向`node`结点下添加左右子结点时：

*  `node`结点，左子树高度-右子树高度=1-1=0，平衡
 *  `parent`结点，左子树高度-右子树高度=2-1=1，平衡
 *  `grandpa`结点，左子树高度-右子树高度=1-3=-2，失衡

由于在`grandpa`结点处失衡，因此先按照`parent`结点进行右旋操作，然后再按照`grandpa`结点进行左旋操作。

## 5.5、AVL树的添加 ##

### 5.5.1、添加操作 ###

//添加操作
    public void put(Key key, Value value) { 
        //获取根结点
        Node t = root;
        //判断根结点
        if (t == null) { 
            root = new Node(key, value);
            size++;
            return;
        }
        //找指定位置
        Node parent;
        int cmp;
        do { 
            parent = t;
            cmp = key.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                t.value = value;
        } while (t != null);
        //添加新结点
        Node e = new Node(key, value);
        e.parent = parent;
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        //添加后修正
        fixAfterPut(e);
        //添加后加一
        size++;
    }

### 5.5.2、如何修正 ###

添加后可能会导致所有祖先节点都失衡，只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡，仅需 O(1) 次调整即可。

### 5.5.3、修正操作 ###

//修正操作
    private void fixAfterPut(Node node) { 
        while ((node = parentOf(node)) != null) { 
            if (isBalance(node)) { 
                //平衡后更新结点高度
                updateHeight(node);
            } else { 
                //不平衡以后恢复平衡
                rebalance(node);
                //整棵树恢复平衡退出
                break;
            }
        }
    }
    
    //判断是否平衡
    private boolean isBalance(Node node) { 
        return Math.abs(heightOf(leftOf(node)) - heightOf(rightOf(node))) <= 1;
    }
    
    //平衡当前结点
    private void rebalance(Node grandpa) { 
        Node parent = tallerOf(grandpa);
        Node node = tallerOf(parent);
        if (parent == leftOf(grandpa)) {  // L
            if (node == leftOf(parent)) {  // LL
                rotateRight(grandpa);
            } else {  // LR
                rotateLeft(parent);
                rotateRight(grandpa);
            }
        } else {  // R
            if (node == rightOf(parent)) {  // RR
                rotateLeft(grandpa);
            } else {  // RL
                rotateRight(parent);
                rotateLeft(grandpa);
            }
        }
    }

### 5.5.4、添加测试 ###

添加层序遍历代码：

创建AVL树的测试：`AdelsonVelskyLandisTreeTest`

public class AdelsonVelskyLandisTreeTest { 
        public static void main(String[] args) { 
            AdelsonVelskyLandisTree<Integer, Integer> avlt = new AdelsonVelskyLandisTree<>();
            avlt.put(1, 1);
            avlt.put(2, 2);
            avlt.put(3, 3);
            avlt.put(4, 4);
            avlt.put(5, 5);
            avlt.put(6, 6);
            avlt.put(7, 7);
            avlt.put(8, 8);
            avlt.put(9, 9);
            avlt.put(10, 10);
            avlt.put(11, 11);
            avlt.put(12, 12);
            avlt.layerErgodic();
        }
    }

最终测试效果对比：

![7e06ca70d667c9550c666fe5cf0a24ec.png][]

## 5.6、AVL树的获取 ##

### 5.6.1、获取指定结点 ###

### 5.6.2、获取最小结点 ###

//获取树最小结点
    public Node getMinNode() { 
        Node p = root;
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

### 5.6.3、获取最大结点 ###

//获取树最大结点
    public Node getMaxNode() { 
        Node p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }

### 5.6.4、获取前驱结点 ###

![2798ceb60336947952aa7b57dd506410.png][]

**前驱结点：** 小于当前结点的最大值，在一棵树中，判断前驱结点分为三种情况。

*  第一种情况：要查询的结点为null，此时直接返回null。
 *  第二种情况：要查询的结点不为null，并且左子树不为null，在其左子树中找到最大的那个结点即可。如上图所示：结点8的前驱结点是结点7。
 *  第三中情况：要查询的结点不为null，并且左子树为null，我们就需要循环向上查询其父结点，直到当前结点是父结点的右子结点为止。如上图所示：结点9的前驱结点是结点8，操作顺序：首先结点9是结点10的左子结点，结点10是结点8的右子结点，此时停止，结点8就是前驱结点。

--------------------

### 5.6.5、获取后继结点 ###

![2798ceb60336947952aa7b57dd506410.png][]

**后继结点：** 大于当前结点的最小值，在一棵树中，判断后继结点分为三种情况。

*  第一种情况：要查询的结点为null，此时直接返回null。
 *  第二种情况：要查询的结点不为null，并且右子树不为null，在其右子树中找到最小的那个结点即可。如上图所示：结点8的后继结点是结点9。
 *  第三中情况：要查询的结点不为null，并且右子树为null，我们就需要循环向上查询其父结点，直到当前结点是父结点的左子结点为止。如上图所示：结点7的后继结点是结点8，操作顺序：首先结点7是结点6的右子结点，结点6是结点4的右子结点，结点4是结点8的左子结点，此时停止，结点8就是后继结点。

--------------------

## 5.7、AVL树的删除 ##

### 5.7.1、删除操作 ###

//删除操作
    public Value delete(Key key) { 
        Node p = getNode(key);
        if (p == null)
            return null;
        Value oldValue = p.value;
        deleteNode(p);
        return oldValue;
    }
    
    //真正删除
    private void deleteNode(Node p) { 
        size--;
    
        //4、要删除的结点有2个孩子，肯定有左孩子，肯定有右孩子
        if (p.left != null && p.right != null) { 
            //找到前驱结点，然后替换要删除结点的键值
            Node s = predecessor(p);
            p.key = s.key;
            p.value = s.value;
            //替换完成以后，指向前驱结点为删除做准备
            p = s;
        }
    
        //3、要删除的结点有1个孩子，可能有左孩子，可能有右孩子
        Node replacement = (p.left != null ? p.left : p.right);
        if (replacement != null) { 
            //让左右子结点连接到p的父结点上
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left = replacement;
            else
                p.parent.right = replacement;
    
            //释放当前p结点所有指向等待回收
            p.left = p.right = p.parent = null;
    
            //删除完成以后，我们需要进行平衡
            fixAfterDelete(p);
        }
        //2、要删除的结点是树根结点，此时直接删除即可
        else if (p.parent == null) { 
            root = null;
        }
        //1、要删除的结点是叶子结点，此时直接删除即可
        else { 
            //先删除
            if (p.parent != null) { 
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                // p.parent = null;
            }
            //再调整
            fixAfterDelete(p);
        }
    }

### 5.7.2、如何删除 ###

删除后可能会导致父节点或祖先节点失衡（但只有1个节点会失衡），恢复平衡后，可能会导致更高层的祖先节点失衡，最多需要 O(logn) 次调整。

### 5.7.3、修正操作 ###

//修正操作
    private void fixAfterDelete(Node node) { 
        while ((node = parentOf(node)) != null) { 
            if (isBalance(node)) { 
                //平衡后更新结点高度
                updateHeight(node);
            } else { 
                //不平衡以后恢复平衡
                rebalance(node);
            }
        }
    }

### 5.7.4、删除测试 ###

修改AVL树的测试：`AdelsonVelskyLandisTreeTest`

最终测试效果对比：

![9b13a12982561a2b6c635110c6c35f81.png][]

[665cf9558ee9e9986ad46ed72e9fb5f0.png]: /images/20221022/ee7ca25f19064a7f852dd25ebb1e9be5.png
[eb6090687332a30999831a5a8fd55d59.png]: /images/20221022/62309be216514cdcb82004def42a429a.png
[f46601ba4647455497942c6ec2b60393.png]: /images/20221022/6377a3b047644489b81e267e76550900.png
[a6cc1c8793d2335420149a1f33d6f9c4.png]: /images/20221022/c2b7c3d9884f44b29ea82f61a3448bfe.png
[f03d4bd02ef4fa43c8bfe60d5be34189.png]: /images/20221022/8bcacb44b3f343089242453b1d5f81d3.png
[bbe030af54ffc3bda0c6822cd8b14d2e.png]: /images/20221022/b8fa8be6090f44cda9625f1616f61a5b.png
[866f2b03282b5942928310e36ab360d8.png]: /images/20221022/b5cf03ee31d94438b7682a53866f85d0.png
[59dc8a1de587b1b7f42ec58f79ecabe0.png]: /images/20221022/03845f35f56f43daadcad02c3bc46040.png
[cd91427725ae7305c1af1e4f0d565332.png]: /images/20221022/35a9591724c148b98f90731be5a525e1.png
[e83f93513329aed45f93b647255b9520.png]: /images/20221022/7ff1fa39dce5405ea6dc7ad1d51c7adf.png
[09ca09fa9b4464ffd49408a562b850df.png]: /images/20221022/b02020a9a1fa489c966ca91f19ac7dcd.png
[39663bd7eddcaffeb1c6e4c7dfe87b2d.png]: /images/20221022/cc4a567a26744e1baffeb6fb17e855b6.png
[c0983fb0060c47c6291d95d332d609a5.png]: /images/20221022/ac27f551f46640e5876079f4e7e2ed27.png
[f8f7f09887e6422fb585b255a224a19b.png]: /images/20221022/ec7cf0f1390e49bab3d2eb404f6ba682.png
[37eb516cdf887776d2ebc194cebf75ef.png]: /images/20221022/b2f0ba8b05664aaf99371373ed38bc2b.png
[0031b98953ebbe0c78f8ca06e1df0589.png]: /images/20221022/d1df4ab2ec9a4c5a880326a1fac9a5bb.png
[a29ab0d0d701d2e1a33f8a39529eb502.png]: /images/20221022/51843d99d3034f3d9c71cc8e025c59c4.png
[c7d49ea2a3da0e6708f1fe1635b2f191.png]: /images/20221022/b8bc53a0caa7490f8b0583ab0a8c9bcc.png
[3a17d2adbe9dbeb3437a114b22041e02.png]: /images/20221022/dda6d2b6f2b747fe8c9a9eda9a1b6e23.png
[a33d421221bd7a1c327d426602ab84dd.png]: /images/20221022/43deba2928084261ad706364c512c490.png
[285c439212c59bc18771881841a095bc.png]: /images/20221022/9d52149a446648b2ab684956e77b8d3a.png
[abc2d59b29fbf9fba4e1d668fbdc1349.png]: /images/20221022/e073113a9bd54792b70f86b00117fed8.png
[147b8fd1a70462d9725f40951c5e544b.png]: /images/20221022/726d5197da7f4b9f96c0a9c002cd6117.png
[a936c16d614762c859f9e4e2c1d046f6.png]: /images/20221022/8ba6c74658c74c52b3c88d7eb21c50aa.png
[b833ca182c67c88f1f1ee0addec661ba.png]: /images/20221022/cd357b786d7540c8b4de974297ddaea9.png
[8276a201cc00b6cd7eb1abaeeabe0fe9.png]: /images/20221022/3dc052488b8443ee9209e5a4d2a4feed.png
[a5afdc87dc8984b04bfb94f5262e59d4.png]: /images/20221022/41ab5dd8a87a4dd7be03e1d659174298.png
[eb39438fef97f376ad29e98c412c2845.png]: /images/20221022/c103bce89f8d46198e6533901cd3b580.png
[f261c474137c452125c3f04568793540.png]: /images/20221022/79ef9990cf3b4278a0c6711b5ef3d1c7.png
[d6b75d503e39d6829d93b5beade03c6a.png]: /images/20221022/cc8671bcd9da408094f73b68db9ec93e.png
[fa0bb4fbd6204571f16a2a0f126bf514.png]: /images/20221022/a2ec2d846f7f42a082655365a19a4299.png
[5a2652bec698bb730f983064e703ecd4.png]: /images/20221022/7c6f0aaee81d44ae9602ac30cad349c2.png
[111856749c223cd385a52408580bac5e.png]: /images/20221022/907b36118ca14fc7b2886eb277bbf3c8.png
[3e59b69e0e8b821a93a4945aba4787a7.png]: /images/20221022/94851368393a4c139cb292be929905c2.png
[8df7d84574e6636063eb8ecd0b8fca9d.png]: /images/20221022/063c63e5f47f4c91b124eba4f233b25e.png
[fe9dde082206687cb37d2d130a8ef07f.png]: /images/20221022/e976f41449204b96a4886a401974964c.png
[1cff4ba3ce2cdfed5421c521c52dc124.png]: /images/20221022/6fea0fd49fd74b3482082b2f54b497ef.png
[8738265b8eae749fd6175e8f2d3b2611.png]: /images/20221022/678c8fd048f6479098c6196e5c465e47.png
[dbf9bcfa3fd409eb7bbacf45644b2849.gif]: /images/20221022/678277d579e9480ba93abe6f29d2ed90.png
[35a541327b49f6e9722f5d8a5cbb94f7.png]: /images/20221022/b848960cd1534f47a6a100307c3d577c.png
[370fbbe367457fe0d6dcc0ccea4fb00e.gif]: /images/20221022/145c5c481c3143da934b4098b9b91fb1.png
[cacf5b81c0efd9cdc26fac169d2d6822.png]: /images/20221022/feb47d7c593a4deeac32605609e2fda7.png
[7fd62b556c5cfa3eb95d272e92c755e5.png]: /images/20221022/14f80f004f444bd3972526b0f03e8a4d.png
[5738722ade0b14c2fc4489240dc07641.png]: /images/20221022/a98d3571d48c45a585e678ca4db25004.png
[79c171b824b1de7c995a86af21e13ab0.png]: /images/20221022/ce95f8c2b62b4f2b8de95f612bb3ca24.png
[8391d78fdaa00a934e26a7bbef404d72.png]: /images/20221022/fbcca2f119aa4771ab43d744f7192722.png
[9c7ecefb7879e11c208c5ae653a82fc3.png]: /images/20221022/7eed7a459826460eac525086c26bf723.png
[7ad85da7e61812f968cd6227c892f1da.png]: /images/20221022/2e940c46e27741a6a1d05b0df9a5e83d.png
[c4d3bb3e9adfa50358b385030243100c.png]: /images/20221022/fbd196a1a049443f977ce7eddb2308f6.png
[65e812f33cb42ccaf5733b969cb36ebd.png]: /images/20221022/7e3c1fbc55a74af7b08e55a709634f8e.png
[58738f410c9ce9300fd9168defb120cd.png]: /images/20221022/2fc3f04991c941f8af41b851021d3446.png
[14b28d7738c2994dc7caa2ede158ee36.png]: /images/20221022/572f79dc7ecb48ecba58ae00906d0669.png
[fc0dde869a61e3e5d056ae1064a0b23c.png]: /images/20221022/c536aade7e4a454db872cb4cf4ab4335.png
[d192da9e7b2efd4ade4ae2aa2b1223f3.png]: /images/20221022/6605fb098dec4c419ebc5edd6c41bc64.png
[258ecf0f2de99699e2de17a61dc38610.png]: /images/20221022/4aa66a03c7d7420b968e243ec5ef195f.png
[0b36ef25391de7ffcdbc7eff893ad5bf.png]: /images/20221022/27bc492caa3a4f868e2dcd2cc95fc3c0.png
[8c96e68cc2a3f1ba4029bd0d0cfefb41.png]: /images/20221022/3da2ba57719d4040a1139d327fea2ec2.png
[fe720f078d8e145dff83a43a9ddcd0c2.png]: /images/20221022/c043e2dfcdbe456a8ea060b5d01c2b2f.png
[13040399241a66db8af91bf39760de85.png]: /images/20221022/5edf585435da4d3aa6e929762a9ad9eb.png
[a76705ee89b91d731fd446153133cac3.png]: /images/20221022/37a8cf82a3244c4b8303c78683018d90.png
[14e1b0d8cc0dcc671e7ae64afc97be1c.png]: /images/20221022/cad00f70096743f992b9f7aae545ae14.png
[08cfb68e1fd08578c9735fd426ad9444.png]: /images/20221022/6a5d1870d21c43e09dc49e2d484b1ddc.png
[7e06ca70d667c9550c666fe5cf0a24ec.png]: /images/20221022/5e7f0d0613954ffd9c8a422e8b452a29.png
[2798ceb60336947952aa7b57dd506410.png]: https://img-blog.csdnimg.cn/img_convert/2798ceb60336947952aa7b57dd506410.png
[9b13a12982561a2b6c635110c6c35f81.png]: https://img-blog.csdnimg.cn/img_convert/9b13a12982561a2b6c635110c6c35f81.png