平衡二叉树

作者: 贪挽懒月 | 来源:发表于2020-12-14 09:38 被阅读0次

1. 为什么会出现平衡二叉树这种数据结构？

之前学习了二叉排序树，假如现有数列：1,2,3,4,5，要用这个数列创建一棵二叉排序树，结果是这样的：

二叉排序树

看起来就怪怪的，其实就是斜着放的单链表。这棵树存在以下问题：

左子树全部为空，其实就是一个单链表；
其实查询比单链表更慢，因为在检索的时候要判断左子树是否为空，因为不能发挥二叉排序树的优势。

为了解决上面的问题，平衡二叉树(AVL树)就应运而生了。

2. 什么是平衡二叉树？

平衡二叉树又叫AVL树，也叫平衡二叉搜索树，可以保证较高的查询效率；
它是一棵空树，或者是左右子树的高度差的绝对值不会超过1，并且左右两棵子树都是一棵平衡二叉树；
平衡二叉树常用的实现算法有红黑树，AVL，替罪羊树，Treap，伸展树等；

3. 如何创建平衡二叉树？

(1). 左旋转思路：

假如现有数列：4,3,6,5,7,8，创建出来的二叉树排序数如下图：

二叉排序树

节点4的左子树高度为1，右子树高度为3，高度差是2，所以不是平衡二叉树。如果要将其变成平衡二叉树该怎么做呢？因为其右子树的高度更高，要分点儿给左子树，所以方法叫做左旋转。具体步骤如下：

创建一个新节点newNode，值为根节点的值，即：Node newNode = new Node(4)；
当前节点currentNode(节点4)的左子树(节点3)作为新节点的左子树，即：newNode.left = currentNode.left；
当前节点(节点4)的右子树(节点6)的左子树(节点5)作为新节点的右子树，即：newNode.right = currentNode.right.left；
把当前节点(节点4)的值换成右子节点(节点6)的值，即现在二叉树的效果如下：

二叉树

当前节点的右子树(节点6)的右子树(节点7)作为当前节点的右子树，即：currentNode.right = currentNode.right.right，设置完后效果如下：

二叉树

最后一步，新节点作为当前节点的左子树，即：currentNode.left = newNode，最后效果如下：

平衡二叉树

(2). 右旋转：

过程和左旋转类似，只不过是将左旋转步骤中的左右颠倒一下。

创建新节点，值为当前根节点的值；
当前节点的右子树作为新节点的右子树；
当前节点左子树的右子树作为新节点的左子树；
把当前节点的值换成左子节点的值；
当前节点的左子树的左子树作为当前节点的左子树；
新节点作为当前节点的右子树。

(3). 代码实现左/右旋转：

首先创建如下的AVL树类：

public class AvlTree {

    // 根节点
    private Node root;

    /**
     * 给外部调用的添加节点的方法
     * 
     * @param value
     */
    public void add(int value) {
        add(new Node(value));
    }

    /**
     * 添加节点
     * 
     * @param node
     */
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            throw new IllegalArgumentException("二叉排序树为空");
        }
    }
    

    /**
     * 节点类
     * 
     * @author zhu
     *
     */
    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) {
                return;
            }
            // 如果传入的节点值比当前节点值小
            if (node.value < this.value) {
                // 如果当前节点左边没有节点
                if (this.left == null) {
                    // 就把node挂在当前节点左边
                    this.left = node;
                } else {
                    // 当前节点左边有节点，那就递归
                    this.left.add(node);
                }
            } else { // 往右边添加
                if (this.right == null) {
                    // 就把node挂在当前节点右边
                    this.right = node;
                } else {
                    // 当前节点右边有节点，那就递归
                    this.right.add(node);
                }
            }
        }

        /**
         * 中序遍历
         */
        public void infixOrder() {
            // 往左递归
            if (this.left != null) {
                this.left.infixOrder();
            }
            // 输出当前节点
            System.out.println(this.value);
            // 向右递归
            if (this.right != null) {
                this.right.infixOrder();
            }
        }
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }
}

目前这棵树只有最基本的添加节点和中序遍历的方法。因为是否要进行旋转，需要根据树的高度来进行判断，所以在Node内部类中新增如下方法，用来获取树的高度：

/**
* 返回以当前节点为根节点的树的高度
* 
* @return
*/
public int height() {
    // 左右子树不为空的时候就递归，直到它为空为止，然后取左右子树中高度较大的值作为树的高度，最后加1是自身也算一个高度
    return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}

/**
* 返回当前节点左子树的高度
* 
* @return
*/
public int leftHeight() {
    return left == null ? 0 : left.height();
}

