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

although purpose of question not make difference, state anyway. working on making method performs dijkstra's algorithm on graph. algorithm requires set u of unvisited cities. when city visited, must removed list.

so want use binary search tree set u because best data structure can think of allow me have big set of cities can search , delete efficiently.

the array of cities in alphabetical order, array indexes 1,2,..n, cities[0] = albany ny, cities[n] = yuma az.

i created binary search tree use, not self-balancing. if add of elements are, create linked list of height (n-1).

therefore, my question following: how can order array if add array in order, or order should add array bst resulting bst closer log(n)?

i using following constructor when creating bst:

//this constructor initialized bst city array //a node created city object, , appended  //the tree bst(city[] cities) {     (int = 0; < 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), second parameter                                         //root , first parameter passed methods parameter.   //append finds correct location node , inserts  // //append(bstnode,bstnode) adds newnode tree @ appropriate location //current used in recursive step // //append(city) creates new node city parameter , passes  // node 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 empty tree         root = newnode;         root.setdepth(0);         size = 1;     } else     {         //add 1 depth in each level of recursion         newnode.setdepth(current.getdepth() + 1);          //if newnode comes first in lexographical order compared current         // place left or go left         if (newnode.compareto(current) < 0)         {             if (current.getleft() == null)//if spot empty             {                 current.setleft(newnode);//place node                  size++;             } else             {                 append(newnode, current.getleft());//else recall method             }             //if newnode after current in lexographical order,             //place right or go right            } else if (newnode.compareto(current) > 0)         {             if (current.getright() == null)//if spot empty             {                 current.setright(newnode);//place node                  size++;             } else             {                 append(newnode, current.getright());//else recall method             }         } else//if newnode has data node has             //print error , not add         {             system.out.println("attempting append duplicate node.\nthe"                     + "city " + newnode.getdata().getname()                      + "already in node that"                     + "exists in bst.\nno element appended.");         }     }//end else*(root != null) }//end append(bstnode,bstnode) --------------------------------------------- 

for set of unvisited cities consider either hashmap<string, city> or hashset<city>. in either case lookup cost constant (i.e. o(1)) better o(log(n)) large enough n.

a common way implement dijkstra algorithm uses heap of nodes, ordered cost. in java might represented treemap<double, city> or set of cost-city pairs ordered cost, possibly based on priorityqueue. @ each step in algorithm, keep removing treemap.firstentry() until entry's value present in list of unvisited cities.

the entry's key gives minimum cost reach newly found city. having found new city, add cities has links heap, keyed on total cost reach each city. unless interested in alternative paths, there no point in adding cities have been reached heap.