尽管这个问题的目的可能不会有什么不同，但我还是会说明的。我正在制作一种在图上执行Dijkstra算法的方法。该算法需要一组U个未访问的城市。访问城市时，必须将其从列表中删除。
所以我想对我的集合U使用二进制搜索树，因为它是我能想到的最好的数据结构，可以让我有一个大的城市集，我可以有效地搜索和删除。
对于索引为1,2、..的数组，城市数组按字母顺序排列，。。n、 cities[0]=纽约州奥尔巴尼市，cities[n]=亚利桑那州尤马市。
我创建了一个我想使用的二进制搜索树，但它不是自我平衡的。如果我按原样添加所有元素，它实际上只会创建一个高度(n-1)的链表。
因此，我的问题如下：如果我按顺序添加数组，我如何对数组进行排序，或者我应该按什么顺序将数组添加到BST中，以便得到的BST更接近log(n)？
创建BST:时，我将使用以下构造函数
//this constructor initialized a BST with a City array
//a node is created with the City object, and then appended to
//the tree
BST(City[] cities)
{
for (int i = 0; i < cities.length; i++)
{
BSTNode newNode = new BSTNode(cities[i]);
append(newNode);
}
}//end BST(int[]) ----------------------------------------------------------
使用的附加方法有：
//::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
//::::::::::::::::: APPEND METHODS :::::::::::::::::::::::::::::::::::::|
//::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::/
//append (BSTNode) calls append(BSTNode,BSTNode), with the second parameter
//root and first parameter passed from this methods parameter.
//append finds the correct location for a node and inserts it
//
//append(BSTNode,BSTNode) adds newNode to the tree at the appropriate location
//current is used in the recursive step
//
//append(City) creates a new node with the City parameter and passes that
// node as a parameter in append(BSTNode)
public void append(City city)
{
BSTNode newNode = new BSTNode(city);
append(newNode);
}//end append(int) --------------------------------------------------------
public void append(BSTNode newNode)
{
append(newNode, root);
}//end append(BSTNode) ----------------------------------------------------
private void append(BSTNode newNode, BSTNode current)
{
if (root == null)
{
//setup root node for an empty tree
root = newNode;
root.setDepth(0);
size = 1;
} else
{
//add 1 to depth in each level of recursion
newNode.setDepth(current.getDepth() + 1);
//if newNode comes first in lexographical order compared to current
// then place left or go left
if (newNode.compareTo(current) < 0)
{
if (current.getLeft() == null)//if spot is empty
{
current.setLeft(newNode);//place node
size++;
} else
{
append(newNode, current.getLeft());//else recall this method
}
//if newNode is after current in lexographical order, then
//place right or go right
} else if (newNode.compareTo(current) > 0)
{
if (current.getRight() == null)//if spot is empty
{
current.setRight(newNode);//place node
size++;
} else
{
append(newNode, current.getRight());//else recall method
}
} else//if newNode has data that another node already has then
//print error and do not add
{
System.out.println("Attempting to append a duplicate node.nThe"
+ "city " + newNode.getData().getName()
+ "already is in a node that"
+ "exists in this BST.nNo element appended.");
}
}//end else*(root != null)
}//end append(BSTNode,BSTNode) ---------------------------------------------
对于您的未访问城市集，请考虑HashMap<String, City>或HashSet<City>。在任何一种情况下，查找成本都是恒定的(即O(1))，对于足够大的n，这比O(log(n))要好。
实现Dijkstra算法的一种常见方法是使用按成本排序的节点堆。在Java中，这可能由一个TreeMap<Double, City>或一组按成本排序的成本-城市对表示，可能基于PriorityQueue。在算法的每一步，不断删除TreeMap.firstEntry()，直到条目的值出现在未访问的城市列表中。
入口的钥匙为您提供到达新发现的城市的最低费用。找到新城市后，将其链接到的所有城市添加到堆中，关键是到达每个城市的总成本。除非你对替代路径感兴趣，否则将已经到达的城市添加到堆中是没有意义的。