algorithm - 根据n log n时间的置换构造二叉树

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

注意 :-

我不需要平均时间n log n，但是最坏的时间。

我需要使用常规规则进行插入时得到的确切树。不允许使用AVL或红黑树。

这是一个分配问题。这是非常不平凡的。实际上乍看之下似乎是不可能的。我已经考虑了很多。我的观察:

我们用来证明排序花费至少n log n时间的参数并不能消除这种算法的存在。

如果始终可以在O(n)时间内找到大小在树大小的两个分数之间的子树，则可以轻松解决该问题。

选择root的中位数或左子级作为子树的根是行不通的。

最佳答案

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

直觉

该算法的主要直觉是基于以下陈述:

语句＃1 :如果BST包含值a和b(a < b)并且它们之间没有值，则A(值a的节点)是B(值b的节点)的父节点(可能是间接的)或B是A的父级(可能是间接父级)。

该语句显然是正确的，因为如果它们的最低共同祖先C是A和B以外的其他节点，则其c的值必须在a和b之间。请注意，语句＃1对于任何BST(平衡或不平衡)都是正确的。

语句＃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，并且由于树中a和b之间没有值，因此没有值可以是的正确子元素。节点A。

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

语句＃3 :在平衡的BST中，对于不在树中的任何x值，您都可以找到O(log(N))时间中最接近和最接近的值。

这直接从语句＃1和＃2得出:您需要的是在BST中找到x值的潜在插入点(取O(log(N)))，这两个值之一将是插入点的直接父级，并找到另一个您需要将树返回根(再次使用O(log(N)))。

因此，现在算法背后的想法变得很清楚:为了快速插入不平衡的BST中，我们需要找到值越来越小且最接近的节点。如果我们另外使用与目标(非平衡)BST相同的 key 以及该BST中的对应节点作为值来维护平衡的BST，则可以轻松地做到这一点。使用该附加数据结构，我们可以找到O(log(N))时间中每个新值的插入点，并使用O(log(N)) time中的新值来更新此数据结构。

算法

用root初始化“主要”的balancedRoot和null。

对于列表中每个值x的

，请执行以下操作:

(如果这是第一个值)，只需将其添加为两棵树的根节点，然后转到＃2

balancedRoot指定的树中的

查找与最接近的值(BalancedA，指向主BST中的节点A)和最接近的最大值(BalancedB，指向主BST中的节点B)相对应的节点。

如果没有最接近的较低值，即我们要添加最小元素，则将其作为左侧子元素添加到节点B

如果没有最接近的较大值，即我们要添加最大元素，则将其作为正确的子元素添加到节点A

查找树中的节点A或B中哪个较低。您可以使用存储在节点中的显式level。如果较低的节点是A(较少的节点)，则将x添加为A的直接右子，否则将x添加为B的直接左子(更大的节点)。另外(更巧妙)，您可能会注意到，从语句＃1和＃2可以得出，两个候选插入位置(A的右 child 或B的左 child )恰好将为空，这是您想要的位置插入您的值x。

将值x添加到平衡树(可能从步骤4重新使用)。

转到步骤2

由于循环的任何内部步骤都不会超过O(log(N))，因此总复杂度为O(N*log(N))
Java实现

我懒得自己实现平衡的BST，所以我使用了标准的Java TreeMap ，它实现了Red-Black树，并且具有与算法的步骤＃4相对应的有用的lowerEntry和higherEntry方法(您可以查看source code来确保两者都是实际上O(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));
    }
}