06.二叉查找树&AVL树

写在前面

前面讲了树的基本概念，这篇文章主要讲常见的树的基本操作，如查找，新增，删除等。其中通过动图的方式使得更加容易理解。

二叉查找树

二叉查找树（BST，Binary Sort Tree）,也称二叉排序树，或二叉搜索树。一棵二叉查找树满足以下条件：

• 左子树的所有值均小于根节点的值
• 右子树的所有值均大于根节点的值
• 左右子树同时也满足以上两点

通俗来说就是一棵二叉树，节点左小右大。

插入操作

一棵二叉查找树的插入操作，如果插入的值 x 从根节点开始：

1. x值小于该节点值，在左子树中继续
2. x值大于该节点值，在右子树中继续
3. 如果节点是叶节点，X值小于该节点值则插入左子节点，否则插入右节点

在上面的二叉排序树中，如果我们插入节点的值为 80，具体操作如下：

查找操作

一棵二叉查找树的查找操作，如果查找的值 x 从根节点开始：

1. 如果x小于根节点，则在左子树中继续查找
2. 如果x大于根节点，则在右子树中继续查找
3. 如果x的值等于根节点，则返回该节点
4. 如果都查找不到，则返回null

在上面的二叉排序树中，如果我们需要查找节点的值为10的节点，具体操作如下：

遍历树

树的遍历有三种方法。前序（preorder），中序（inorder），后序（postorder）。

前序遍历

中序遍历

后序遍历

最大值和最小值

最小值：找到根节点的左子节点，一直向左查找直到没有左子节点的节点即为最小节点

最大值：找到根节点的右子节点，一直向右查找直到没有右子节点的节点即为最小节点

删除操作

该节点是叶子节点

结点为叶子结点时，直接删除，把父节点指向子节点的引用设为null。

一棵二叉查找树的删除操作，如果删除的值 x 从根节点开始：

1. 如果节点的值等于 x，则删除
2. x值小于该节点值，在左子树中继续
3. x值大于该节点值，在右子树中继续

如果我们删除节点的值为 80，具体操作如下：

该节点有一个子节点

节点有一个子节点，分两种情况，判断是父节点的左子结点还是右子节点，把父节点的引用指向结点的子节点（子节点也要分左右子节点情况，相当于一共四种情况）

左左左：即删除节点在根节点的左边，且删除节点在其父节点的左边，且删除节点的子节点为左子节点

左右左：即删除节点在根节点的左边，且删除节点在其父节点的右边，且删除节点的子节点为左子节点

右右右：即删除节点在根节点的右边，且删除节点在其父节点的右边，且删除节点的子节点为右子节点

右左右：即删除节点在根节点的右边，且删除节点在其父节点的左边，且删除节点的子节点为右子节点

该节点有两个子节点

由于二叉搜索树的特性，保证了某个结点的左子树的值都小于该节点，右子树的值都大于该节点，只需找到左子树中的最大值或者右子树中的最小值（也叫作中续后继节点）来替换该结点，即可保证节点删除后任为二叉搜索树。

后继节点

在二叉查找树中，节点是按照左小右大的方式排列的，对任意一个节点来说，比该节点的值次高的节点为它的中续后继，简称为后继节点。由于左侧节点总小于右侧节点及父节点，所以后继节点没有左子节点，可能存在右子节点。通过后继节点来替换该结点，即可保证节点删除后仍为二叉搜索树。

查找方式也分为2种

若使用左子树中的最大值来替换

若使用右子树的最小值（后继节点）来替换

代码实现

