平衡二叉树详解(定义特征及旋转示例)

平衡二叉树定义

平衡二叉树，英文名Balanced Binary Tree，是一种自平衡的树，也叫AVL树。

 

平衡二叉树特征

平衡二叉树具有以下性质：

• 平衡二叉树规定了左结点小于根节点，右结点大于根节点；
• 并且还规定了左子树和右子树的高度差不得超过1，这样保证了它不会成为线性的链表；

如下图所示：

 

平衡二叉树失衡

在二叉查找树中存在退化成单链表的极端情况，例如序列，构建二叉查找树如图所示：

此时构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)，在此二叉搜索树中查找元素 6 需要查找 6 次，严重影响了查询效率。

怎样才能提升查询效率呢？

我们发现：二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。

那如何去恢复平衡，使得二叉搜索树依然成立为一棵平衡树？

主要的解决办法：就是通过左旋和右旋来解决，防止特殊情况出现上面的线性结构。

1.左旋的情况

为了调整高度差，则通过左旋便可修复，如下图所示：

还是动态演示下，这样更容易理解左旋。

2.右旋的情况

为了调整高度差，则通过左旋便可修复，如下图所示：

还是动态演示下，这样更容易理解左旋。

备注：这样的方式也有对应的缺点，由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。

 

平衡二叉树实现

代码示例如下：

class BalancedBinaryTree {
 
    private Node root;
 
    public Node getRoot() {
        return root;
    }
 
    //添加结点
    public void add(Node node) {
        //root为空则让root指向node
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
    }
 
    //中序遍历
    public void infixOrder() {
        if (this.root == null) {
            System.out.println("二叉排序树为空，无法遍历！");
        } else {
            this.root.infixOrder();
        }
    }
}
 
class Node {
    int value;
    Node left;
    Node right;
 
    public Node(int value) {
        this.value = value;
    }
 
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
 
    //左旋转
    public void leftRotate() {
        //创建一个新结点 将当前结点的值赋值给它
        Node newNode = new Node(this.value);
        //将新结点的左子树设置成当前结点的左子树
        newNode.left = this.left;
        //将新结点的右子树设置为当前结点的右子结点的左子树
        newNode.right = this.right.left;
        //把当前结点的值换成右子结点的值
        this.value = this.right.value;
        //把当前结点的右子树设置成当前结点的右子结点的右子树
        this.right = this.right.right;
        //把当前结点的左子结点设置成新结点
        this.left = newNode;
    }
 
    //右旋转
    public void rightRotate() {
        //创建一个新结点，把当前结点的值赋值给新结点
        Node newNode = new Node(this.value);
        //将新结点的右子树设置成当前结点的右子树
        newNode.right = this.right;
        //将新结点的左子树设置成当前结点的左子结点的右子树
        newNode.left = this.left.right;
        //将当前结点的值设置成当前结点左子结点的值
        this.value = this.left.value;
        //将当前结点的右子结点设置成新结点
        this.right = newNode;
        //将当前结点的左子结点设置成左子结点的左子树
        this.left = this.left.left;
    }
 
    //返回以当前结点为根结点的树的高度
    public int height() {
        //返回左子树和右子树中较大的高度再加上当前结点的高度
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }
 
    //返回左子树的高度
    public int leftHeight() {
        if (this.left == null) {
            return 0;
        }
        return this.left.height();
    }
 
    //返回右子树的高度
    public int rightHeight() {
        if (this.right == null) {
            return 0;
        }
        return this.right.height();
    }
 
    //添加结点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //判断传入的结点的值与当前子树的根结点的关系
        //要添加的结点的值小于当前结点的值
        if (node.value < this.value) {
            //当前结点的左子结点为空
            if (this.left == null) {
                this.left = node;
            } else {
                //递归向左子树添加
                this.left.add(node);
            }
        } else if (node.value > this.value) {//要添加的结点的值大于当前结点的值
            //当前结点的右子结点为空
            if (this.right == null) {
                this.right = node;
            } else {
                //递归向右子树添加
                this.right.add(node);
            }
        }
 
        //当添加完一个结点后，如果右子树的高度-左子树的高度 > 1 则左旋转
        if (rightHeight() - leftHeight() > 1) {
            //如果当前结点的右子树的左子树的高度大于当前结点的右子树的右子树的高度
            //则需要先对当前结点的右子树进行右旋转
            //因为rightHeight() - leftHeight() > 1 所以this.right肯定不为null
            if (this.right.leftHeight() > this.right.rightHeight()) {
                this.right.rightRotate();
            }
            //左旋转
            leftRotate();
            //一定要return！因为旋转完后已经平衡，
            //如果还让下面的进行判断，很有可能出问题
            return;
        }
        //左子树的高度-右子树的高度 > 1 则右旋转
        if (leftHeight() - rightHeight() > 1) {
            //如果当前结点的左子树的右子树的高度大于当前结点的左子树的左子树的高度
            //则需要先对当前结点的左子树进行左旋转
            //因为leftHeight() - rightHeight() > 1 所以this.left肯定不为null
            if (this.left.rightHeight() > this.left.leftHeight()) {
                this.left.leftRotate();
            }
            //右旋转
            rightRotate();
            return;
        }
    }
 
    //中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}

 

关注「mikechen」，十余年BAT架构经验倾囊相授！