/**
* 返回当前节点右子树的高度
* 
* @return
*/
public int rightHeight() {
    return right == null ? 0 : right.height();
}

接下来测试一下获取树的高度的代码是否正确：

public static void main(String[] args) {
    int[] arr = {4,3,6,5,7,8};
//      int[] arr = {10,12,8,9,7,6}; // 需要右旋转的树
    AvlTree avlTree = new AvlTree();
    for (int i=0; i<arr.length; i++) {
        avlTree.add(arr[i]);
    }
    System.out.printf("树的高度：%s\r\n" ,avlTree.getRoot().height());
    System.out.printf("根节点左子树的高度：%s\r\n", avlTree.getRoot().leftHeight());
    System.out.printf("根节点右子树的高度：%s\r\n", avlTree.getRoot().rightHeight());
}

如果正常的话，会打印出：

树的高度：4
根节点左子树的高度：1
根节点右子树的高度：3

接下来，就按照上面左/右旋转的步骤，在Node内部类中写两个方法就好了，如下：

/**
* 左旋转
*/
public void leftRotate() {
    // 1. 创建新节点，值为当前节点的值
    Node newNode = new Node(value);
    // 2. 当前节点左子树作为新节点的左子树
    newNode.left = left;
    // 3. 当前节点的右子树的左子树作为新节点的右子树
    newNode.right = right.left;
    // 4. 把当前节点的值换成右子节点的值
    value = right.value;
    // 5. 当前节点的右子树的右子树作为当前节点的右子树
    right = right.right;
    // 6. 新节点作为当前节点的左子树
    left = newNode;
}
        
/**
* 右旋转，和左旋转对称
*/
public void rightRotate() {
    Node newNode = new Node(value);
    newNode.right = right;
    newNode.left = left.right;
    value = left.value;
    left = left.left;
    right = newNode;
}

写好之后怎么用呢？在Node内部类中的add方法中，每添加完一个节点，就判断一下是否需要进行左右旋转，如果需要，就调用左右旋转的方法，如下：

public void add(Node node) {
    if (node == null) {
        return;
    }
    // 如果传入的节点值比当前节点值小
    if (node.value < this.value) {
        // 如果当前节点左边没有节点
        if (this.left == null) {
            // 就把node挂在当前节点左边
            this.left = node;
        } else {
            // 当前节点左边有节点，那就递归
            this.left.add(node);
        }
    } else { // 往右边添加
        if (this.right == null) {
            // 就把node挂在当前节点右边
            this.right = node;
        } else {
            // 当前节点右边有节点，那就递归
            this.right.add(node);
        }
    }
    // 添加完一个节点后，如果(右子树高度 - 左子树高度) > 1，左旋转
    if (rightHeight() - leftHeight() > 1) {
        leftRotate();
    }
    // 添加完一个节点后，如果(左子树高度 - 右子树高度) > 1，右旋转
    if (leftHeight() - rightHeight() > 1) {
        rightRotate();
    }
}

这样每次添加一个节点后，都会判断是否需要旋转。同样是刚才测试的代码，再次运行，就会发现树的高度、左右子树的高度都发生变化了。

(4). 双旋转：

假如现有数列：10,11,7,6,8,9，用上面的测试代码跑一下，发现结果如下：

树的高度：4
根节点左子树的高度：1
根节点右子树的高度：3

没错，即使进行了左右旋转，它仍然不是平衡二叉树。这种情况，需要进行双旋转。怎么进行双旋转呢？

就是当进行右旋转的时候，进行如下操作：

如果它的左子树的右子树高度大于它的左子树的左子树的高度，就先对它的左节点进行左旋转；

当进行左旋转的时候，进行如下操作：

如果它的右子树的左子树高度大于它的右子树的右子树的高度，就先对它的右节点进行右旋转；

代码就是在刚才add方法中加的两个if中再加一层判断，如下：

// 添加完一个节点后，如果(右子树高度 - 左子树高度) > 1，左旋转
if (rightHeight() - leftHeight() > 1) {
    if (right != null && right.leftHeight() > right.rightHeight()) {
        right.rightRotate();
    }
    leftRotate();
    return;
}
// 添加完一个节点后，如果(左子树高度 - 右子树高度) > 1，右旋转
if (leftHeight() - rightHeight() > 1) {
    if (left != null && left.rightHeight() > left.leftHeight()) {
        left.leftRotate();
    }
    rightRotate();
}

加上这段逻辑，数列10,11,7,6,8,9形成的二叉树也是平衡的了。

平衡二叉树

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读