平衡二叉搜索树详细介绍

妖狐艹你老母 2023-09-26 21:07 12阅读 0赞

# 1. 介绍 #

*  `平衡二叉树`也称为`高度平衡树`。
 *  当`左子树和右子树的高度之差不大于m时`，它被定义为二叉树，其中`m通常等于1`。
 *  `树的高度`是`树之间最长路径上的边数根节点和叶节点`。

## 1)平衡二叉搜索树 ##

![在这里插入图片描述][a093b7032c9e45c08f265843541a64e9.png]

*  上面的树是二叉搜索树。
 *  二叉搜索树是一棵树，其中`左侧的每个节点的值都低于其父节点`，`右侧的节点的值均高于其父节点`。
 *  在上面的树中，`n1是根节点`，`n4、n6、n7是叶节点`。
 *  `n7 节点`是`距离根节点最远的节点`。
 *  `n4`和`n6` 包含`2 条边`，`根节点`和 `n7`节点之间存在 `3 条边`。
 *  由于`n7距离根节点最远`；因此，上述`树的高度为 3`。
 *  现在我们来看看上面的树是否平衡。
 *  `左子树`包含节点`n2、n4、n5 和 n7`，而`右子树`包含节点`n3 和 n6`。
 *  `左子树`有`两个叶节点`，即 `n4` 和`n7`。
 *  节点`n2`和`n4`之间`只有一条边`，节点`n7`和`n2`之间只有`两条边`；因此，节点 `n7`离根节点最远。
 *  `左子树`的`高度为2`。
 *  `右子树`只包含一个叶子节点，即`n6`，并且只有一条边；因此，`右子树的高度为1`。
 *  `左子树和右子树的高度之差为1`。由于我们得到的值为`1`，所以我们可以说上面的树是一棵`高度平衡的树`。
 *  应该为每个节点（如 n2、n3、n4、n5、n6 和 n7）执行计算高度差的过程。当我们处理每个节点时，就会发现`k的值不大于1`，所以可以说上面的树是`一棵平衡二叉树`。

## 2)不平衡二叉搜索树 ##

![在这里插入图片描述][3c40e08548844b368541a0260e4c1d33.png]

*  在上面的树中，`n6、n4、n3`是`叶子节点`，其中`n6`是`离根节点最远的节点`。
 *  `根节点`和`叶节点`之间存在`三条边`；因此，上述`树的高度为3`。
 *  当我们以`n1为根节点`时，则左子树包含节点`n2、n4、n5和n6`，而`子树包含节点n3`。
 *  在左子树中，`n2是根节点`，`n4和n6是叶节点`。
 *  在`n4`和`n6`个节点中，`n6`是`距其根节点最远的节点`，`n6有两条边`；因此，左子树的高度为 `2`。
 *  `右子树的左右两边都有孩子`；因此，`右子树的高度为0`。
 *  由于`左子树的高度为2`，`右子树的高度为0`，所以左子树和右子树的`高度之差为2`。
 *  `根据定义，差值左子树和右子树的高度之间不能大于1`。
 *  在这种情况下，`差异为2，大于1`；因此，上面的二叉树是`一个不平衡的二叉搜索树`。

## 3）为什么我们需要平衡二叉树？ ##

![在这里插入图片描述][06c415b0b07b4cad8b2718b0ee565c6f.png]