public class BSTTree {
    /**
     * 节点
     */
    public static class Node {
        //数据，为简化代码，本程序默认节点里存储一个int变量，实际程序里可以存储自定义类型变量
        int data;
        //左子节点
        Node leftChild;
        //右子节点
        Node rightChild;
        public Node(int data) {
            this.data = data;
        }
        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", leftChild=" + leftChild +
                    ", rightChild=" + rightChild +
                    '}';
        }
    }
    /**
     * 新增节点  采用递归的方式
     *
     * @param root 根节点
     * @param data 插入的数据
     * @return
     */
    public static Node insert(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        //若插入的数据小于根节点，插入到其左子树
        if (data <= root.data) {
            root.leftChild = insert(root.leftChild, data);
        } else {
            //插入到其右子树
            root.rightChild = insert(root.rightChild, data);
        }
        return root;
    }
    /**
     * 前序遍历
     *
     * @param root
     */
    public static void preOrder(Node root) {
        if (root != null) {
            System.out.println(root.data + "->");
            preOrder(root.leftChild);
            preOrder(root.rightChild);
        }
    }
    /**
     * 中序遍历
     *
     * @param root
     */
    public static void inOrder(Node root) {
        if (root != null) {
            inOrder(root.leftChild);
            System.out.print(root.data + "->");
            inOrder(root.rightChild);
        }
    }
    /**
     * 后序遍历
     *
     * @param root
     */
    public static void postOrder(Node root) {
        if (root != null) {
            postOrder(root.leftChild);
            postOrder(root.rightChild);
            System.out.print(root.data + "->");
        }
    }
    /**
     * 查找数据
     *
     * @param data
     * @return
     */
    public static Node find(Node root, int data) {
        //若查找的数据小于根节点，则向左查找（也可以采用递归的方式查找）
        Node current = root;
        while (current != null) {
            if (data < current.data) {
                current = current.leftChild;
            } else if (data > current.data) {
                //向右查找
                current = current.rightChild;
            } else {
                return current;
            }
        }
        return null;
    }
    /**
     * 最小值
     *
     * @param root
     * @return
     */
    public static Node minimum(Node root) {
        if (root == null) {
            return null;
        }
        while (root.leftChild != null) {
            root = root.leftChild;
        }
        return root;
    }
    /**
     * 最大值
     *
     * @param root
     * @return
     */
    public static Node maximum(Node root) {
        if (root == null) {
            return null;
        }
        while (root.rightChild != null) {
            root = root.rightChild;
        }
        return root;
    }
    /**
     * 删除节点
     * 1.该节点是叶子节点，即没有子节点
     * 2.该节点有一个子节点
     * 3.该节点有两个子节点（通过该节点的中续后继节点来代替需要删除的节点，
     * 因为后继节点比删除节点的右节点都小，比删除节点的左节点都大）
     * 中续后继节点：比该节点值次高的节点为中续后继节点，如节点2的后继节点为3
     *       4
     *      / \
     *    2    6
     *   / \  / \
     *  1  3  5  8
     *
     * @param root
     * @param data 要删除的节点的值
     */
    public static boolean delete(Node root, int data) {
        //用来表示要删除节点的父节点
        Node parent = null;
        //需要删除的节点是否为父节点的左子节点
        boolean ifLeftChild = true;
        //需要删除的节点
        Node current = root;
        //定位删除节点的位置及其父节点
        while (true) {
            if (data == current.data) {
                break;
            } else if (data < current.data) {
                ifLeftChild = true;
                parent = current;
                current = current.leftChild;
            } else if (data > current.data) {
                ifLeftChild = false;
                parent = current;
                current = current.rightChild;
            }
            //若找不到直接返回fasle
            if (current == null) {
                return false;
            }
        }
        //1.该节点是叶子节点
        if (current.leftChild == null && current.rightChild == null) {
            //若为根节点,删除整棵树
            if (current == root) {
                root = null; //GC
            }
            //若为左子节点
            if (ifLeftChild) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
        }
        //2.该节点有一个子节点
        if (current.leftChild != null && current.rightChild == null) {//若删除节点的左子节点不为null
            //如果该节点为根节点，将根节点的左子节点变为根节点
            if (current == root) {
                root = current.leftChild;
            }
            if (ifLeftChild) {
                //左左左：若该节点为父节点的左子节点，则该节点的左子节点变为父节点的左子节点
                parent.leftChild = current.leftChild;
            } else {
                //左右左：若该节点为父节点的左子节点，则该节点的左子节点变为父节点的右子节点
                parent.rightChild = current.leftChild;
            }
        } else if (current.leftChild == null && current.rightChild != null) {
            if (current == root) {
                root = current.rightChild;
            }
            if (ifLeftChild) {
                //右左右：若该节点为父节点的左子节点，则该节点的右子节点变为父节点的左子节点
                parent.leftChild = current.rightChild;
            } else {
                //右右右：若该节点为父节点的右子节点，则该节点的右子节点变为父节点的右子节点
                parent.rightChild = current.rightChild;
            }
        }
        //3.该节点有两个子节点，这里通过后继节点的方式删除
        if (current.leftChild != null && current.rightChild != null) {
            //获取删除节点且重新构建的后继结点
            Node successor = getSuccessor(current);
            if (root == current) {
                root = successor;
            } else if (ifLeftChild) {
                parent.leftChild = successor;
            } else {
                parent.rightChild = successor;
            }
        }
        return true;
    }
    /**
     * @param node 要删除的节点(假设此时该节点存在右子节点)
     * @return 删除节点的后继节点
     */
    public static Node getSuccessor(Node node) {
        //node节点的左子节点
        Node leftChild = node.leftChild;
        //定义后继节点的父节点
        Node successorParent = node;
        //定义后继节点
        Node successor = node;
        //定义一个临时变量current，先获取删除节点的右子节点，然后再获取右子节点的最小值
        Node current = node.rightChild;
        //这一步就是查找删除节点的后继节点
        while (current != null) {
            //找到后继几点的父节点
            successorParent = successor;
            successor = current;
            //获取右子节点的最小值,直左子树的左子节点为null说明该节点就是删除节点的右子节点的最小值
            current = current.leftChild;
        }
        //找到后继节点之后重新构建后继节点树
        if (current != node.rightChild) {
            /* 后继节点的父节点的左子节点由原来的后继节点变为原来后继点的右子节点（因为左子节点的值始终小于父节点的值）
             * 如下55若为后继节点提出去后，58就变为了60的左子节点
             *       60                          55
             *      / \                            \
             *    55  80      ---重新构建---        60
             *     \                              / \
             *     58                            58 80
             */
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = node.rightChild;
            successor.leftChild = leftChild;
        }
        return successor;
    }
    public static void main(String[] args) {
        /*
         * 新增操作
         *       4
         *      / \
         *    2    6
         *   / \  / \
         *  1  3  5  8
         *          /
         *         7
         */
        Node root = null;
        root = insert(root, 4);
        root = insert(root, 2);
        root = insert(root, 1);
        root = insert(root, 3);
        root = insert(root, 6);
        root = insert(root, 5);
        root = insert(root, 8);
        root = insert(root, 7);
//        root = insert(root, 50);
//        root = insert(root, 25);
//        root = insert(root, 15);
//        root = insert(root, 35);
//        root = insert(root, 5);
//        root = insert(root, 20);
//        root = insert(root, 30);
//        root = insert(root, 40);
        //delete(root, 25);
        inOrder(root);
//        System.out.println("---------");
//        //查找操作 4
//        Node node = find(root, 4);
//        printTree(node);
//        System.out.println("---------");
//        //删除操作
//        Node delete = delete(root, 4);
//        printTree(delete);
    }
    /**
     * 打印
     *
     * @param root
     */
    public static void printTree(Node root) {
        System.out.println("根节点" + root.data);
        if (root.leftChild != null) {
            System.out.print("左子节点:");
            printTree(root.leftChild);
        }
        if (root.rightChild != null) {
            System.out.print("右子节点:");
            printTree(root.rightChild);
        }
    }
}

