排序一个数组来制作一个有点平衡的二叉搜索树

Question

虽然这个问题的目的可能不会有什么不同，但我还是要说明一下。我正在制作一种在图形上执行 Dijkstra 算法的方法。该算法需要一组 U 未访问过的城市。当访问一个城市时，它必须从列表中删除。

所以我想为我的集合 U 使用二叉搜索树，因为它是我能想到的最好的数据结构，它将允许我拥有一大组城市，我可以从中高效地搜索和删除。

城市数组按字母顺序排列，对于索引为 1,2,..n 的数组，cities[0] = Albany NY，cities[n] = Yuma AZ。

我创建了一个我想使用的二叉搜索树，但它不是自平衡的。如果我按原样添加所有元素，它实际上只会创建一个高度为 (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) ---------------------------------------------

Answer 1

对于您未访问过的城市集，请考虑 HashMap<String, City> 或 HashSet<City>。在任何一种情况下，查找成本都是恒定的（即 O(1)），对于足够大的 n，这比 O(log(n)) 更好。

实现 Dijkstra 算法的一种常用方法是使用按成本排序的节点堆。在 Java 中，这可能由 TreeMap<Double, City> 或一组按成本排序的成本-城市对表示，可能基于 PriorityQueue。在算法的每一步，继续删除 TreeMap.firstEntry()，直到条目的值出现在未访问城市列表中。

条目的密钥为您提供了到达新发现的城市的最低费用。找到新城市后，将所有与它有链接的城市添加到堆中，关键是到达每个城市的总成本。除非您对替代路径感兴趣，否则将已经到达的城市添加到堆中是没有意义的。

排序一个数组来制作一个有点平衡的二叉搜索树

order an array to make a somewhat-balanced binary search tree

java

arrays

binary-search-tree