tree height parent level balanced
tree height parent level balanced
balanced leaf level parent tree
public void print() {
LLNode<T> curr = front;
while (curr != null) {
System.out.println(curr.getInfo());
curr = curr.getLink();
}
public void addFront(T element) {
LLNode<T> newnode = new LLNode<T>(element);
newnode.setLink(front);
front = newnode;
// if this is the only node, make rear point to it
if (read == null)
rear = newnode;
numElements++;
}
public void add(T element) {
// Adds element to this list.
int i = 0;
int k;
boolean locfound = false;
// loop till we find a bigger element or reach the end
while (i < numElements && !locfound) {
if (list[i].equals(element))
throw new DuplicateElementException();
// if list[i] is greater then add element before it
if (comp.compare(list[i],element) > 0)
locfound = true;
else
i++;
}
// if a bigger element was not found, add at the end
if (!locfound)
list[numElements] = element;
// otherwise move later elements to make room for new one
// i is location where the new element will be placed
else {
for (k = numElements ; k > i ; k--)
list[k] = list[k-1];
list[i] = element;
}
numElements++;
}
public T smallest() {
int i;
if (numElements == 0)
return null;
T small = elements[0];
for (i = 1 ; i < numElements ; i++)
if (elements[i].compareTo(small) < 0)
small = elements[i];
return small;
}
public T smallest() {
LLNode<T> curr;
if (numElements == 0)
return null;
T small = front.getInfo();
for (curr = front ; curr != null ; curr = curr.getLink())
if (curr.getInfo().compareTo(small) < 0)
small = curr.getInfo();
return small;
}
public static ClassA smallest(ListInterface<ClassA> mylist) {
int i;
ClassA small, curr;
if (mylist.size() == 0)
return null;
small = mylist.get(0);
for (i = 1 ; i < numElements ; i++) {
curr = mylist.get(i);
if (curr.compareTo(small) < 0)
small = curr;
}
return small;
}
public static ClassA smallest(ListInterface<ClassA> mylist) {
int i;
ClassA small, curr;
Comparator<ClassA> mycomp = ClassA.comp();
if (mylist.size() == 0)
return null;
Iterator<ClassA> iter = mylist.iterator();
small = iter.next();
while (iter.hasNext() {
curr = mylist.next();
if (mycomp.compare(curr, small) < 0)
small = curr;
}
return small;
}
public void removeAll(T target) {
int curr = 0;
while (curr < numElements-1) {
if (elements[curr].equals(target)) {
elements[curr] = elements[numElements-1];
numElements--;
}
else
curr++;
}
}
public static void removeAll(ArrayCollection<String> collect, String target) {
String str = collect.get(target);
while (str != null) {
collect.remove(str);
str = collect.get(target);
}
}
public class Visit implements Comparable<T> { private String name; private String continent; int year; int month; public Visit(String nn, String cc, int yy, int mm) { name = nn; continent = cc; year = yy; month = mm; } public String toString() { return "Country: " + name + "\nContinent: " + continent + "\nDate: " + month + "/" + year + "\n"; } public int compareTo(Visit visit) { return name.compareTo(visit.name); } public boolean equals(Object ob) { if (ob == null || !(ob instanceof Visit)) return false; Visit visit = (Visit) ob; if (continent.equals(visit.continent) && name.equals(visit.name)) return true; return false; } }Visit one = new Visit("Venezuela", "South America", 12, 2012); Visit two = new Visit("Spain", "Europe", 5, 2007); Visit three = new Visit("Italy", "Europe", 6, 2010); Visit four = new Visit("China", "Asia", 6, 2005); SortedABList<Visit> trips = new SortedABList<Visit>(); trips.add(one); trips.add(two); trips.add(three); trips.add(four); for (Visit trip : trips) System.out.println(trip);public static Comparator<Visit> dateCountryComp() { return new Comparator<Visit> () { public int compare(Visit v1, Visit v2) { if (v1.year != v2.year) return v1.year - v2.year; if (v1.month != v2.month) return v1.month - v2.month; return v1.name.compareTo(v2.name); } }; }This method is part of the Visit class.SortedABList<Visit> trips = new SortedABList<Visit>(Visit.dateCountryComp()); trips.add(new Visit("Venezuela", "South America", 12, 2012)); trips.add(new Visit("Spain", "Europe", 5, 2007)); trips.add(new Visit("Italy", "Europe", 6, 2010)); trips.add(new Visit("China", "Asia", 6, 2005)); for (Visit trip : trips) System.out.println(trip);public static Comparator<Visit> contCountryDateComp() { return new Comparator<Visit> () { public int compare(Visit v1, Visit v2) { int comp = v1.continent.compareTo(v2.continent); if (comp != 0) return comp; comp = v1.name.compareTo(v2.name); if (comp != 0) return comp; if (v1.year != v2.year) return v1.year - v2.year; return v1.month - v2.month; } }; }This method is part of the Visit class.SortedABList<Visit> trips = new SortedABList<Visit>(Visit.dateCountryComp()); trips.add(new Visit("Venezuela", "South America", 12, 2012)); trips.add(new Visit("Spain", "Europe", 5, 2007)); trips.add(new Visit("Italy", "Europe", 6, 2010)); trips.add(new Visit("China", "Asia", 6, 2005)); Visit visit; tripIter = trips.iterator(); while (tripIter.hasNext()) { visit = tripIter.next(); System.out.println(visit); }
- The following code is added to the ArrayCollection class, which
now must implement Iterable<T>:
public Iterator<T> iterator() { return new ArrayCollIter(); } class ArrayCollIter implements Iterator { private int previousPos = -1; // last position we have returned in the iteration // create the iterator public ArrayCollIter() { } public boolean hasNext() { // Returns true if the iteration has more elements; otherwise returns false. // if previousPos is at the end of the list, we are done return (previousPos < (numElements - 1)) ; } public T next() { // Returns the next element in the iteration. // Throws NoSuchElementException - if the iteration has no more elements if (!hasNext()) throw new IndexOutOfBoundsException("Illegal invocation of next " + " in ArrayCollection iterator.\n"); previousPos++; return elements[previousPos]; } } // end of ArrayCollIter class ArrayCollection<Visit> trips = new ArrayCollection<Visit>(); trips.add(new Visit("Venezuela", "South America", 12, 2012)); trips.add(new Visit("Spain", "Europe", 5, 2007)); trips.add(new Visit("Italy", "Europe", 6, 2010)); trips.add(new Visit("China", "Asia", 6, 2005)); Visit visit; tripIter = trips.iterator(); while (tripIter.hasNext()) { visit = tripIter.next(); System.out.println(visit); }ArrayCollection<Visit> trips = new ArrayCollection<Visit>(); trips.add(new Visit("Venezuela", "South America", 12, 2012)); trips.add(new Visit("Spain", "Europe", 5, 2007)); trips.add(new Visit("Italy", "Europe", 6, 2010)); trips.add(new Visit("China", "Asia", 6, 2005)); for (Visit visit : trips)) { System.out.println(visit); }- The following code replaces the code in part 2 above. It
is added to the ArrayCollection class, which still implements
Iterable<T>:
public Iterator<T> iterator() { // the return statement creates a new iterator and the definition // of the Iterator class starts with the { return new Iterator<T>() { private int previousPos = -1; public boolean hasNext() { // Returns true if the iteration has more elements; otherwise returns false. return (previousPos < (size() - 1)) ; } public T next() { // Returns the next element in the iteration. // Throws NoSuchElementException - if the iteration has no more elements if (!hasNext()) throw new IndexOutOfBoundsException("Illegal invocation of next " + " in ArrayCollection iterator.\n"); previousPos++; return elements[previousPos]; } }; // end of return statement } // end of iterator() method - The code in parts 2 and 3 remains the same.
- The following code is added to the LinkedCollection class, which
now must implement Iterable<T>:
public Iterator<T> iterator() { return new LinkedIterator(); } // inner class for iterator private class LinkedIterator implements Iterator { private LLNode<T> loc = head; public boolean hasNext() { return loc != null; } public T next() { if (loc == null) throw new IndexOutOfBoundsException("invalid next in LinkedIterator"); T nextval = loc.getInfo(); loc = loc.getLink(); return nextval; } } // end of LinkedIterator LinkedCollection<Visit> trips = new LinkedCollection<Visit>(); trips.add(new Visit("Venezuela", "South America", 12, 2012)); trips.add(new Visit("Spain", "Europe", 5, 2007)); trips.add(new Visit("Italy", "Europe", 6, 2010)); trips.add(new Visit("China", "Asia", 6, 2005)); Visit visit; tripIter = trips.iterator(); while (tripIter.hasNext()) { visit = tripIter.next(); System.out.println(visit); }LinkedCollection<Visit> trips = new LinkedCollection<Visit>(); trips.add(new Visit("Venezuela", "South America", 12, 2012)); trips.add(new Visit("Spain", "Europe", 5, 2007)); trips.add(new Visit("Italy", "Europe", 6, 2010)); trips.add(new Visit("China", "Asia", 6, 2005)); for (Visit visit : trips)) { System.out.println(visit); }- The following code replaces the code in part 2 above. It
is added to the LinkedCollection class, which still implements
Iterable<T>:
// anonymous inner class for iterator public Iterator
iterator() { return new Iterator () { private LLNode loc = head; public boolean hasNext() { return loc != null; } public T next() { if (loc == null) throw new IndexOutOfBoundsException("invalid next in Collection iterator"); T nextval = loc.getInfo(); loc = loc.getLink(); return nextval; } }; // end of inner class & return stmt } // end of iterator method - The code in parts 2 and 3 remains the same.
- In the best case there is room in the array and we are adding the new element at position numElements. This only takes a few statements to add the element to the array, so the complexity is O(1). In the worst case the array is full and the element is being added at position [0]. Enlarge is called, which copies all list elements from the old array to the new array. This is followed by moving all elements to make room for the new element at position [0]. Both of these take N steps, for a total of approximately 2N steps, which is O(N).
- In the best case there is room in the array, so it takes only a few statements to add the new element at position numElements. Thus the complexity is O(1). In the worst case the array is full, so enlarge is called. Enlarge copies all list elements from the old array to the new array; this makes the add method O(N).
- In the best case the element being removed is the one at the end of the list, which requires only a few statements. This is O(1). All elements are moved down to close the gap left by the removed element so the worst case occurs when the element to be removed is at location [0]. Thus the operation is O(N).
- The method must search for the element to be removed, then remove it and close the gap that is left. There is no difference between the best and worst cases; both are O(N). If the element is in location [0] then it is found right away but there are N steps to move all elements down to fill the gap. If the element is in location [1] then it is found after one step and there are N-1 steps to move all elements down to fill the gap. If we continue this reasoning we can see that N steps are always required.
- This method is O(1) in the best and worst cases, because the location can be accessed in the array in one step.
- The array must be searched to find the element. In the best case it is found right away, so the complexity is O(1). In the worst case it is found at the end of the array, so the complexity is O(N).
- The method has to find the element in position i-1 to add the new element after it. In the best case the new element is being added at the beginning of the list, so only a few statements are needed to link it in. This is O(1). In the worst case the new element is being added in location N. This means that the find method has to loop to find location N-1, and then needs a few statements to link the new element into the list. The loop to find the location to insert makes the method O(N).
- The method uses the rear pointer to add the new element at the end of the list. This takes a few statements in any case. So the best and worst case are both O(1).
- Find is called to get a pointer to the element in location index (and it's predecessor). After the find it takes a few statements to remove the element. In the best case the element is at the front of the list and is found right away, so the method is O(1). In the worst case the element is at the end of the list so it takes N steps to find it, which makes the method O(N).
- As with the other version of remove, if the element is at the front of the list it will be found right away and the best case is O(1). And the worst case is when the element is at the end so the complexity is O(N) because it takes N steps to find the element.
- The get method calls find which has to loop to find the element in location index. The best case is when index is 0, so no loop is needed and the method is O(1). The worst case is when index is numElements - 1, which makes find loop N-1 times. This makes the complexity O(N).
- The get method calls find which has to loop to find the element. The best case is when the element is found at the front of the list, so no loop is needed and the method is O(1). The worst case is when the element is at the end of the list, which makes find loop N times. This makes the complexity O(N).