平衡二叉树（AVL）

平衡二叉树（AVL），是一个二叉排序树，同时任意节点左右两个子树的高度差（或平衡因子，简称BF）的绝对值不超过1，并且左右两个子树也满足。

为什么使用平衡二叉树

通过二叉查找树的查找操作可以发现，一棵二叉查找树的查找效率取决于树的高度，如果使树的高度最低，那么树的查找效率也会变高。

如下面一个二叉树，全部由右子树构成

这个时候的二叉树其实就类似于链表，此时的查找时间复杂度为O(n)，而AVL树的查找时间复杂度为O(logn)。之前讲过O(logn)耗时是小于O(n)的，如下：

可参考：常见数据结构的时间复杂度

平衡二叉树的调整

一棵平衡二叉树的插入操作会有2个结果：

如果平衡没有被打破，即任意节点的BF=1，则不需要调整

如果平衡被打破，则需要通过旋转调整，且该节点为失衡节点

一棵失衡的二叉树通过以下调整可以重新达到平衡：

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变

右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

通过旋转最小失衡子树来实现失衡调整：

在一棵平衡二叉树新增节点，在新增的节点向上查找，第一个平衡因子的绝对值超过1（BF>1）的节点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，有可能多棵子树同时失衡，这时只需要调整最小的不平衡子树即可。

看完下面的旋转方式之后再回来看最小失衡子树旋转就很清晰了

LL旋转

向左子树（L）的左孩子（L）插入新节点

插入节点在失衡节点的左子树的左边，经过一次右旋即可达到平衡，如下

• 插入新节点5，旧根节点40为失衡节点

• 旧根节点40为新根节点20的右子树

• 新根节点20的右子树30为旧根节点40的左子树

旋转过程

RR旋转

插入节点在失衡节点的右子树的右边，经过一次左旋即可达到平衡，如下

• 插入新节点60，旧根节点20为失衡节点

• 旧根节点20为新根节点40的左子树

• 新根节点40的左子树30为旧根节点20的右子树

旋转过程

LR旋转

插入节点在失衡节点的左子树的右边，先左旋，再右旋，如下

旋转过程

RL旋转

插入节点在失衡节点的右子树的左边，先右旋，再左旋，如下

旋转过程

代码实现