*  上面的树是`二叉搜索树`，因为所有`左子树节点都小于其父节点，而所有右子树节点都大于其父节点`。
 *  假设我们想要在上面的树中`找到值 79`。
 *  首先，我们将节点`n1的值`与79进行比较；因为79的值不等于35并且大于35所以我们移动到节点`n3`，即48。
 *  因为值79不等于48并且79大于48所以我们向右移动48的孩子。节点48的右孩子的值为`79`，等于要查找的值。
 *  `搜索一个元素 79 所需的跳数是 2`，`搜索任何元素所需的最大跳数是 2`。
 *  搜索一个元素的平均情况是 `O(logn)`。  
    ![在这里插入图片描述][c96a9f409ec94009a9e7c402b9282d76.png]
 *  上面的树也是`一棵二叉搜索树`，因为所有的`左子树节点都小于它的父节点`，而所有的`右子树节点都大于它的父节点`。假设我们要在上面的树中找到值 79。
 *  首先，我们将值 `79`与节点`n4`，即 13 进行比较。由于值 79 大于 13，因此我们移动到节点 13 的右子节点，即 `n2 (21)`。
 *  节点`n2`的值为`21`小于`79`，所以我们再次`向右移动节点21`。
 *  节点21的右孩子值为29。由于值79大于29所以我们`向右移动节点29的孩子`。
 *  节点29的右孩子的值为35，小于79，所以我们`移动到节点35的右孩子，即48`。
 *  值79大于48，所以我们`移动到右孩子节点48的值`。
 *  48的右子节点的值为79，等于要查找的值。在这种情况下，搜索一个元素所需的跳数是 5。
 *  在这种情况下，最坏的情况是 O(n)。
 *  如果节点数增加，树状图1中使用的公式比树状图2中使用的公式更有效。
 *  假设以上两棵树中可用的节点数都是 100,000。
 *  要在树形图中搜索任何元素，所用时间为 100,000µs，而在树形图中搜索元素所用时间为 log(100,000)，即 16.6µs。
 *  我们可以观察到上述两棵树之间的巨大时间差异。
 *  因此，我们得出结论，`平衡二叉树提供比线性树数据结构更快的搜索`。

## 4)如何判断一棵二叉树是否是高度平衡的？ ##

*  `高度平衡二叉树`是一种二叉树，其中`任意节点的左子树和右子树的高度相差`不超过`1`，并且`左右子树也都是高度平衡的`。
 *  例子：左边的树是一棵高度平衡的二叉树。而右边的树不是高度平衡的树。因为根的左子树的高度比右子树的高度高 2。  
    ![在这里插入图片描述][1c97c15d11714c74a3967c47d6e23901.png]

### (1)方法1： ###

*  使用`dfs遍历获取左右子树的高度`。
 *  如果高度差不大于 1 且左右子树平衡则返回 true，否则返回 false。

/* 判断二叉树是否为Java程序 身高平衡与否 */
     
    /* 二叉树节点有数据，指向左孩子的指针， 和一个指向右孩子的指针 */
    class Node {
        
        int data;
        Node left, right;
        Node(int d)
        {
        
            data = d;
            left = right = null;
        }
    }
     
    class BinaryTree {
        
        Node root;
     
        /* 如果以根为根的二叉树是，则返回真
         * 高度平衡 */
        boolean isBalanced(Node node)
        {
        
            int lh; /* 对于左子树的高度 */
     
            int rh; /* 对于右子树的高度 */
     
            /* 如果树为空则返回真 */
            if (node == null)
                return true;
     
            /* 获取左右子树的高度 */
            lh = height(node.left);
            rh = height(node.right);
     
            if (Math.abs(lh - rh) <= 1 && isBalanced(node.left)
                && isBalanced(node.right))
                return true;
     
            /* 如果我们到达这里，那么树不是高度平衡的
             */
            return false;
        }
     
        /* 测试 isBalanced() 函数的实用函数*/
        /*  函数计算树的“高度”。高度 是最长路径上的节点数 根节点向下到最远的叶节点.*/
        int height(Node node)
        {
        
            /* 基本情况树是空的*/
            if (node == null)
                return 0;
     
            /* 如果树不为空，则 height = 1 + max of 左高和右高 */
            return 1
                + Math.max(height(node.left),
                           height(node.right));
        }
     
        public static void main(String args[])
        {
        
            BinaryTree tree = new BinaryTree();
            tree.root = new Node(1);
            tree.root.left = new Node(2);
            tree.root.right = new Node(3);
            tree.root.left.left = new Node(4);
            tree.root.left.right = new Node(5);
            tree.root.left.left.left = new Node(8);
     
            if (tree.isBalanced(tree.root))
                System.out.println("Tree is balanced");
            else
                System.out.println("Tree is not balanced");
        }
    }

Tree is not balanced

