投稿
  1. 极客之音首页
  2. 数据结构

【算法题解】65. 通过旋转构建二叉平衡树

小半 • • 数据结构 • 阅读 222

题目还是 【算法题解】64. 将二叉搜索树变平衡 这道题。

上一题中我们使用了 「中序序列构建二叉平衡搜索树」 的解法，也是最简单的解法。

这一次我们直接使用原始树来构造一棵二叉平衡搜索树，不管原始树是否是二叉搜索树，通用性更强，当然难度也更高。

解题思路

以任意方式遍历原始二叉树，每遍历到一个节点，就将其插入到二叉平衡搜索树 AVL 当中。

开始时 AVL 为空，直接将插入的节点当作根节点即可。

后续插入过程中，如果插入值大于根节点，就插入右子树。如果插入值小于根节点，就插入左子树，保证插入结果为二叉搜索树。参考题解【算法题解】60. 二叉搜索树中的插入操作 。

在保证插入结果是二叉搜索树的同时，还需要保证这棵树是平衡的，即任意节点的左右子树高度差不能大于 1 。这就要求我们在构建平衡树的同时维护每个节点的高度，并在插入新节点后判断其是否破坏了平衡性，如果破坏了就通过 「旋转」 的方式将其变平衡。

如何维护每个节点的高度？

插入一个新的节点时默认其高度是 1，然后再通过递归，逐层修改其父节点的高度。

Java伪代码实现：

// 存储每个节点的高度
private Map<TreeNode, Integer> heightMap = new HashMap<>();

// 向 AVL 树中插入一个值，返回 AVL 树的根节点
public TreeNode insert(TreeNode root, int val){
    if(root == null){
        root = new TreeNode(val);
        heightMap.put(root, 1);
        return root;
    }

    
    if(val < root.val){
        // 插入左子树
        root.left = insert(root.left, val);
    }else{
        // 插入右子树
        root.right = insert(root.right, val);
    }

    // 更新 root 的高度
    heightMap.put(root, Math.max(heightMap.getOrDefault(root.left, 0), heightMap.getOrDefault(root.right, 0)) + 1);
    
}

插入时怎么旋转？

每当插入一个新节点，并维护好节点高度的同时。如果发现插入的节点导致树不再平衡，那么就需要通过旋转的方式来将树重新变平衡。

插入时遇到的不平衡现象有以下4种：

  1. LL：新插入的节点在当前根节点的左节点的左边，右旋。【算法题解】65. 通过旋转构建二叉平衡树

  2. RR: 新插入的节点在当前根节点的右节点的右边，左旋。【算法题解】65. 通过旋转构建二叉平衡树

  3. LR: 新插入的节点在当前根节点的左节点的右边，先左节点左旋变换为 LL 。【算法题解】65. 通过旋转构建二叉平衡树然后再根节点右旋。【算法题解】65. 通过旋转构建二叉平衡树

  4. RL：新插入的节点在当前根节点的右节点的左边，先右节点右旋变换为 RR 。【算法题解】65. 通过旋转构建二叉平衡树然后再根节点左旋。【算法题解】65. 通过旋转构建二叉平衡树

Java伪代码实现变更为：

// 存储每个节点的高度
private Map<TreeNode, Integer> heightMap = new HashMap<>();

// 向 AVL 树中插入一个值，返回 AVL 树的根节点
public TreeNode insert(TreeNode root, int val){
 if(root == null){
        root = new TreeNode(val);
        heightMap.put(root, 1);
        return root;
    }

    
    if(val < root.val){
        // 插入左子树
        root.left = insert(root.left, val);
        // 当左子树的高度 - 右子树的高度 > 1, 可能是 LL 或者 LR
        if(heightMap.getOrDefault(root.left, 0) - heightMap.getOrDefault(root.right, 0) > 1){
            // 判断是否是 LR
            if(val > root.left.val){
                // LR
                // root.left 左旋转换为LL
            }

            //LL
            // root 右旋
        }

        
 }else{
        // 插入右子树
        root.right = insert(root.right, val);

        // 当右子树的高度 - 左子树的高度 > 1, 可能是 RR 或者 RL
        if(heightMap.getOrDefault(root.right, 0) - heightMap.getOrDefault(root.left, 0) > 1){
            // 判断是否是 RL
            if(val < root.right.val){
                // RL
                // root.right 右旋转换为RR
            }

            //RR
            // root 左旋
        }
    }


    // 更新 root 的高度
    heightMap.put(root, Math.max(heightMap.getOrDefault(root.left, 0), heightMap.getOrDefault(root.right, 0)) + 1);

    return root;
}

