排序二叉树和平衡二叉树

2020 年 9 月 29 日
笔记
数据结构和算法

概述

对于一组元素 [7, 3, 10, 12, 5, 1, 9] 可以有很多种存储方式，但无论使用哪种数据结构，都或多或少有缺陷。比如使用线性结构存储，排序方便，但查找效率低。二叉排序树的特点就是能在保证元素有序的同时，提高查找的效率。

二叉排序树的定义

二叉排序树，也叫二叉查找树，二叉搜索树，英文名 Binary Sort Tree（BST）。它或者是一颗空树，或者是一颗具有以下性质的二叉树

若左子树不为空，则左子树上所有结点的值均小于它的根结点的值
若右子树不为空，则右子树上所有结点的值均大于它的根结点的值
左、右子树也分别为二叉排序树

序列 [7, 3, 10, 12, 5, 1, 9] 以二叉排序树存储的结构如图：

创建二叉排序树 & 添加 & 查找 & 遍历

值得注意的是，对二叉排序树作中序遍历，结果正好是一个有序序列。

public class Node {

    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    /**
     * 向子树添加结点
     * @param node 要添加的结点
     */
    public void add(Node node) {
        if (node != null) {
            // 添加的结点比当前结点的值小
            if (node.value < this.value) {
                // 左结点为空
                if (this.left == null) {
                    this.left = node;
                } else {
                    // 左结点不为空
                    this.left.add(node);
                }
            // 添加的结点比当前结点的值大
            } else {
                // 右结点为空
                if (this.right == null) {
                    this.right = node;
                    // 右结点不为空
                } else {
                    this.right.add(node);
                }
            }
        }
    }

    /**
     * 中序遍历
     */
    public void midShow() {
        // 输出左结点内容
        if (left != null) {
            left.midShow();
        }
        // 输出当前结点内容
        System.out.println(value);
        // 输出右结点内容
        if (right != null) {
            right.midShow();
        }
    }

    /**
     * 查找结点
     * @param value 目标结点的值
     * @return  目标结点
     */
    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) {
                return null;
            }
            return left.search(value);
        } else {
            if (right == null) {
                return null;
            }
            return right.search(value);
        }
    }
}

public class BinarySortTree {

    private Node root;

    /**
     * 向二叉排序树添加结点
     * @param node
     */
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    /**
     * 中序遍历
     */
    public void midShow() {
        if (root != null) {
            root.midShow();
        }
    }

    /**
     * 查找结点
     * @param value 目标结点的值
     * @return  目标结点
     */
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }
}

删除结点

二叉排序树的删除操作相对麻烦些，我们不能像以前那样直接删除结点对应的整个子树，而是要把子结点保留下来，并重新拼接成新的排序二叉树。针对不同的情况，也有不同的应对策略：

删除叶子结点。直接砍掉就好了，不会对其他结点有影响。
删除只有一个子结点的结点。子结点代替原结点的位置。
删除有两个子结点的结点。被删除结点同时也是对应二叉排序子树的根结点，根据二叉排序树的性质，根结点就是序列的中间值，所以要补上中间值的位置，要用中间值的后一位的元素（对应右子树的最小结点）或前一位元素（对应左子树的最大结点）

public class BinarySortTree {

    private Node root;

	......

    /**
     * 删除结点
     * @param value 要删除结点的值
     */
    public void delete(int value) {
        if (root != null) {
            // 找到目标结点
            Node target = search(value);
            if (target != null) {
                // 找到目标结点的父结点
                Node parent = searchParent(value);
                // 要删除的结点是叶子结点
                if (target.left == null && target.right == null) {
                    // 要删除的结点是父结点的左子结点
                    if (parent.left.value() == value) {
                        parent.left = null;
                    // 要删除的结点是父结点的右子结点
                    } else {
                        parent.right = null;
                    }
                // 要删除的结点有两个子结点
                } else if (target.left != null && target.right != null) {
                    // 删除右子树中值最小的结点，并获取该结点的值
                    int min = deleteMin(target.right);
                    // 替换目标结点的值
                    target.value = min;
                // 要删除的结点只有一个子结点
                } else {
                    // 有左子结点
                    if (target.left != null) {
                        // 要删除的结点是父结点的左子结点
                        if (parent.left.value() == value) {
                            // 父结点的左子结点指向目标结点的左子结点
                            parent.left = target.left;
                        // 要删除的结点是父结点的右子结点
                        } else {
                            // 父结点的右子结点指向目标结点的左子结点
                            parent.right = target.left;
                        }
                    // 有右子结点
                    } else {
                        // 要删除的结点是父结点的左子结点
                        if (parent.left.value == value) {
                            // 父结点的左子结点指向目标结点的左子结点
                            parent.left = target.right;
                        // 要删除的结点是父结点的右子结点
                        } else {
                            parent.right = target.right;
                        }
                    }
                }
            }
        }
    }

