Java Reference
In-Depth Information
23. Tree traversal schemes include preorder traversal, inorder traversal, and
postorder traversal.
24. Postorder traversal of an expression tree yields the instructions for evaluating
the expression on a stack-based calculator.
25. The
TreeSet
class uses a form of balanced binary trees that guarantees that
adding and removing an element takes O(log(n)) time.
26. To use a tree set, the elements must be comparable.
27. When removing an element from a priority queue, the element with the highest
priority is retrieved.
28. A heap is an almost complete tree in which the values of all nodes are at most
as large as those of their descendants.
29. Inserting or removing a heap element is an O(log(n)) operation.
30. The regular layout of a heap makes it possible to store heap nodes efficiently in
an array.
31. The heapsort algorithm is based on inserting elements into a heap and removing
them in sorted order.
32. Heapsort is an O(n log(n)) algorithm.
757
758
CLASSES, OBJECTS, AND METHODS INTRODUCED IN THIS
CHAPTER
java.util.Collection<E>
contains
remove
size
java.util.HashMap<K, V>
java.util.HashSet<K, V>
java.util.Map<K, V>
get
keySet
put
remove
