gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-01 15:40:57 24 4
gpt4 key购买 nike

我有一个按 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;
}
}

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

最佳答案

你的树似乎无法 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),但是您需要更少的引用来存储整个事物,并且缓存性能应该更好。

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

关于java - 在添加到二叉搜索树之前对数组进行排序 Java,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8034220/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com