在n log n时间内根据排列构造二叉树

Question

数字1到n以指定顺序p_1,p_2,...,p_n插入二叉搜索树中.描述一个O(nlog n)时间算法来构造最终的二进制搜索树.

注意 :-

1. 我不需要平均时间n log n,但是最差的时间.
2. 我需要使用通常的规则进行插入时产生的确切树.不允许AVL或红黑树.

这是一个作业问题.这非常非常重要.事实上,乍一看似乎是不可能的.我已经考虑过了很多.我的观察: -

1. 我们用来证明排序至少花费n log n时间的论点并没有消除这种算法的存在.
2. 如果总是可以在O(n)时间内找到一个子树,其大小在树的两个分数之间,则问题可以很容易地解决.
3. 选择root的中位数或左子项作为子树的根不起作用.

Answer 1

由于 David Eisenstat 没有时间扩展他的答案，我将尝试将更多细节放入类似的算法中。

直觉

该算法背后的主要直觉基于以下陈述：

语句#1：如果 BST 包含值a和b( a < b) 并且它们之间没有值，则A(value 的节点a) 是 ( Bvalue 的节点) 的（可能间接）父节点b，或者B是 的（可能间接）父节点A。

这个说法显然是正确的，因为如果它们的最低公共祖先是和C之外的其他节点，那么它的值必须在和 之间。请注意，语句 #1 对于任何 BST（平衡或不平衡）都成立。ABcab

语句 #2：如果一个简单（不平衡）BST 包含值a和b( a < b) 并且它们之间没有值并且我们试图添加值x使得a < x < b，那么X（值的节点x）将是或的直接右（更大）子A节点B树中较低节点的直接左（少）子节点。

我们假设两个节点中较低的一个a（另一种情况是对称的）。在插入阶段，值x将沿着与插入期间相同的路径行进a，因为树不包含a和之间的任何值x，即在任何比较值处a并且x是无法区分的。这意味着该值x将导航树直到节点A，并将B在较早的步骤中传递节点（参见语句#1）。因为x > a它应该成为 的右孩子A。A此时，的直接右子节点必须为空，因为A位于B的子树中，即该子树中的所有值都小于，并且由于树中和b之间没有值，因此没有值可以是节点 的右子节点。abA

请注意，对于执行重新平衡后的某些平衡 BST，语句 #2 可能不正确，尽管这应该是一个奇怪的情况。

语句#3：在平衡 BST 中，对于x尚未在树中的任何值，您可以及时找到最接近的较大值和最接近的较小值O(log(N))。

x这直接来自语句 #1 和 #2：您所需要的只是找到BST 中值的潜在插入点（需要O(log(N))），两个值之一将是插入点的直接父级，并找到您需要的另一个值将树返回到根（再次需要O(log(N))）。

所以现在算法背后的想法变得清晰了：为了快速插入不平衡的 BST，我们需要找到具有最接近的较小值和较大值的节点。如果我们另外维护一个平衡的 BST，其键与我们的目标（不平衡）BST 相同，并且以该 BST 中的相应节点作为值，我们就可以轻松做到这一点。使用该附加数据结构，我们可以及时找到每个新值的插入点，并及时O(log(N))用新值更新该数据结构。O(log(N))

算法

1. 初始化“main”root并balancedRoot使用null.
2. 对于x列表中的每个值执行以下操作：
3. 如果这是第一个值，只需将其作为根节点添加到两棵树中，然后转到#2
4. 在由 指定的树中balancedRoot查找与最接近的较小值（BalancedA，指向A主 BST 中的节点）和最接近的较大值（BalancedB，指向B主 BST 中的节点）相对应的节点。
5. • 如果没有最接近的较低值，即我们要添加最小元素，请将其作为左子节点添加到节点B
   • 如果没有最接近的较大值，即我们要添加最大元素，请将其作为右子节点添加到节点A
   • 查找树中较低的节点A或。B您可以使用显式level存储在节点中。如果较低节点是A（较小节点），则添加x为直接右子节点，A否则添加x为（较大节点）的直接左子节点B。A或者（更聪明地），您可能会注意到，从语句 #1 和 #2 可以看出，两个候选插入位置（的右子节点或的左子节点）之一B将为空，这就是您想要插入的位置你的价值x。

6. x为平衡树添加价值（可能会重复使用步骤 #4）。

7. 转到步骤#2

由于循环的内部步骤不超过O(log(N))，因此总复杂度为O(N*log(N))

Java实现

我懒得自己实现平衡 BST，所以我使用了标准 JavaTreeMap来实现红黑树，并且具有与算法的步骤 #4 相对应的有用方法lowerEntry和方法（您可以查看源代码以确保两者实际上都是） 。higherEntryO(log(N))

import java.util.Map;
import java.util.TreeMap;

public class BSTTest {

    static class Node {
        public final int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }

        public boolean compareTree(Node other) {
            return compareTrees(this, other);
        }

        public static boolean compareTrees(Node n1, Node n2) {

            if ((n1 == null) && (n2 == null))
                return true;
            if ((n1 == null) || (n2 == null))
                return false;
            if (n1.value != n2.value)
                return false;
            return compareTrees(n1.left, n2.left) &&
                    compareTrees(n1.right, n2.right);
        }


        public void assignLeftSafe(Node child) {
            if (this.left != null)
                throw new IllegalStateException("left child is already set");
            this.left = child;
        }

        public void assignRightSafe(Node child) {
            if (this.right != null)
                throw new IllegalStateException("right child is already set");
            this.right = child;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }


    static Node insertToBst(Node root, int value) {
        if (root == null)
            root = new Node(value);
        else if (value < root.value)
            root.left = insertToBst(root.left, value);
        else  
            root.right = insertToBst(root.right, value);
        return root;
    }


    static Node buildBstDirect(int[] values) {
        Node root = null;
        for (int v : values) {
            root = insertToBst(root, v);
        }
        return root;
    }

    static Node buildBstSmart(int[] values) {
        Node root = null;
        TreeMap<Integer, Node> balancedTree = new TreeMap<Integer, Node>();
        for (int v : values) {
            Node node = new Node(v);
            if (balancedTree.isEmpty()) {
                root = node;
            } else {
                Map.Entry<Integer, Node> lowerEntry = balancedTree.lowerEntry(v);
                Map.Entry<Integer, Node> higherEntry = balancedTree.higherEntry(v);
                if (lowerEntry == null) {
                    // adding minimum value
                    higherEntry.getValue().assignLeftSafe(node);
                } else if (higherEntry == null) {
                    // adding max value
                    lowerEntry.getValue().assignRightSafe(node);
                } else {
                    // adding some middle value
                    Node lowerNode = lowerEntry.getValue();
                    Node higherNode = higherEntry.getValue();
                    if (lowerNode.right == null)
                        lowerNode.assignRightSafe(node);
                    else
                        higherNode.assignLeftSafe(node);
                }
            }
            // update balancedTree
            balancedTree.put(v, node);
        }
        return root;
    }

    public static void main(String[] args) {
        int[] input = new int[]{7, 6, 9, 4, 1, 8, 2, 5, 3};

        Node directRoot = buildBstDirect(input);
        Node smartRoot = buildBstSmart(input);
        System.out.println(directRoot.compareTree(smartRoot));
    }
}