    /**
     * 删除最小值结点
     * @param node  目标二叉树的根结点
     * @return 最小值
     */
    public int deleteMin(Node node) {

        Node target = node;
        while (target.left != null) {
            target = target.left();
        }
        delete(target.value);
        return target.value;
    }

    /**
     * 查找父结点
     * @param value 目标父结点的子结点的值
     * @return 目标父结点
     */
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }
}

public class Node {

    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

	......

    /**
     * 查找结点
     * @param value 目标结点的值
     * @return  目标结点
     */
    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) {
                return null;
            }
            return left.search(value);
        } else {
            if (right == null) {
                return null;
            }
            return right.search(value);
        }
    }

    /**
     * 查找父结点
     * @param value 目标父结点的子结点的值
     * @return 目标父结点
     */
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (this.left != null && this.value > value) {
                return this.left.searchParent(value);
            } else if (this.right != null && this.value < value) {
                return this.right.searchParent(value);
            } else {
                return null;
            }
        }
    }
}

平衡二叉树

上述的排序二叉树，如果结构良好，那么检索数据时的时间开销为 O(logn)，其中 n 为结点个数。但如果排序二叉树的结构畸形，那么最坏时间开销可能为 O(n)，如下图所示：

这样也满足二叉排序树的定义，但和单链表无异，如果是这样的话，那使用排序二叉树还有什么意义呢？所以我们下一步要思考的是如何保证一颗排序二叉树结构良好

平衡二叉树，也叫 AVL 树，除了具有二叉排序树的性质以外，它要求每一个结点的左右子树的高度之差的绝对值不超过一

每一次插入新元素后，树的平衡都有可能被破坏，因此每次插入时都要通过旋转来维持平衡二叉树的结构。假设需平衡的结点为 8，那么破坏平衡的情况有四种：

左左：对 8 的左儿子的左子树进行一次插入
左右：对 8 的左儿子的右子树进行一次插入
右左：对 8 的右儿子的左子树进行一次插入
右右：对 8 的右儿子的右子树进行一次插入

要解决上述的问题，找到距离新插入结点最近的不平衡子树进行旋转，对于左左情况使用右旋转，右右情况使用左旋转，可以统称为单旋转。左右和右左情况则使用双旋转。左旋转和右旋的旋转方式是互为镜像的，掌握其中一个，另一个自然也会了。左右、右左也是如此

以左左为例讲解单旋转：

找到最近的不平衡子树 8
创建一个新结点，值等于当前结点的值，即是 8
把新结点的右子树设置为当前结点的右子树，即是 9
把新结点的左子树设置为当前结点的左子树的右子树，即是 7，到这里得出下面结果
再接下来目的就很明确了，将 6 当作根结点，新结点作为 6 的右儿子，这样就完成了一次右旋转，可以想象成 8 向右转了一个角度

双旋转其实就是做两次旋转，对于左右情况，先对 6 做一次左旋转，然后才是 8 做一次右旋转；对于右左情况，先对 8 做一次右旋转，然后才是 5 做一次左旋转

代码实现如下：

public class AVLNode {

    int value;
    AVLNode left;
    AVLNode right;

    public AVLNode(int value) {
        this.value = value;
    }

    /**
     * 返回当前结点的高度
     * @return 当前结点的高度
     */
    public int getHeight() {
        return Math.max(left == null ? 0 : left.getHeight(),
                right == null ? 0 : right.getHeight()) + 1;
    }

    /**
     * 获取左子树的高度
     * @return 左子树的高度
     */
    public int getLeftHeight() {
        if (left == null) {
            return 0;
        }
        return left.getHeight();
    }

    /**
     * 获取右子树的高度
     * @return 右子树的高度
     */
    public int getRightHeight() {
        if (right == null) {
            return 0;
        }
        return right.getHeight();
    }