那么接下来的重点就是如何实现左旋和右旋。

左旋

// 1. node 的右节点变成新的根结点。 
// 2. node 变为其右节点（新的根结点）的做节点。
// 3. node 右节点的左节点变为 node 的新的右节点。
private TreeNode rotateLeft(TreeNode node){
 TreeNode right = node.right;
 if(right == null){
        return node;
    }
        
    node.right = right.left;
    right.left = node;
    // 高度更新， 因为只有 node 和 其右节点改变了子树，所以只需要重新计算他两的高度
    // 更新node节点高度
    heightMap.put(node, Math.max(heightMap.getOrDefault(node.left, 0), heightMap.getOrDefault(node.right, 0)) + 1);
    
 // 跟新右节点，也就是新的根结点的高度
    heightMap.put(right, Math.max(heightMap.getOrDefault(right.left, 0),, heightMap.getOrDefault(right.right,0)) + 1);
    return right;
}

右旋

// 1. node  的左节点变为新的根结点。
// 2. node 变为其左节点（新的根结点）的右节点。
// 3. node 的左节点原来的右节点变为 node 的 左节点。
private TreeNode rotateRight(TreeNode node){
 TreeNode left = node.left;
 if(left == null){
        return node;
    }
        
    node.left = left.right;
    left.right = node;
    // 高度更新， 因为只有 node 和 其左节点改变了子树，所以只需要重新计算他两的高度
    // 更新node节点高度
    heightMap.put(node, Math.max(heightMap.getOrDefault(node.left, 0), heightMap.getOrDefault(node.right, 0)) + 1);
    
 // 跟新右节点，也就是新的根结点的高度
    heightMap.put(left, Math.max(heightMap.getOrDefault(left.left, 0),, heightMap.getOrDefault(left.right,0)) + 1);
    
 return left;
}

完整代码见代码实现。

代码实现

代码实现中，二叉树的遍历采用的是广度优先搜索，更简单直观一些。当然其他遍历方式也是可以的。

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 存储每个节点的高度
    private Map<TreeNode, Integer> heightMap = new HashMap<>();
    public TreeNode balanceBST(TreeNode root) {
        TreeNode avlRoot = null;
        // 广度优先
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            avlRoot = insert(avlRoot, node.val);
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        return avlRoot;
    }



    // 向 AVL 树中插入一个值，返回 AVL 树的根节点
    public TreeNode insert(TreeNode root, int val){
        if(root == null){
            root = new TreeNode(val);
            heightMap.put(root, 1);
            return root;
        }

        
        if(val < root.val){
            // 插入左子树
            root.left = insert(root.left, val);
            // 当左子树的高度 - 右子树的高度 > 1, 可能是 LL 或者 LR
            if(heightMap.getOrDefault(root.left, 0) - heightMap.getOrDefault(root.right, 0) > 1){
                // 判断是否是 LR
                if(val > root.left.val){
                    // LR
                    // root.left 左旋转换为LL
                    root.left = rotateLeft(root.left);
                }

                //LL
                // root 右旋
                root = rotateRight(root);
            }

            
        }else{
            // 插入右子树
            root.right = insert(root.right, val);

            // 当右子树的高度 - 左子树的高度 > 1, 可能是 RR 或者 RL
            if(heightMap.getOrDefault(root.right, 0) - heightMap.getOrDefault(root.left, 0) > 1){
                // 判断是否是 RL
                if(val < root.right.val){
                    // RL
                    // root.right 右旋转换为RR
                    root.right = rotateRight(root.right);
                }

                //RR
                // root 左旋
                root = rotateLeft(root);
            }
        }

        
        // 更新 root 的高度
        heightMap.put(root, Math.max(heightMap.getOrDefault(root.left, 0), heightMap.getOrDefault(root.right, 0)) + 1);

        return root;
    }

 
    // 左旋
    private TreeNode rotateLeft(TreeNode node){
        TreeNode right = node.right;
        if(right == null){
            return node;
        }
            
        node.right = right.left;
        right.left = node;
        // 高度更新， 因为只有 node 和 其右节点改变了子树，所以只需要重新计算他两的高度
        // 更新node节点高度
        heightMap.put(node, Math.max(heightMap.getOrDefault(node.left, 0), heightMap.getOrDefault(node.right, 0)) + 1);
        
        // 跟新右节点，也就是新的根结点的高度
        heightMap.put(right, Math.max(heightMap.getOrDefault(right.left, 0), heightMap.getOrDefault(right.right,0)) + 1);
        return right;
    }

    // 右旋
    private TreeNode rotateRight(TreeNode node){
        TreeNode left = node.left;
        if(left == null){
            return node;
        }
            
        node.left = left.right;
        left.right = node;
        // 高度更新， 因为只有 node 和 其左节点改变了子树，所以只需要重新计算他两的高度
        // 更新node节点高度
        heightMap.put(node, Math.max(heightMap.getOrDefault(node.left, 0), heightMap.getOrDefault(node.right, 0)) + 1);
        
        // 跟新右节点，也就是新的根结点的高度
        heightMap.put(left, Math.max(heightMap.getOrDefault(left.left, 0), heightMap.getOrDefault(left.right,0)) + 1);
        
        return left;
    }
}

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func balanceBST(root *TreeNode) *TreeNode {
    heightMap := map[*TreeNode]int{}

    // 广度优先遍历
    queue := []*TreeNode{root}

    var avlRoot *TreeNode

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Left != nil {
             queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
        avlRoot = insert(avlRoot, node.Val, heightMap)
    }
    return avlRoot
}