public class AVLTree {
    //节点
    public static class Node {
        int data; //数据
        Node leftChild; //左子节点
        Node rightChild;//右子节点
        int height; // 记录该节点所在的高度
        public Node(int data) {
            this.data = data;
        }
    }
    //获取节点的高度
    public static int getHeight(Node p){
        return p == null ? -1 : p.height; // 空树的高度为-1
    }
    public static void main(String[] args) {
        Node root = null;
        root = insert(root,40);
        root = insert(root,20);
        root = insert(root,50);
        root = insert(root,10);
        root = insert(root,30);
        //插入节点在失衡结点的左子树的左边
        root = insert(root,5);
        //打印树，按照先打印左子树，再打印右子树的方式
        printTree(root);
    }
    public static void printTree(Node root) {
        System.out.println(root.data);
        if(root.leftChild !=null){
            System.out.print("left:");
            printTree(root.leftChild);
        }
        if(root.rightChild !=null){
            System.out.print("right:");
            printTree(root.rightChild);
        }
    }
    // AVL树的插入方法
    public static Node insert(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data <= root.data) { // 插入到其左子树上
            root.leftChild = insert(root.leftChild, data);
            //平衡调整
            if (getHeight(root.leftChild) - getHeight(root.rightChild) > 1) {
                if (data <= root.leftChild.data) { // 插入节点在失衡结点的左子树的左边
                    System.out.println("LL旋转");
                    root = LLRotate(root); // LL旋转调整
                }else{ // 插入节点在失衡结点的左子树的右边
                    System.out.println("LR旋转");
                    root = LRRotate(root);
                }
            }
        }else{ // 插入到其右子树上
            root.rightChild = insert(root.rightChild, data);
            //平衡调整
            if(getHeight(root.rightChild) - getHeight(root.leftChild) > 1){
                if(data <= root.rightChild.data){//插入节点在失衡结点的右子树的左边
                    System.out.println("RL旋转");
                    root = RLRotate(root);
                }else{
                    System.out.println("RR旋转");//插入节点在失衡结点的右子树的右边
                    root = RRRotate(root);
                }
            }
        }
        //重新调整root节点的高度值
        root.height = Math.max(getHeight(root.leftChild), getHeight(root.rightChild)) + 1;
        return root;
    }
    /**
     * LR旋转
     */
    public static Node LRRotate(Node p){
        p.leftChild = RRRotate(p.leftChild); // 先将失衡点p的左子树进行RR旋转
        return LLRotate(p); // 再将失衡点p进行LL平衡旋转并返回新节点代替原失衡点p
    }
    /**
     * RL旋转
     */
    public static Node RLRotate(Node p){
        p.rightChild = LLRotate(p.rightChild); // 先将失衡点p的右子树进行LL平衡旋转
        return RRRotate(p); // 再将失衡点p进行RR平衡旋转并返回新节点代替原失衡点p
    }
    /*
     * LL旋转
     * 右旋示意图(对结点20进行右旋)
     *      40                       20
     *     /  \                     /  \
     *    20  50                  10   40
     *   /  \        LL旋转       /    / \
     *  10  30                  5    30  50
     *  /
     * 5
     */
    public static Node LLRotate(Node p){ // 40为失衡点
        Node lsubtree = p.leftChild;   //失衡点的左子树的根结点20作为新的结点
        p.leftChild = lsubtree.rightChild; //将新节点的右子树30成为失衡点40的左子树
        lsubtree.rightChild = p; // 将失衡点40作为新结点的右子树
        // 重新设置失衡点40和新节点20的高度
        p.height = Math.max(getHeight(p.leftChild), getHeight(p.rightChild)) + 1;
        lsubtree.height = Math.max(getHeight(lsubtree.leftChild), p.height) + 1;
        return lsubtree; // 新的根节点取代原失衡点的位置
    }
    /*
     * RR旋转
     * 左旋示意图(对结点20进行左旋)
     *      20                          40
     *     /  \                        /  \
     *    10  40                     20   50
     *       /  \      RR旋转        / \    \
     *      30  50                 10 30   60
     *           \
     *           60
     */
    public static Node RRRotate(Node p){ // 20为失衡点
        Node rsubtree = p.rightChild;  //失衡点的右子树的根结点40作为新的结点
        p.rightChild = rsubtree.leftChild; //将新节点的左子树30成为失衡点20的右子树
        rsubtree.leftChild = p; // 将失衡点20作为新结点的左子树
        // 重新设置失衡点20和新节点40的高度
        p.height = Math.max(getHeight(p.leftChild), getHeight(p.rightChild)) + 1;
        rsubtree.height = Math.max(getHeight(rsubtree.leftChild), getHeight(rsubtree.rightChild)) + 1;
        return rsubtree; // 新的根节点取代原失衡点的位置
    }
}

总结

能看到这的，都是狠人。其实并不难，主要理解左旋和右旋的概念，我觉得就很清晰了。这篇也花了我一整天时间，基本我也是从0到1去接触的，如果感兴趣可以多研究研究。

更新记录