    /**
     * 向子树添加结点
     * @param node 要添加的结点
     */
    public void add(AVLNode node) {
        if (node != null) {
            // 添加的结点比当前结点的值小
            if (node.value < this.value) {
                // 左结点为空
                if (this.left == null) {
                    this.left = node;
                    // 左结点不为空
                } else {
                    this.left.add(node);
                }
                // 添加的结点比当前结点的值大
            } else {
                // 右结点为空
                if (this.right == null) {
                    this.right = node;
                    // 右结点不为空
                } else {
                    this.right.add(node);
                }
            }
        }
        // 判断是否平衡
        // 进行右旋转
        if (getLeftHeight() - getRightHeight() >= 2) {
            // 双旋转
            if (left != null && left.getLeftHeight() < left.getRightHeight()) {
                // 先左旋转
                left.leftRotate();
                // 再右旋转
                rightRotate();
            } else {
                // 单旋转
                rightRotate();
            }
        }
        // 进行左旋转
        if(getLeftHeight() - getRightHeight() <= -2) {
            if (right != null && right.getRightHeight() < right.getLeftHeight()) {
                // 先右旋转
                right.rightRotate();
                // 再左旋转
                leftRotate();
            } else {
                // 单旋转
                leftRotate();
            }
        }
    }

    /**
     * 左旋转
     */
    private void leftRotate() {
        AVLNode node = new AVLNode(value);
        node.left = left;
        node.right = right.left;
        value = right.value;
        right = right.right;
        left = node;
    }

    /**
     * 右旋转
     */
    private void rightRotate() {
        // 创建一个新结点，值等于当前结点的值
        AVLNode node = new AVLNode(value);
        // 把新结点的右子树设置为当前结点的右子树
        node.right = right;
        // 把新结点的左子树设置为当前结点的左子树的右子树
        node.left = left.right;
        // 把当前结点的值换为左子结点的值
        value = left.value;
        // 把当前结点的左子树设置为左子树的左子树
        left = left.left;
        // 把当前结点的右子树设置为新结点
        right = node;
    }

    /**
     * 查找结点
     * @param value 目标结点的值
     * @return  目标结点
     */
    public AVLNode search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) {
                return null;
            }
            return left.search(value);
        } else {
            if (right == null) {
                return null;
            }
            return right.search(value);
        }
    }

    /**
     * 查找父结点
     * @param value 目标父结点的子结点的值
     * @return 目标父结点
     */
    public AVLNode searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (this.left != null && this.value > value) {
                return this.left.searchParent(value);
            } else if (this.right != null && this.value < value) {
                return this.right.searchParent(value);
            } else {
                return null;
            }
        }
    }
}

public class AVLTree {

    private AVLNode root;

    /**
     * 向二叉排序树添加结点
     * @param node
     */
    public void add(AVLNode node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    /**
     * 查找结点
     * @param value 目标结点的值
     * @return  目标结点
     */
    public AVLNode search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    /**
     * 删除结点
     * @param value 要删除结点的值
     */
    public void delete(int value) {
        if (root != null) {
            // 找到目标结点
            AVLNode target = search(value);
            if (target != null) {
                // 找到目标结点的父结点
                AVLNode parent = searchParent(value);
                // 要删除的结点是叶子结点
                if (target.left == null && target.right == null) {
                    // 要删除的结点是父结点的左子结点
                    if (parent.left.value == value) {
                        parent.left = null;
                        // 要删除的结点是父结点的右子结点
                    } else {
                        parent.right = null;
                    }
                    // 要删除的结点有两个子结点
                } else if (target.left != null && target.right != null) {
                    // 删除右子树中值最小的结点，并获取该结点的值
                    int min = deleteMin(target.right);
                    // 替换目标结点的值
                    target.value = min;
                    // 要删除的结点只有一个子结点
                } else {
                    // 有左子结点
                    if (target.left != null) {
                        // 要删除的结点是父结点的左子结点
                        if (parent.left.value == value) {
                            // 父结点的左子结点指向目标结点的左子结点
                            parent.left = target.left;
                            // 要删除的结点是父结点的右子结点
                        } else {
                            // 父结点的右子结点指向目标结点的左子结点
                            parent.right = target.left;
                        }
                        // 有右子结点
                    } else {
                        // 要删除的结点是父结点的左子结点
                        if (parent.left.value == value) {
                            // 父结点的左子结点指向目标结点的左子结点
                            parent.left = target.right;
                            // 要删除的结点是父结点的右子结点
                        } else {
                            parent.right = target.right;
                        }
                    }
                }
            }
        }
    }

    /**
     * 删除最小值结点
     * @param node  目标二叉树的根结点
     * @return
     */
    public int deleteMin(AVLNode node) {

        AVLNode target = node;
        while (target.left != null) {
            target = target.left;
        }
        delete(target.value);
        return target.value;
    }

    /**
     * 查找父结点
     * @param value 目标父结点的子结点的值
     * @return 目标父结点
     */
    public AVLNode searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }
}

Tags: 数据结构和算法