*  时间复杂度：在完整二叉树的情况下为 O(n^2)。
 *  辅助空间：由于使用递归，调用堆栈的 O(n) 空间

### (2)方法2： ###

*  `高效实施：`以上实施可以通过以下方式进行优, 在`同一个递归中计算高度而不是单独调用 height() 函数`。
 *  对于每个节点进行两次递归调用——`一次用于左子树，另一次用于右子树`。
 *  根据递归调用返回的高度，`判断以当前节点为根的子树是否是高度平衡的`。
 *  如果它是平衡的，则返回该`子树的高度`。
 *  否则，`返回 -1 表示子树不是高度平衡的`。

class Node {
        
        int key;
        Node left;
        Node right;
        Node(int k)
        {
        
            key = k;
            left = right = null;
        }
    }
     
    class GFG {
        
        public static void main(String args[])
        {
        
            Node root = new Node(10);
            root.left = new Node(5);
            root.right = new Node(30);
            root.right.left = new Node(15);
            root.right.right = new Node(20);
     
            if (isBalanced(root) > 0)
                System.out.print("Balanced");
            else
                System.out.print("Not Balanced");
        }
     
        // 检查树是否高度平衡的函数
        public static int isBalanced(Node root)
        {
        
            if (root == null)
                return 0;
            int lh = isBalanced(root.left);
            if (lh == -1)
                return -1;
            int rh = isBalanced(root.right);
            if (rh == -1)
                return -1;
     
            if (Math.abs(lh - rh) > 1)
                return -1;
            else
                return Math.max(lh, rh) + 1;
        }
    }

Balanced

*  `时间复杂度`：O(n) 因为我们只有一个 dfs 调用并利用从中返回的高度来确定高度平衡，所以它在线性时间内执行任务。
 *  `辅助空间：O(n)`

### (3)方法3: ###

*  按照下面的步骤来实现上面的想法： 定义一个辅助函数 `isBalancedfast`，它将`根节点作为输入并返回一对布尔值和整数值`，分别表示以`给定节点为根的树是否平衡及其高度`。
 *  定义递归的基本情况：`如果根节点为 NULL`，则返回一对，第一个设置为`true`，第二个设置为`0`。
 *  在当前节点的左右子树上递归调用`isBalancedfast`。
 *  `从返回的对中检索布尔值和整数值，并将它们设置为 leftAns、rightAns、leftHeight 和 rightHeight`。
 *  `取其左右子树的最大高度加1，计算当前节点的高度`。
 *  `检查左右子树高度的绝对差值是否小于等于1，如果是，则设置diff为true；否则，将其设置为 false。`
 *  如果 leftAns、rightAns 和 diff 都为真，则将 `ans.first`设置为真；否则，将其设置为 false。
 *  将 `ans.second`设置为`当前节点的高度`。 返回答案。
 *  定义一个`公共函数 isBalanced`，它将根节点作为输入并调用根节点上的 isBalancedfast 辅助函数。
 *  `返回 isBalancedfast 函数返回的对中的第一个元素`。这表示整个二叉树是否平衡。

class Node {
        
        int val;
        Node left, right;
     
