平衡二叉搜索树

一、定义

平衡二叉搜索树（Balanced Binary Search Tree），通常简称为平衡二叉树，是一种特殊的二叉搜索树（Binary Search Tree），它通过保持树的平衡性来确保各种操作（如查找、插入和删除）的平均时间复杂度为 O(log n)，其中 n 是树中节点的数量。平衡二叉搜索树是对普通二叉搜索树的一种优化，旨在避免出现极端情况下的不平衡，进而提高了整体的性能。

二、特点

平衡性：平衡二叉搜索树保持了左右子树的高度差不超过1的特性，这使得树的高度保持在较低水平，从而提高了各种操作的效率。
二叉搜索树性质：除了保持平衡外，平衡二叉搜索树仍然满足二叉搜索树的基本性质，即左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。
插入和删除操作的平均复杂度：在平衡二叉搜索树中，插入和删除操作的平均时间复杂度为 O(log n)，这是由于树的平衡性质保证了树的高度较低，因此插入和删除操作只需要对树进行少量的调整。

三、分类

常见的平衡二叉搜索树包括：

AVL树：最早被发明的自平衡二叉搜索树，通过旋转操作来保持树的平衡性。
红黑树：一种更加实用的平衡二叉搜索树，用于实现各种数据结构和算法中的字典（dictionary）。
Splay树：一种自适应的二叉搜索树，通过频繁访问节点来提高其在树中的位置，从而实现了较好的平衡性。

四、应用场景

平衡二叉搜索树广泛应用于需要高效的插入、删除和查找操作的场景，例如：

数据库系统中的索引结构；
编辑器中的自动补全功能；
编译器和解释器中的符号表实现；
网络路由表的实现；
文件系统中的文件索引结构。

五、实现

二叉搜索树进行改进

5.1 平衡二叉搜索树

旋转的方式实现

import java.util.Comparator;

/**
 * @Description 平衡二叉搜索树 --旋转的方法
 * @Author lcy
 * @Date 2020/11/25 16:58
 */
public class BalanceBinarySearchTree<E> extends BinarySearchTree<E> {

    public BalanceBinarySearchTree(Comparator<E> comparator){
        super(comparator);
    }

    public BalanceBinarySearchTree(){
        super(null);
    }

    /**
     * 左旋转
     * @param node 需要旋转的节点
     * @author lcy
     * @date 2020/11/18 16:21
     **/
    protected void rotateLeft(Node<E> node){
        //左旋转node节点的右节点--parentNode
        Node<E> parentNode = node.right;
        //需要node节点的右子树改为当前parentNode的左子树
        node.right = parentNode.left;
        //父节点值替换
        if (node.right != null) {
            node.right.parent = node;
        }
        //parent节点的左节点为node节点
        parentNode.left = node;
        //父节点替换
        parentNode.parent = node.parent;
        //node节点的父节点指向--旋转以后子树根节点变换
        if (node.isLeftChild()) {
            parentNode.parent.left = parentNode;
        } else if (node.isRightChild()) {
            parentNode.parent.right = parentNode;
        } else {
            //如果是根节点
            rootNode = parentNode;
        }
        node.parent = parentNode;
    }

    /**
     * 右旋转
     * @param node 需要旋转的节点
     * @author lcy
     * @date 2020/11/18 16:21
     **/
    protected void rotateRight(Node<E> node){
        //左旋转node节点的右节点--parentNode
        Node<E> parentNode = node.left;
        //需要node节点的右子树改为当前parentNode的左子树
        node.left = parentNode.right;
        //父节点值替换
        if (node.left != null) {
            node.left.parent = node;
        }
        //parent节点的左节点为node节点
        parentNode.right = node;
        //父节点替换
        parentNode.parent = node.parent;
        //node节点的父节点指向--旋转以后子树根节点变换
        if (node.isLeftChild()) {
            parentNode.parent.left = parentNode;
        } else if (node.isRightChild()) {
            parentNode.parent.right = parentNode;
        } else {
            //如果是根节点
            rootNode = parentNode;
        }
        node.parent = parentNode;
    }

    /**
     * 统一旋转，旋转以后的最后结果为：
     * ┌──d──┐
     * │     │
     * ┌─b─┐ ┌─f─┐
     * │   │ │   │
     * a   c e   g
     * @param root 原树的根节点
     * @param b    b节点
     * @param c    c节点
     * @param d    d节点
     * @param e    e节点
     * @param f    f节点
     * @author lcy
     * @date 2020/11/19 14:42
     **/
    protected void rotate(Node<E> root,Node<E> b,Node<E> c,Node<E> d,Node<E> e,Node<E> f){
        //设置新的根节点
        d.parent = root.parent;
        if (root.isLeftChild()) {
            root.parent.left = d;
        } else if (root.isRightChild()) {
            root.parent.right = d;
        } else {
            rootNode = d;
        }

        //设置d的左子树
        if (c != null) {
            c.parent = b;
        }
        b.right = c;

        //设置d的右子树
        if (e != null) {
            e.parent = f;
        }
        f.left = e;

        //设置b，f的父节点指向
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;

    }

}

平衡二叉搜索树 ​

一、定义 ​

二、特点 ​

三、分类 ​

四、应用场景 ​

五、实现 ​