46

参考： 我被问到这个问题@MS SDE 面试，第三轮。这不是作业问题。我也考虑了一下，并在下面提到了我的方法。

问题： 修改 BST 使其尽可能平衡。不用说，您应该尽可能高效地进行操作。

提示： 面试官说这是一个合乎逻辑的问题，如果你有不同的想法就会得到答案。不涉及困难的编码。
--> 话虽如此，我不认为他希望我指向 AVL/RB Trees。

我的解决方案： 我建议，我会按顺序遍历树，将中间元素作为新树的根（我们称之为新根）。然后到中间元素的左边，把它的中间元素作为树根新根的左子树的根。同样做正确的部分。递归执行此操作将给出最佳平衡 BST。

为什么我在这里发布它： 但他对答案不满意:(那么，真的有办法做到这一点而无需使用权重/RB着色策略，还是他只是在和我开玩笑？请输入你的专家想法。

复制？不！ 我知道有这个问题，但是请求者提出的解决方案太复杂了，另一个人谈到了 AVL 树。

4

4 回答 4

43

您可能想研究Day-Stout-Warren算法，它是一种 O(n) 时间、O(1) 空间算法，用于将任意二叉搜索树重塑为完整的二叉树。直观地说，该算法的工作原理如下：

  1. 使用树旋转，将树转换为退化链表。
  2. 通过对链表应用选择性旋转，将链表转换回完全平衡的树。

该算法的美妙之处在于它以线性时间运行并且只需要恒定的内存开销；实际上，它只是重塑底层树，而不是创建新树并复制旧数据。编写代码也相对简单。

希望这可以帮助！

于 2012-12-25T05:07:50.683 回答
17

“尽可能平衡” =​​ 完整（或完整）二叉树1。你不能比它更平衡。

解决方案很简单 - 构建一个“空”完整二叉树，并以中序遍历的方式迭代新树和输入树（同时）以填充完整树。

完成后，您可以获得最平衡的树，这种方法的时间复杂度为O(n).

编辑：
这应该按照以下步骤完成：

  1. 构建一个带有n节点的虚拟完整树。每个节点的所有值都将被初始化为一些垃圾值。
  2. 创建两个迭代器：(1)originalIter用于原始树，(2)newIter用于新的（用垃圾初始化的）树。两个迭代器都将按顺序遍历返回元素。

  3. 执行以下操作以使用原始值填充树：

     while (originalIter.hasNext()):
      newIter.next().value = originalIter.next().value

（1）（来自维基百科）：完全二叉树是一棵二叉树，其中除了可能的最后一层之外，每一层都被完全填满，并且所有节点都尽可能靠左

于 2012-12-22T09:46:50.173 回答
12

DSW算法可以解决这个是O(n)时间。算法如下：

1] Using right-rotation operations, turn the tree into a linked list
   (a.k.a. backbone or vine)
2] Rotate every second node of the backbone about its parent to turn
   the backbone into a perfectly balanced BST.

参考

于 2013-08-30T08:44:06.447 回答
1

这会将您的正常 BST 转换为在 O(n) 中具有最小可能高度的平衡 BST。首先，保存所有排序到向量中的节点。然后，根是中间元素，递归地从 0 到 mid-1 构建一棵树作为它的左边，并从 mid+1 到 vector.size()-1 构建一棵树作为它的右孩子。在所有这些步骤之后，根保持平衡的 BST 与最小高度。

    import java.util.Vector;

        public class ConvertBSTIntoBalanced {

            public static void main(String[] args) {
                TreeNode node1 = new TreeNode(1);
                TreeNode node2 = new TreeNode(2);
                TreeNode node3 = new TreeNode(3);
                TreeNode node4 = new TreeNode(4);
                node1.right = node2;
                node2.right = node3;
                node3.right = node4;
                ConvertBSTIntoBalanced convertBSTIntoBalanced = new ConvertBSTIntoBalanced();
                TreeNode balancedBSTRoot = convertBSTIntoBalanced.balanceBST(node1);
            }

            private void saveNodes(TreeNode node, Vector<TreeNode> nodes) {
                if (node == null)
                    return;
                saveNodes(node.left, nodes);
                nodes.add(node);
                saveNodes(node.right, nodes);
            }

            private TreeNode buildTree(Vector<TreeNode> nodes, int start, int end) {
                if (start > end)
                    return null;
                int mid = (start + end) / 2;
                TreeNode midNode = nodes.get(mid);
                midNode.left = buildTree(nodes, start, mid - 1);
                midNode.right = buildTree(nodes, mid + 1, end);
                return midNode;
            }

            public TreeNode balanceBST(TreeNode root) {
                Vector<TreeNode> nodes = new Vector<>();
                saveNodes(root, nodes);
                return buildTree(nodes, 0, nodes.size() - 1);
            }

        public class TreeNode {

        public Integer val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(Integer x) {
            val = x;
        }

    }

        }

我希望它有所帮助。

于 2020-04-03T11:44:36.340 回答