        public Node(int v) {
        
            val = v;
            left = null;
            right = null;
        }
    }
     
    // 定义 Solution 类以检查二叉树是否平衡
    class Solution {
        
        // 确定二叉树是否平衡的辅助函数
        private Pair<Boolean, Integer> isBalancedfast(Node root) {
        
            // 基本情况：如果 root 为 null，则树是平衡的并且高度为 0
            if (root == null) {
        
                Pair<Boolean, Integer> p = new Pair<>(true, 0);
                return p;
            }
     
            // 在左右子树上递归调用 isBalancedfast 函数
            Pair<Boolean, Integer> left = isBalancedfast(root.left);
            Pair<Boolean, Integer> right = isBalancedfast(root.right);
     
            // 检索左右子树是否平衡
            boolean leftAns = left.first;
            boolean rightAns = right.first;
     
            //检查左右子树的高度差
            boolean diff = Math.abs(left.second - right.second) <= 1;
     
            // 创建一对来存储答案（树是否平衡）及其高度
            Pair<Boolean, Integer> ans = new Pair<>(false, Math.max(left.second, right.second) + 1);
     
            // 如果两个子树都是平衡的并且它们的高度最多相差 1，则树是平衡的
            if (leftAns && rightAns && diff) {
        
                ans = new Pair<>(true, Math.max(left.second, right.second) + 1);
            }
     
            return ans;
        }
     
        //检查二叉树是否平衡的函数。
        public boolean isBalanced(Node root) {
        
            return isBalancedfast(root).first;
        }
    }
     
    // Driver Code
    public class Main {
        
        public static void main(String[] args) {
        
            // 创建二叉树
            Node root = new Node(1);
            root.left = new Node(2);
            root.right = new Node(3);
            root.left.left = new Node(4);
            root.left.right = new Node(5);
            root.left.left.left = new Node(8);
     
            // 创建解决方案类的对象
            Solution obj = new Solution();
     
            // 使用 isBalanced 函数检查二叉树是否平衡
            if (obj.isBalanced(root)) {
        
                System.out.println("The given binary tree is balanced.");
            } else {
        
                System.out.println("The given binary tree is not balanced.");
            }
        }
    }

The given binary tree is not balanced.

`时间复杂度`： O(N) ，其中 N 是树中存在的节点数，这是因为树的每个节点都只被访问过。  
`辅助空间`： O(H) ，其中 h 是二叉树的高度。

## 5)排序数组到平衡 BST ##

*  给定一个排序数组。编写一个`使用数组元素创建平衡二叉搜索树的函数。`

Input: arr[] = {
        1, 2, 3}
    Output: A Balanced BST
          2
        /  \
     1     3 
    Explanation: all elements less than 2 are on the left side of 2 , and all the elements greater than 2 are on the right side
    
    Input: arr[] = {
        1, 2, 3, 4}
    Output: A Balanced BST
              3
            /  \
         2    4
       /
    1

### 方法1： 通过查找中间元素`将数组排序为平衡 BST` ###

#### (1)思路 ####

*  找到数组的中间元素并使它成为树的根，然后对根的左孩子的左子数组执行相同的操作，对根的右孩子的右子数组执行相同的操作。
 *  按照下面提到的步骤实施该方法：
    
     *  将数组的中间元素设置为根。
     *  对左半边和右半边递归地做同样的事情。
     *  获取左半部分的中间，并使其成为在步骤 1 中创建的根的左子节点。
     *  获取右半部分的中间，并使其成为在步骤 1 中创建的根的右子节点。
     *  打印树的预序

#### (2)代码 ####

class Node {
        
     
        int data;
        Node left, right;
     
