Reading: Deitel & Deitel, 15.7
A tree is a set of one or more nodes such that
disjoint sets,
and each of these sets is a tree (also called a subtree).
Here are some other definitions:
Exercise 1: What is the depth and the degree of the following tree? What is the level of nodes A, D, F, and H? Circle all leaf nodes. The answers are at the end of the worksheet.
Binary Search Trees
A binary tree is a tree where each node has exactly two children (typically denoted left and right), and each child is either a binary tree or NULL. In other words it is a tree of degree 2. A binary tree is a mathematical structure. If we add some operations, we would have an Abstract Data Type. Note that its definition says nothing about its implementation.
A binary search tree is a binary tree with the following characteristics.
Each node has a key of type T (the node can have other data as well),
and an order relation is defined on these keys; i.e., they can be compared
using the operations <, >, and ==.
All nodes in the left subtree of a particular node have key values
less than the key value at that node, and all nodes in right subtree
of a node have key values greater than the key of that node. (Assume that
duplicate keys are not permitted.)
Here is a binary search tree of integers:
New nodes are inserted into a binary search tree as a leaf node with both children NULL. To find where the new node belongs, start at the root. If the key value of the item to be inserted is less than the key value of the root, if the left child of the root is NULL, then insert the new node as the left child, otherwise recursively insert into the left subtree. If the item to be inserted is greater than the key value of the root, if the right child is NULL, insert the new node as the right child of the root, otherwise recursively insert into the right subtree.
Thus, if a new node with the value 32 were to be inserted into the above tree, it would be inserted as the right child of node 26.
Using this algorithm, the first node to be inserted is made the root node and will always be the root node. Once a node has been inserted, it will never be moved; i.e., it will always have the same parent. There are other designs for trees where this is not the case.
Exercise 2: Draw the tree which would result by inserting the following elements into an initially empty tree in the order shown.
23, 12, 31, 42, 72, 38, 78, 47, 81, 50
Now draw the tree which would result if the same numbers were inserted in the order shown below. Note that the structure of the tree differs depending on the order in which elements are inserted.
72, 50, 23, 38, 42, 12, 81, 78, 47, 31
Here is code which creates a class BinTreeClass and
defines an InsertItem member function. As with linked lists, we
define a separate class (or struct) for the node, called a TreeNode, which contains the data and pointers to the two children.
This code is in
/dept/cs/cs2/wksht18/tree.cpp
#include <iostream>
using namespace std;
template <class T>
class TreeNode {
public:
T data;
TreeNode<T> *leftptr;
TreeNode<T> *rightptr;
TreeNode(const T &item) { // constructor
data=item;
leftptr=rightptr=NULL;
}
};
template <class T>
class BinTreeClass {
private:
TreeNode<T> *root;
void InsertItemHelper(TreeNode<T> *CurrNode, TreeNode<T> *ToBeInserted) {
if (CurrNode->data > ToBeInserted->data) {
if (CurrNode->leftptr == NULL) {
CurrNode->leftptr = ToBeInserted;
return;
}
else InsertItemHelper(CurrNode->leftptr,ToBeInserted);
}
else {
if (CurrNode->rightptr == NULL) {
CurrNode->rightptr = ToBeInserted;
return;
}
else InsertItemHelper(CurrNode->rightptr,ToBeInserted);
}
}
public:
BinTreeClass() { root=NULL;}
BinTreeClass(T item) {
root = new TreeNode<T>(item);
}
void InsertItem(T item) {
TreeNode<T> *temp = new TreeNode<T>(item);
if (root == NULL) {
root = temp;
return;
}
else InsertItemHelper(root,temp);
}
};
int main()
{
BinTreeClass<int> TreeOfInt;
int numbers[] = {47, 23, 31, 72, 38, 78, 81, 50, 42, 12};
for (int i=0;i<10;i++)
TreeOfInt.InsertItem(numbers[i]);
TreeOfInt.Inorder();
return 0;
}
Pay particular attention to the use of the recursive helper function. This is a private member function which calls itself recursively to find the correct location to insert the new node.
Exercise 3: Notice
that there is a call to a member function Inorder in main.
This function performs what is called an inorder traversal of the
the tree.
An traversal of a tree is a sequence of visits to
each node of the tree performing some operation on the node such as printing its
data. In an inorder traversal, all nodes in the left subtree are visited
using an inorder traversal, then the node itself, then all nodes in the
right subtree are visited using an inorder traversal. Specifically,
when the operation is printing, the inorder traversal is as follows.
If the left child is not NULL, all values in the left child should be
printed inorder before printing the value of a particular node, then the value
of the node is printed, then all values of the right subchild should
be printed inorder. Since we have a binary search tree,
this method will print out all of the keys sorted in
ascending order. A call to the Inorder function on the tree diagrammed
on page 2 would have the following output:
19 21 26 35 46 48 50 85
Write this function.
Hint: Create a function InorderHelper(TreeNode<T> *curr) which
does three things: it first prints out all of the values of the left
subchild of curr inorder; it then displays the value of curr;
and then displays all of the values of the right subtree of curr
inorder.
Exercise 4: In addition to inorder traversal, there are a number of other ways to traverse a tree. In preorder traversal to print the nodes, as a node is visited, its value is printed out immediately, then its left subchild is traversed in preorder, then its right subchild is traversed in preorder. The output of preorder traversal of the tree which is diagrammed on page 2 is
35 21 19 26 46 85 50 48
Write such a function and test it by adding a line of code to main.
The third type of traversal is postorder. In postorder traversal to print the nodes, first the left subtree of a node is traversed in postorder, then the right subtree is traversed in postorder, and finally the value is printed out. Here is the output of postorder traversal of the tree which is diagrammed on page 2.
19 26 21 48 50 85 46 35
Note that in postorder traversal, the root node is always printed last. Describe how you might modify your inorder traversal function to traverse a tree in postorder.
Exercise 5: Write a function TreeNode<T>* find(T item) which returns a pointer to the node with the value of item if there is such a node in the tree, and NULL if there is no such item in the tree. Test your function by adding lines in main() to find an item in the tree and an item which is not in the tree.
As before, to do this, you will need a findhelper function which takes one more argument than the find function. Its second argument should be a node.
Performance of the find function
The advantage of storing items in a binary search tree is that under many circumstances, it is possible to find a particular item quickly, far more quickly than in a linked list for example. The performance of the find function depends on the extent to which the tree is balanced. A tree is balanced if the difference between the level of the leaf node with the lowest level and the level of the leaf node with the highest level is one or less. If a tree has 31 nodes and is completely balanced, how many levels will it have? How many nodes will be at each level? What will be the maximum number of comparisons required to locate a node in the tree?
Answers: The tree will have 5 levels. The first level will have 1 node, the second level will have 2 nodes, the third will have 4 nodes, the fourth level will have 8 nodes, and the fifth level will have 16 nodes. The maximum number of comparisons required will be 5.
The extent to which a tree is balanced depends on the order in which the nodes are inserted into the tree. If the nodes are inserted in sorted order, either ascending or descending, the tree will be completely unbalanced. A tree with 31 nodes inserted in ascending order would have 31 levels, and all nodes, including the root), would have at least one null child. Try drawing the tree which would result if the following nodes were inserted into an initially empty tree in this order!
92 87 82 71 65 64 50 42
Very Important: If a tree is balanced, what is the order of the find function, where n is the number of nodes in the tree?
A binary search tree as an implementation of the ADT set
Recall that an Abstract Data Type (ADT) is a set of operations on some data, but it does not say anything about its implementation. In previous worksheets we have seen an implementation of the ADT Set where the data were stored in an array. You could also implement a Set in which the data were stored in a binary search tree. That is, it would have the same member functions as the Set ADT that we discussed before (int Size(), void AddItem(T item), void PrintItems(), bool DeleteItem(T item), bool IsMember(T item)), but the items in the set would be stored in a binary search tree rather than in an array. (We have not discussed deleting nodes from a tree yet, so that member function would be difficult to implement).
Exercise 5 There is a major advantage to implementing a set as a binary search tree rather than as an array, particularly if the set is large. What is it?
Solution to Exercise 1:
The depth is 3. The degree is 3. The level of node A is 0, the level of node D is 1, the level of node F is 2, and the level of node H is 3. Nodes C, E, G and H are leaf nodes.