 |
AuD
Lecture 'Algorithmen und Datenstrukturen' (code examples)
|
|
AuD
Lecture 'Algorithmen und Datenstrukturen' (code examples)
|
Base class for a binary search tree. More...
Base class for a binary search tree.
Please keep in mind that this is an educational implementation. It is not optimized for a particular application!
The internal node (nested class aud.BinarySearchTree.Node) representation is based on aud.BinaryTree!
On the one hand, this choice enables us to reuse functionality. On the other hand, there are some disadvantages due to extra data that is stored or extra indirections for method calls.
BinarySearchTree stores head as a dummy node (member head_), which has has by definition a smaller key than any other node.
This implementation does not use dummy nodes as leaves!
Note that aud.BinaryTree#getLeft and aud.BinaryTree#getRight also update links to parents! While this is convenient in many cases, it requires special care in other cases! (Explicitly setting null references, order of operations matters "even more".)
Each aud.BinarySearchTree.Node stores a key-value pair of type aud.BinarySearchTree.Entry as node data.
BinarySearchTree is a generic class, and Key and Value are provided as type parameters.
The Key type must be comparable, i.e., extend Comparable<key>.
The rationale of storing key-value pairs is that this way the search tree can be used to implement a set or a map:
find or insert). A typical application for maps are dictionaries. Keys are compared by compareKeys, which treats null keys as smallest possible keys. Then head's key equals null by definition.
The method find searches a an entry for a given key.
The core function used for finding (find) a node by key and also for finding an insertion point (for insert) is findLowerBound). It returns a aud.BinarySearchTree.LowerBound instance (which stores the node and some additional information).
The method findEntry (and similarly getMinimum and getMaximum) returns a aud.BinarySearchTree.Cursor rather than a node.
aud.BinarySearchTree.Cursor provides a reference to nodes in the tree, i.e., allows access to its key and value.
The iterator() method implements Iterable<Cursor>, and this inorder traversal iterator provides Cursor instances. (With some more work, we could alternatively provide different iterators over keys, values, and key-value pairs/entries.)
Although this is not a balanced tree, BinarySearchTree provides methods for local rebalancing. These are
restructure based on the implementation in Goodrich and Tamassia (2nd ed, chapter 7.4, p. 269).rotateLeft single rotation, right-right case rotateRight single rotation, left-left case rotateLeftRight double rotation, left-right case rotateRightLeft double rotation, right-left case All of these call the auxiliary method setupBalancedSubtree (as does restructure) to perform the rotations. Note that an implementation that works exclusively with rotations (not restructuring), would probably implement the double rotations as a combination of two single rotations.
Especially restructure is used for balancing by sub-classes, e.g., aud.AVLTree.
The method restructure(char,Key) is provided for testing the above methods interactively (see aud.example.BinarySearchTreeExample).
Note that we excessively use the fact that an extra reference to the node's parent is stored. In fact, this allows a simple bottom-up processing as by restructure. A more (memory) efficient implementation would avoid these references at the cost of a more complex implementation!
insert provides a callback onInsert to notify a subclass of a change of the tree. Similarly, remove invokes onRemove.
These callback can be used by sub-classes for balancing and visualization/output.
Definition at line 137 of file BinarySearchTree.java.
1.9.5