        Node(int d)
        {
        
            data = d;
            left = right = null;
        }
    }
     
    class BinaryTree {
        
     
        static Node root;
     
        /*构造Balanced Binary Search的函数 来自排序数组的树 */
        Node sortedArrayToBST(int arr[], int start, int end)
        {
        
     
            /* Base Case */
            if (start > end) {
        
                return null;
            }
     
            /* 获取中间元素并使其成为根 */
            int mid = (start + end) / 2;
            Node node = new Node(arr[mid]);
     
            /* 递归构造左子树并使 它离开了根的孩子 */
            node.left = sortedArrayToBST(arr, start, mid - 1);
     
            /* 递归构造右子树并使 它是 root 的右孩子 */
            node.right = sortedArrayToBST(arr, mid + 1, end);
     
            return node;
        }
     
        /* 打印 BST 前序遍历的实用函数
         */
        void preOrder(Node node)
        {
        
            if (node == null) {
        
                return;
            }
            System.out.print(node.data + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
     
        public static void main(String[] args)
        {
        
            BinaryTree tree = new BinaryTree();
            int arr[] = new int[] {
         1, 2, 3, 4, 5, 6, 7 };
            int n = arr.length;
            root = tree.sortedArrayToBST(arr, 0, n - 1);
            System.out.println(
                "Preorder traversal of constructed BST");
            tree.preOrder(root);
        }
    }

PreOrder Traversal of constructed BST 
    4 2 1 3 6 5 7

*  时间复杂度：O(N)
 *  辅助空间：O(H) ~= O(log(N))，用于递归堆栈空间，其中 H 是树的高度。

### 方法 2：使用队列——迭代方法 ###

#### (1)思路 ####

*  首先用根节点初始化一个队列，循环直到队列为空。
 *  从队列中移除第一个节点并找到排序数组的中间元素。
 *  使用先前找到的中间节点创建新节点，并将左子节点设置为双端队列节点左子节点（如果存在），并将右子节点设置为双端队列节点右子节点。
 *  将新节点加入队列。
 *  将出队节点的右子节点设置为排序数组左侧的中间元素。
 *  如果出队节点有一个左子节点，则将其排入队列。
 *  返回根节点。

#### (2)代码 ####

class Node {
        
        int val;
        Node left;
        Node right;
     
        public Node(int val)
        {
        
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
     
    public class Main {
        
        // 将数组转换为 BST 的函数
        // 并返回创建树的根
        public static Node sortedArrayToBST(int[] nums)
        {
        
            //如果数组为空则返回 null
            if (nums.length == 0) {
        
                return null;
            }
     
            int n = nums.length;
            int mid = n / 2;
            Node root = new Node(nums[mid]);
            // 初始化队列
            Queue<Object[]> q = new LinkedList<>();
            // 将根及其索引推送到队列
            q.add(new Object[] {
         root,
                                 new int[] {
         0, mid - 1 } });
            q.add(new Object[] {
        
                root, new int[] {
         mid + 1, n - 1 } });
     
            while (!q.isEmpty()) {
        
                // 从队列中获取前面的元素
                Object[] curr = q.poll();
     
                // 获取父节点及其索引
                Node parent = (Node)curr[0];
                int[] indices = (int[])curr[1];
                int left = indices[0];
                int right = indices[1];
     
                // 如果有要处理的元素和父元素
                // 节点不为空
                if (left <= right && parent != null) {
        
                    mid = (left + right) / 2;
                    Node child = new Node(nums[mid]);
     
                    // 设置子节点为左孩子或右孩子
                    // 父节点的
                    if (nums[mid] < parent.val) {
        
                        parent.left = child;
                    }
                    else {
        
                        parent.right = child;
                    }
     
                    // 推动左右孩子和他们的
                    // 队列索引
                    q.add(new Object[] {
        
                        child, new int[] {
         left, mid - 1 } });
                    q.add(new Object[] {
        
                        child, new int[] {
         mid + 1, right } });
                }
            }
     
            return root;
        }
     
        // 打印前序遍历的函数
        // 构建的 BST
        public static void printBST(Node root)
        {
        
            if (root == null) {
        
                return;
            }
     
            System.out.print(root.val + " ");
            printBST(root.left);
            printBST(root.right);
        }
     
        public static void main(String[] args)
        {
        
            // create a sorted array
            int[] nums = {
         1, 2, 3, 4, 5, 6, 7 };
            Node root = sortedArrayToBST(nums);
            printBST(root);
        }
    }

4 2 1 3 6 5 7

*  时间复杂度：O(N)，其中 N 是数组中元素的数量。
 *  辅助空间：O(N)

[a093b7032c9e45c08f265843541a64e9.png]: https://img-blog.csdnimg.cn/a093b7032c9e45c08f265843541a64e9.png
[3c40e08548844b368541a0260e4c1d33.png]: https://img-blog.csdnimg.cn/3c40e08548844b368541a0260e4c1d33.png
[06c415b0b07b4cad8b2718b0ee565c6f.png]: https://img-blog.csdnimg.cn/06c415b0b07b4cad8b2718b0ee565c6f.png
[c96a9f409ec94009a9e7c402b9282d76.png]: https://img-blog.csdnimg.cn/c96a9f409ec94009a9e7c402b9282d76.png
[1c97c15d11714c74a3967c47d6e23901.png]: https://img-blog.csdnimg.cn/1c97c15d11714c74a3967c47d6e23901.png