Searching a linked list (sorted or not) takes time O(N), but insertion (once found) takes time O(1). Searching a sorted array list takes time O(log N), but insertion so as to maintain the sorted order requires O(N). The goal here is to use a tree to implement a list-like interface so that both in-order insert and search take time O(log N). The data will be String. The class will be called StrList.
We will also make Get(k) work in time O(log N).
The interface you are to implement for StrList is the following:
Normally we think of a list as a linear structure. What does "linear" mean? Perhaps the most basic attribute of linear structure is the get(k) operation. However, the linear structure here is always sorted: as a result, we will not support add() or set(int k, string s) as these aren't consistent with ordered lists.
Note that implementing a list interface with a tree structure is a good example of the benefits of separating interface from structure.
The trickiest is probably get(int k). Finding the kth element is straightforward (sort of) if you do in-order traversal of the tree and stop at the kth element, but that is O(N). (Also, it's tricky to stop a recursive traversal before completion. Can you think of a good way to do this?)
As with insert() and search(), the one-parameter version will call a recursive two-parameter version get(k,t), where the second parameter is a TreeNode.
We want to check at most one node per level of the tree, which is O(log N) if the tree is even remotely balanced. The idea is to maintain, at each TreeNode t, a "cached" copy of the size of the subtree rooted by t; this is the contents of the count_ field. To maintain this size property, the value of count_ must be updated on every insertion within the subtree.
To find the kth element of the list, suppose we've recursively arrived at TreeNode t. Let lcount be the size of t.left() (that is, t.left().count(), unless t.left() is null, in which case lcount==0). Then:
The hard part, actually, is making sure count_ is updated when new values are inserted into the tree. This is done for you by my rinsert() method for the comp<0 case, but you need to extend it to the comp>0 (t.right() subtree) case (where the //FIX THIS comments appear). If you do it correctly there, following the example of the left-subtree case, then the counts will be fixed all the way up the tree. (Why?). It is essential that rinsert() return true if a value was inserted, and false if a value was not inserted, so parent calls can tell whether they should update their counts.
You should fix the count-setting part of rinsert() before trying to implement get(k), because the latter depends on the former. You can check your counts by looking carefully at the output of inTraverse(). Here's what it should look like for slist2:
antelope (1)
eats (3)
fresh (1)
grass, (7)
plays (1)
with (3)
zebra (1)
Note that, at each node t, count_ represents the size of subtree t.
The test code provided in SListDriver.java includes insert1() and insert2(); the former creates an unbalanced tree and the latter creates a balanced tree. The inTraverse() method prints count_, and can be used to determine whether your count_ values are correct.
To test get(k), use code like this (from main()):
for (int n = 0; n < slist.size(); n++) { System.out.printf("string %d is %s%n", n, slist.get(n)); }To test search, use the search() method below (and in the project file), and then search for a few strings:
search("zebra",sl); search("aardvark",sl); search("grass,",sl); search("eats",sl); search("food",sl); public static void search(string s, strlist t) { if (t.search(s)) Console.WriteLine("string \"{0}\" was found", s); else Console.WriteLine("string \"{0}\" was NOT THERE", s); }