平衡二叉搜索树 (BBST)

二叉搜索树(BST)的缺陷？

二叉搜索树，在某种情况下会导致极度的不平衡，导致时间复杂度剧增。

如图，如果按照 7 4 9 2 5 8 11 的顺序添加节点

image-20200511145438192

如果按照从小到大的顺序添加节点

image-20200511145514949

二叉树退化成链表

如何改进BST？

有没有办法防止二叉搜索树退化成链表？

让添加，删除，搜索的复杂度维持在 O(log N)

平衡

平衡：当节点数量固定时，左右子树的高度越来越接近，这棵二叉树就越平衡(高度越低).

理想平衡

最理想的平衡，就是像完全二叉树，满二叉树那样，高度是最小的。

改进

  • 首先，节点的添加，删除顺序是无法限制的，可以认为是随机的
  • 所以改进的方案是，在节点添加，删除操作之后，想办法让二叉搜索树恢复平衡(减小树的高度)

image-20200511150225219

  • 如果接着继续调整节点的位置，完全可以达到理想平衡，但是付出的代价可能会比较大
    • 比如调整的次数会比较多，反而增加了时间复杂度
  • 总结来说，比较合理的改进方案是：用尽量少的调整次数达到适度的平衡即可。
  • 一棵达到适度平衡的二叉搜索树，可以称之为平衡二叉搜索树。

平衡二叉搜索树 (Balanced Binary Search Tree)

  • 英文简称为: BBST
  • 经典常见的平衡二叉搜索树
    • AVL树 (Windows NT内核广泛应用)
    • 红黑树
      • C++ STL (map , set)
      • Java中的TreeMap, TreeSet, HashMap, HashSet
      • Linux的进程调度
      • Ngix 的 timer 管理
  • 一般也称它们为： 自平衡的二叉搜索树(Self-balancing Binary Search Tree)

练习题

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3 /
9 20 /
15 7 返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1

/
2 2 /
3 3 /
4 4 返回 false 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/balanced-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：
思路一：

平衡二叉树的概念是，每个节点左右子树的高度相差的绝对值 <= 1 。 故思路很简单，我们遍历二叉树每个节点，并计算其左右子树高度差绝对值，所有都 <=1, 则平衡，其中有绝对值 > 1的，则不平衡。

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// 计算node节点高度
    // 递归
    public int height(TreeNode node){
        if (node == null) return 0;

        return Math.max(height(node.left),height(node.right)) + 1;
    }

    // 计算节点高度
    // 迭代
    public int height1(TreeNode node){
        if (node == null) return 0;

        int height = 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size > 0){
                TreeNode n = queue.remove();
                if (n.left != null) queue.add(n.left);
                if (n.right != null) queue.add(n.right);

                size --;
            }
            height ++;
        }

        return height;
    }

    public boolean isBalanced(TreeNode node) {
        if (node == null) return true;

        return (Math.abs(height(node.left) - height(node.right)) <= 1) && isBalanced(node.left) && isBalanced(node.right);
    }

计算节点高度有两种方法

  • 递归， 节点的高度等于其左右子树的高度中的最大值 + 1

  • 迭代， 利用层序遍历，遍历完一层，height++。 直至遍历完所有节点

上述方法是自顶向下的递归，越深处的子节点，需要经过更多次数的计算，包含大量重复的计算。 下边方法中，我们用自下而上的递归，减少重复计算。

可以递归计算当前节点子节点的高度，然后根据子节点的高度判断当前节点是否平衡。

思路二：

从底至顶

思路是对二叉树前序遍历，从底至顶返回子树的最大高度，若判断某子树不是平衡二叉树则 “剪枝”，直接向上返回。

算法流程：

1

recur(root):

  • 递归返回值

    • 当节点 root 左右子树的高度差 < 2，则返回以节点root为根节点的子树的最大高度，即节点root的左右子树中最大高度 + 1
    • 当节点root 左右子树高度差 >= 2, 则代表root不平衡，直接返回 -1.

  • 递归终止条件

    • 叶子节点时，返回高度0
    • 当左(右)子树高度left == -1时，则代表此子树的 左(右)子树 不是平衡树, 因此直接返回 -1.
    1

    isBalance(root):
    • 返回值：若recur(root) != -1， 则代表是平衡二叉树。

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public List<Integer> dfs(TreeNode root){
        if (root == null) return null;

        List<Integer> list = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null){
            while (root != null){
                stack.push(root);
                
                root = root.left;
            }
            
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        
        return list;
    }

    public TreeNode convertBiNode(TreeNode root) {
        if (root == null) return null;

        List<Integer> list = dfs(root);
        
        TreeNode head = new TreeNode(-1);
        TreeNode node = head;
        for (int i = 0; i < list.size(); i++) {
            node.right = new TreeNode(list.get(i));
            node = node.right;
        }
        
        return head.right;
    }