在添加到二叉搜索树Java之前对数组进行排序 [英] sort Array before adding to a Binary Search tree Java
问题描述
我有一个按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;
}
}
这将被视为自平衡二进制搜索树吗?
您的树似乎不是自平衡的. 自平衡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)，但是您需要更少的引用来存储整个内容，并且缓存性能应该更好.
如果您需要一棵可变树并想使其高效，则可能需要使其自平衡，在这种情况下，向其中添加元素的顺序无关紧要./p>
I have an Array of Strings that are in order A-Z. I was wondering the best way to go about sorting them for a balanced binary search tree. My initial thought is to split the array up into the first half and the second half and then sort them individually.
Shouldn't I be able to use a recursive way to keep splitting it in half to get the next Node for the tree? I just can't wrap my head around it right now and thought I would ask if any one had any ideas. to lead me in the right direction or provide some examples. Thanks!
i am using my own BinaryTree Class and BinaryTreeNode Class. EDIT:
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;
}
}
would this be considered a Self balancing binary search tree?
Your tree doesn't seem to be self balancing. A self-balancing BST will take steps, after an insertion, or after a number of insertions, to ensure that it is (roughly) balanced.
If you only add the elements once and use the tree just for reads, you have your sorted array and then proceed as follows: select the element in the middle. create a root with it as key, and then recursively add the elements to its left (the smaller elements) as the left subtree of your root, and the elements to its right as the right subtree, respectively. You should end up with a BST that's more or less balanced. Example code:
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;
}
/* ... */
}
However, in this case, you could simply keep your elements in the sorted array, and use binary search to index into it, instead of a tree. The complexity should be the same, O(logn), but you need less references to store the whole thing, and cache performance should be better.
If you need to have a mutable tree, and want to make it efficient, you'd probably need to make it self-balanced, case in which the order in which you add your elements to it doesn't matter.
这篇关于在添加到二叉搜索树Java之前对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
