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

Question

Although the purpose of this question will probably not make a difference, I will state it anyway. I am working on making a method that performs Dijkstra's Algorithm on a graph. The algorithm requires a set U of unvisited cities. When a city is visited, it must be removed from the list.

So I want to use a binary search tree for my set U because its the best data structure that I can think of that will allow me to have a big set of cities that I can search and delete from efficiently.

The array of cities is in alphabetical order, for an array with indexes 1,2,..n, cities[0] = Albany NY, cities[n] = Yuma AZ.

I created a binary search tree that I would like to use, however it is not self-balancing. If I add all of the elements as they are, it will just essentially create a linked list of height (n-1).

Therefore, my question is the following: How can I order the array if I add the array in order, or what order should I add the array to the BST so that the resulting BST is closer to log(n)?

I will be using the following constructor when creating the 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[]) ----------------------------------------------------------

the append methods used are:

//::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::\
//:::::::::::::::::  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

For your set of unvisited cities consider either a HashMap<String, City> or a HashSet<City>. In either case the lookup cost is constant (i.e. O(1)) which is better than O(log(n)) for large enough n.

A common way to implement the Dijkstra algorithm uses a heap of nodes, ordered by cost. In Java this might be represented by a TreeMap<Double, City> or a set of cost-city pairs ordered by cost, possibly based on a PriorityQueue. At each step in the algorithm, keep removing TreeMap.firstEntry() until the entry's value is present in the list of unvisited cities.

The entry's key gives you the minimum cost to reach the newly found city. Having found the new city, add all the cities to which it has links to the heap, keyed on the total cost to reach each city. Unless you are interested in alternative paths, there is no point in adding cities that have already been reached to the heap.