java - 在添加到二叉搜索树之前对数组进行排序 Java

Question

我有一个按 A-Z 顺序排列的字符串数组。我想知道对它们进行排序以获得平衡二叉搜索树的最佳方法。我最初的想法是将数组分成前半部分和后半部分，然后分别对它们进行排序。

我是否应该能够使用递归方式将其分成两半以获得树的下一个节点？我现在无法理解它，我想我会问是否有人有任何想法。引导我走向正确的方向或提供一些例子。谢谢!

我正在使用我自己的 BinaryTree 类和 BinaryTreeNode 类。 编辑:

public class BinaryTree {
private BinaryTreeNode root;

public void insert(String text) {

root = insertNode(root, text); 

}

private BinaryTreeNode insertNode(BinaryTreeNode curNode, String text) {
if (curNode == null) {
    BinaryTreeNode newNode = new BinaryTreeNode(text);
    //newNode.value = text;
    return newNode;
} else {
    if (text.compareTo(curNode.value) < 0 ) {
        //left child
        //use of recursion to properly place Node
        curNode.left = insertNode(curNode.left, text);
        return curNode;
    }

        else {

        //right
        //use of recursion to properly place Node
        curNode.right = insertNode(curNode.right, text);
        return curNode;
    }
}

}

public BinaryTreeNode getRoot() {
return root;
}

 public void setRoot(BinaryTreeNode root) {
this.root = root;
 }
 }

这会被视为自平衡二叉搜索树吗？

Answer 1

你的树似乎无法 self 平衡。一个self-balancing BST在一次插入或多次插入后将采取措施，以确保其(大致)平衡。

如果您仅添加元素一次并仅使用树进行读取，则您将获得排序后的数组，然后按以下步骤操作:选择中间的元素。使用它作为键创建一个根，然后分别递归地将其左侧的元素(较小的元素)添加为根的左子树，将其右侧的元素添加为右子树。您最终应该得到或多或少平衡的 BST。示例代码:

public class BinaryTree {

    /* ... */


    //each recursive call receives a pair of bounds for the part of the 
    //array it has to process: left and right
    public static BinaryTreeNode nodeFromSortedArray(String[]a,
                                           int left, int right){

        if (right<left) return null;

        if (right==left)
            return new BinaryTreeNode(a[left]);

        int mid = (left+right)/2;

        //create node from middle element
        BinaryTreeNode n = new BinaryTreeNode(a[mid]);

        //recursively add elements to the left as its right subtree
        n.left = nodeFromSortedArray(a, left, mid-1);

        //recursively add elements to the right as its right subtree
        n.right = nodeFromSortedArray(a, mid+1, right);

        return n;
    }

    public static BinaryTree fromSortedArray(String[]a){
        BinaryTree bt = new BinaryTree();
        bt.setRoot(nodeFromSortedArray(a,0,a.length-1));
        return bt;
    }

    /* ... */
}

但是，在这种情况下，您可以简单地将元素保留在排序数组中，并使用二分搜索来索引它，而不是使用树。复杂度应该是相同的，O(logn)，但是您需要更少的引用来存储整个事物，并且缓存性能应该更好。

如果您需要一棵可变树，并希望使其高效，您可能需要使其自平衡，在这种情况下，向其中添加元素的顺序并不重要。