CS 2114 Chapter Notes - Chapter 25: Binary Search Tree, Binary Tree, Iterator
29 Apr 2018
School
Department
Course
Professor
Daniel T. Eisert CS-2114
1
25 – Binary Search Tree Implementations
Reading XII
CS-2114: Software Design & Data Structures
Setting the Stage
Recall that a binary search tree is a binary tree whose nodes contain Comparable
objects and are organized as follows. For each node in the tree:
1. The data in a node is greater than the data in the node’s left subtree.
2. The data in a node is less than the data in the node’s right subtree.
Also recall that a Comparable object belongs to a class that implements the interface
Comparable (which requires a compareTo method).
A Binary Search
Tree Interface
The SearchTree Interface:
- Null values are not allowed to be included in the search tree; however, the
above methods can return null to indicate failure.
- Entries in a search tree must be distinct.
• EXAMPLE:
SearchTreeInterface<Person> myTree = new BinarySearchTree<>();
Person whitney = new PersonWhitney, ;
Person returnValue = myTree.add(whitney);
Following the add operation, returnValue is null since whitney was not
already in the tree.
Person whitney = new PersonWhitney, ;
returnValue = myTree.add(whitney2);
Since the two Person objects have the same name, they are equal; therefore,
the add method will not add whitney2 to the tree. Instead, it replaces
whitney2 and returns whitney.
returnValue = myTree.getEntry(whitney);
Now, the above statement sets returnValue to whitney2 since it is in the tree
and matches whitney.
returnValue = myTree.remove(whitney);
Similarly, the above line of code returns and removes whitney2.
Duplicate Entries:
- The add method ensures that duplicate entries are NEVER added to the tree;
however, a small alteration can make a change to allow entries that are
equal according to compareTo.
• EXAMPLE
public class BinarySearchTree<T extends Comparable<? super T>> extends
BinaryTree<T> implements SearchTreeInterface<T>
{
public BinarySearchTree() {
super(); } // end default constructor
public BinarySearchTree(T rootEntry) {
super();
setRootNode(new BinaryNode<>(rootEntry));
The SearchTree<T extends Comparable<? super T>> Interface extends
TreeInterface<T>
+contains(T): boolean
+getEntry(T): T
+add(T): T
+remove(T): T
+getInorderIterator(): Iterator<T>
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Recall that a binary search tree is a binary tree whose nodes contain comparable objects and are organized as follows. For each node in the tree: the data in a node is greater than the data in the node"s left subtree, the data in a node is less than the data in the node"s right subtree. Also recall that a comparable object belongs to a class that implements the interface. The searchtree> interface extends. Null values are not allowed to be included in the search tree; however, the above methods can return null to indicate failure. Entries in a search tree must be distinct: example: Following the add operation, returnvalue is null since whitney was not already in the tree. Person whitney(cid:1006) = new person(cid:894)(cid:862)whitney(cid:863), (cid:862)(cid:1008)(cid:1008)(cid:1008)(cid:1009)(cid:1009)(cid:1010)(cid:1010)(cid:1010)(cid:1010)(cid:863)(cid:895); returnvalue = mytree. add(whitney2); Since the two person objects have the same name, they are equal; therefore, the add method will not add whitney2 to the tree.
.jpg)
