平衡二叉搜索树及其java实现

一.什么是平衡二叉搜索树？

在二叉搜索树的基础上：
每个左右子树的高度差为0，此时的二叉树称为完全平衡二叉搜索树。
每个左右子树的高度差不大于1时，此时的二叉树称为AVL树。（就是平衡二叉搜索树）

二.旋转

当树的结构发生变化时（插入，删除节点），它可能变得不符合AVL结构了，所以我们需要旋转来保证树符合AVL结构。

其中心思想是：将从插入点到根节点路径上第一个不满足AVL性质的节点修复。

以插入为例，存在四种情况：

1.在节点的左孩子的左子树插入元素。
例如：我们在9的左孩子的左子树插入7

我们的解决方案是：
1.将9变成8的右子树
2.将8的位置移到9的位置（我个人理解为7，8，9整体向右旋转）
结果图为：

具体实现代码为：

// 1.左左插入  左向右旋转  这是第一步 ，第二步是利用返回的节点进行相关操作即可
    AVLTreeNode SingleRotataLeft(AVLTreeNode X)//X节点为9
    {
        AVLTreeNode W=X.getLeft();
        X.setLeft(W.getRight());
        W.setRight(X);

        X.setHeight(Math.max(Height(X.getLeft()),Height(X.getRight()))+1);
        W.setHeight(Math.max(Height(W.getLeft()),X.getHeight())+1);

        return W;
    }

2.在节点的右孩子的右子树插入元素。
例如：我们在12的右子树插入20

我们的解决方案是：
1.将10变成12的左子树
2.将12的位置移到10的位置（我个人理解为10，12，20整体向右旋转）
结果图为：

代码如下：

//2. 右右插入  右向左旋转  //这也只是第一步
    AVLTreeNode SingleRotataRight(AVLTreeNode X)//X为10
    {
        AVLTreeNode W=X.getRight();
        X.setRight(W.getLeft());
        W.setLeft(X);

        X.setHeight(Math.max(Height(X.getRight()),Height(X.getLeft()))+1);
        W.setHeight(Math.max(Height(W.getRight()),X.getHeight())+1);

        return W;
    }

3.在节点的左孩子的右子树插入元素：
其解决策略是：以下一个节点为目标节点向左旋转，然后整体向右旋转

 //左右插入  先将下一个节点整体向左旋转，然后向右旋转
    AVLTreeNode DoubleRotatewithLeft(AVLTreeNode Z)
    {
        Z.setLeft(SingleRotataRight(Z.getLeft()));
        return SingleRotataLeft(Z);
    }

例如：
4.在节点的右孩子的左子树插入元素：
同理：
其解决策略是：以下一个节点为目标节点向右旋转，然后整体向左旋转

//右左插入  先将下一个节点整体向右旋转，然后向左旋转
    AVLTreeNode DoubleRotatewithRight(AVLTreeNode Z)
    {
        Z.setRight(SingleRotataLeft(Z.getRight()));
        return SingleRotataRight(Z);
    }

三.java实现：

1.节点定义：

class AVLTreeNode{
    private int data;
    private int height;
    private AVLTreeNode left;
    private AVLTreeNode right;
    public int getData()
    { return data; }
    public void setData(int data)
    { this.data=data;}
    public int getHeight()
    { return height; }
    public void setHeight(int height)
    { this.height=height; }
    public AVLTreeNode getLeft()
    { return left; }
    public void setLeft(AVLTreeNode left)
    { this.left=left; }
    public AVLTreeNode getRight()
    { return right; }
    public void setRight(AVLTreeNode right)
    { this.right=right; }
}

二.操作方法定义：

class CaoZuo3{
    int Height(AVLTreeNode root)
    {
        if(root==null)
            return -1;
        else
            return root.getHeight();
    }

    // 1.左左插入  左向右旋转
    AVLTreeNode SingleRotataLeft(AVLTreeNode X)
    {
        AVLTreeNode W=X.getLeft();
        X.setLeft(W.getRight());
        W.setRight(X);

        X.setHeight(Math.max(Height(X.getLeft()),Height(X.getRight()))+1);
        W.setHeight(Math.max(Height(W.getLeft()),X.getHeight())+1);

        return W;
    }

    //2. 右右插入  右向左旋转
    AVLTreeNode SingleRotataRight(AVLTreeNode X)
    {
        AVLTreeNode W=X.getRight();
        X.setRight(W.getLeft());
        W.setLeft(X);

        X.setHeight(Math.max(Height(X.getRight()),Height(X.getLeft()))+1);
        W.setHeight(Math.max(Height(W.getRight()),X.getHeight())+1);

        return W;
    }

    //左右插入  先将下一个节点整体向左旋转，然后向右旋转
    AVLTreeNode DoubleRotatewithLeft(AVLTreeNode Z)
    {
        Z.setLeft(SingleRotataRight(Z.getLeft()));
        return SingleRotataLeft(Z);
    }

    //右左插入  先将下一个节点整体向右旋转，然后向左旋转
    AVLTreeNode DoubleRotatewithRight(AVLTreeNode Z)
    {
        Z.setRight(SingleRotataLeft(Z.getRight()));
        return SingleRotataRight(Z);
    }


    //插入操作
    AVLTreeNode Insert(AVLTreeNode root,AVLTreeNode parent,int data)
    {
        if(root==null)
        {
            root=new AVLTreeNode();
            root.setData(data);
            root.setHeight(0);
            root.setLeft(null);
            root.setRight(null);
        }
        else if(data<root.getData())
        {
            root.setLeft(Insert(root.getLeft(),root,data));
            if(Height(root.getLeft())-Height(root.getRight())==2)
            {
                if(data<root.getLeft().getData())
                    root=SingleRotataLeft(root);
                else
                    root=DoubleRotatewithLeft(root);
            }
        }
        else if(data>root.getData())
        {
            root.setRight(Insert(root.getRight(),root,data));
            if(Height(root.getRight())-Height(root.getLeft())==2)
            {
                if(data<root.getRight().getData())
                    root=SingleRotataRight(root);
                else
                    root = DoubleRotatewithRight(root);
            }
        }
        root.setHeight(Math.max(Height(root.getLeft()),Height(root.getRight()))+1);
        return root;
    }

    //遍历操作：
    void Check3(AVLTreeNode first)//中序遍历
    {
        if(first!=null)
        {
            Check3(first.getLeft());
            System.out.print(first.getData());
            Check3((first.getRight()));
        }
    }
}

测试代码：

public class AVLTree {
    public static void main(String[] args) {
        AVLTreeNode one=new AVLTreeNode();
        one.setData(6);
        CaoZuo3 text=new CaoZuo3();
        text.Insert(one,null,5);
        text.Insert(one,null,9);
        text.Insert(one,null,7);
        text.Insert(one,null,8);
        text.Insert(one,null,3);
        text.Check3(one);
    }
}

结果：