func insert(root *TreeNode, val int, heightMap map[*TreeNode]int) *TreeNode {
    if root == nil {
        root = &TreeNode{Val: val}
        heightMap[root] = 1
        return root
    }
    if val < root.Val {
        // 插入左子树
        root.Left = insert(root.Left, val, heightMap)
        if heightMap[root.Left] - heightMap[root.Right] > 1 {
            if val > root.Left.Val {
                root.Left = rotateLeft(root.Left, heightMap)
            }
            root = rotateRight(root, heightMap)
        }
    }else {
        // 插入右子树
        root.Right = insert(root.Right, val, heightMap)
        if heightMap[root.Right] - heightMap[root.Left] > 1 {
            if val < root.Right.Val {
                root.Right = rotateRight(root.Right, heightMap)
            }
            root = rotateLeft(root, heightMap)
        }
    }

    // 更新root高度
    heightMap[root] = max(heightMap[root.Left], heightMap[root.Right]) + 1

    return root

}

func rotateLeft(node *TreeNode, heightMap map[*TreeNode]int) *TreeNode {
    right := node.Right
    if right == nil {
        return node
    }
            
    node.Right = right.Left
    right.Left = node
    // 高度更新， 因为只有 node 和 其右节点改变了子树，所以只需要重新计算他两的高度
    // 更新node节点高度
    heightMap[node] = max(heightMap[node.Left], heightMap[node.Right]) + 1

    // 跟新右节点，也就是新的根结点的高度
    heightMap[right] = max(heightMap[right.Left], heightMap[right.Right] + 1);
    return right
}

func rotateRight(node *TreeNode, heightMap map[*TreeNode]int) *TreeNode {
    left := node.Left
    if left == nil {
        return node
    }
            
    node.Left = left.Right
    left.Right = node
    // 高度更新， 因为只有 node 和 其左节点改变了子树，所以只需要重新计算他两的高度
    // 更新node节点高度
    heightMap[node] = max(heightMap[node.Left], heightMap[node.Right]) + 1

    // 跟新左节点，也就是新的根结点的高度
    heightMap[left] = max(heightMap[left.Left], heightMap[left.Right] + 1);
    return left
}


func max(a int, b int) int {
    if a > b {
        return a
    }else {
        return b
    }
    
}

总结

重点在于如何判断是 LL, LR, RR, RL 中的哪一种，以及怎么实现「左旋」和「右旋」。

– End –

【算法题解】65. 通过旋转构建二叉平衡树

原文始发于微信公众号（i余数）：【算法题解】65. 通过旋转构建二叉平衡树

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/193542.html

赞 (0)
小半的头像小半
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！