Computer Science II Lab 6
Better Living through Better Trees
Introduction
============
Trees are wonderful. Trees are the best thing ever! Trees provide
us with oxygen, paper, fruit, nuts, and they help us find websites
with pictures of cats and/or people who are wrong and must be argued
with (even though you don't know them and will never meet them in
real life). Ok, so there are at least two kinds of trees. We will
be working on creating the second one, the data structure which bears
a resemblance to the biological one. (If you want to make a
biological tree, all you need is an acorn and time!)
As we have discussed in lecture, trees are one of the most
incredibly useful things in computer science. Trees are what make
it possible to cope with massive data sets and narrow them down
quickly. Binary trees, for example, can literally split the search
space in half if they are organized correctly. That is what this
lab is about, implementing binary search trees so that we can
achieve logarithmic run times when searching for data.
In the lab that follows this one, we will use that tree to build an
expression parser. The lab which follows that one will further
build on the concept by creating a small compiler/code generator
stack!
The key to these final 3 labs will be to take it nice and easy.
There will be a lot of pointers flying all over the place, and there
will be lots of complexity. That's ok though. We are building
shapes in memory to manage that complexity. So long as you follow
the patterns, you won't get lost. So take a deep breath and let's
dive in!
The Naive Binary Search Tree (Guided)
=====================================
Ok, so let's start off with a simple binary search tree. Here, we
are going to build a class which can contain a simple binary tree,
and then we will write a bstTree insert function to go with it.
Before I show you the tree template, I want to mention a few things
about this tree. The first is that it is fully linked, so each node
connects to its parent. The second is that it is not strictly in
line with OOP goals. The reason is that it passes pointers to
subtrees back out to the user. This is done largely because it
makes the tree more flexible than it would be if we tried to use it
with tree iterators. We will be coding tree iterators later on, and
will use this class as a building block for a more robust
containers. For now, know that we are trading OOP integrity for
simplicity, but given that this is really about exploring
algorithms, this should be ok.
So without further ado, here is the binary search tree. Your first
task is, of course, to type out btree.h:
--begin btree.h--
1 /*
2 * File: btree.h
3 * Purpose: A nice little binary tree template.
4 */
5 #ifndef BTREE_H
6 #define BTREE_H
7 #include <iostream>
8
9 template<typename T>
10 class BinaryTree {
11 public:
12 //we always create tree nodes with data
13 BinaryTree(T data) {
14 left = right = parent;
15 this->data = data;
16 }
17
18 //destructor
19 ~BinaryTree() {
20 delete left;
21 delete right;
22 }
23
24 //link a left tree
25 void linkLeft(BinaryTree<T> *node) {
26 left = node;
27 node->parent = this;
28 }
29
30 //link a right tree
31 void linkRight(BinaryTree<T> *node) {
32 right = node;
33 node->parent = this;
34 }
35
36
37 //get the left tree
38 BinaryTree<T> *getLeft() {
39 return left;
40 }
41
42
43 //get the right tree
44 BinaryTree<T> *getRight() {
45 return right;
46 }
47
48
49 //get the parent tree
50 BinaryTree<T> *getParent() {
51 return parent;
52 }
53
54 //get the uncle
55 BinaryTree<T> *getUncle() {
56 BinaryTree<T> *gp;
57
58 //root nodes and non-grandchildren have no uncles
59 if(!parent || !parent->parent)
60 return NULL;
61
62 //get the grand parent
63 gp = parent->parent;
64
65 //return the uncle
66 if(parent == gp->left)
67 return gp->right;
68 else
69 return gp->left;
70 }
71
72
73 //return the data itemm
74 T getData() {
75 return data;
76 }
77
78
79 //return the height of the tree
80 int getHeight() {
81 int lh=0, rh=0;
82
83 //get the heights of the left and the right
84 if(left)
85 lh = left->getHeight();
86 if(right)
87 rh = right->getHeight();
88
89 //1 + max of left and right height
90 return 1 + (lh > rh ? lh : rh);
91 }
92
93
94 //print the tree
95 void printTree() {
96 int h = getHeight();
97
98 //print each level
99 for(int i=1; i<=h; i++) {
100 printLevel(i);
101
102 std::cout << std::endl;
103 }
104 }
105
106 private:
107
108 //print a level of the tree
109 void printLevel(int h) {
110 if(h == 1) {
111 std::cout << data << " ";
112 } else {
113 //either print what's on the left, or print a #
114 if(left)
115 left->printLevel(h-1);
116 else
117 std::cout << "# ";
118
119 //either print what's on the right or print a #
120 if(right)
121 right->printLevel(h-1);
122 else
123 std::cout << "# ";
124 }
125 }
126
127 T data; //The data element
128 BinaryTree<T> *left; //left child
129 BinaryTree<T> *right; //right child
130 BinaryTree<T> *parent; //parent
131 };
132
133 #endif
--end btree.h--
Take a moment to study this design. Notice how I still keep the
three node pointers as private members. This is so we can be
assured that the parenting of the tree will be handled properly.
You must use the get and the link methods to build the tree.
Notice that I did not write traversals. We'll be adding traversal
iterators in the next lab. I did, however, add a recursive print
method. When you run it, it will print the tree. If a level of the
tree has holes in it, it prints "#". This function isn't the
prettiest way to display the tree, but it should be easy enough to
follow for debugging purposes. If you want to modify the print
functions so that it prints something more tree like, go for it. In
fact, I'll give you some extra credit points if you do!
Also of note is the presence of the "getUncle" in addition to
"getRight", "getLeft", and "getParent". This returns a node's
uncle, if it has one. This won't be used in any of the labs in this
class, but I have included it here so you can use this btree as a
starting point for exploring other trees. For instance, suppose you
wanted to try your hand at creating a red-black tree. If you do,
you'll need to get the uncles.
Ok, so now we have that little template, now we need to use it.
Here is my test file, which contains the bstInsert function that
works with this tree.
--begin btreeTest.cpp--
1 /*
2 * This is a small test driver for our btree. It builds a naive
3 * BST. Behold the glories of degenerative cases!
4 */
5
6 #include <iostream>
7 #include "btree.h"
8
9 using namespace std;
10
11 //an implementation of the bstInsert algorithm
12 void bstInsert(BinaryTree<int> *t, int data) {
13 if(data <= t->getData()) {
14 //insert left
15 if(!t->getLeft())
16 t->linkLeft(new BinaryTree<int>(data));
17 else
18 bstInsert(t->getLeft(), data);
19 } else {
20 //insert right
21 if(!t->getRight())
22 t->linkRight(new BinaryTree<int>(data));
23 else
24 bstInsert(t->getRight(), data);
25 }
26 }
27
28
29 int main(void) {
30 BinaryTree<int> *t=NULL;
31 int data;
32
33 do {
34 //prompt the user
35 cout << "Enter Number (-1 to exit): ";
36
37 //get the data
38 cin >> data;
39
40 if(data == -1)
41 continue;
42
43 if(!t)
44 t=new BinaryTree<int>(data);
45 else
46 bstInsert(t, data);
47 } while(data != -1);
48
49 //print the tree
50 t->printTree();
51
52 return 0;
53 }
--end btreeTest.cpp--
Enter this program and study it. Make sure you can reconcile my
implementation of bstInsert to the pseudocode you have in your
notes.
Now try the program out. Here's a sample run through:
Enter Number (-1 to exit): 10
Enter Number (-1 to exit): 9
Enter Number (-1 to exit): 7
Enter Number (-1 to exit): 8
Enter Number (-1 to exit): 13
Enter Number (-1 to exit): 11
Enter Number (-1 to exit): 14
Enter Number (-1 to exit): -1
10
9 13
7 # 11 14
# 8 # # # # #
So then, how do we read that tree output? Well, the answer is that
it is printing the tree in row order with a couple of spaces between
the nodes. So if you look at that, here's what you get if we adjust
it so it is more tree like:
10
9 13
7 11 14
8
If you squint at my function's output just right, you can see the
tree. If you adjust your program so that you print something more
like the second example, I will give you some points.
So now, we have this awesome little binary search tree, right?
Wrong! Consider this case:
Enter Number (-1 to exit): 1
Enter Number (-1 to exit): 2
Enter Number (-1 to exit): 3
Enter Number (-1 to exit): 4
Enter Number (-1 to exit): -1
1
# 2
# # 3
# # # 4
As you can see, it rapidly degenerates into a linked list, so a
search would just be an undesirable O(n) search, and not a super
sweet O(lg n) search.
So that's the best we can do without some kind of a balancing
strategy, and that is where the guided portion leaves off.
The AVL Tree (Challenge Lab)
============================
As we discussed in class, the AVL tree is an auto-balancing binary
search tree. Your mission, should you choose to get a high grade,
is to implement this soviet jewel. How you may ask? Well, I have
given you tons of pseudocode in class, now is your chance to put it
to good use. To get you started, I have taken the liberty of
designing a derived template based on the btree. Here is the
skeleton of that design. I went ahead and filled in all the boring
stuff (like comparison operators and all the stuff needed to make
C++ happy about the inheritance structure), but I left all the juicy
details to you. I think the layout of my functions will give you a
strong hint at what you need to do. In fact if you look for the:
/* to be done by intrepid students */
comments, you will see what you need to fill in. Note that I added
2 new private members "rh" and "lh" which measure the height on each
side. You should maintain these as counters during the insertion
process. You should have some pseudocode from class to help with
this. So here is my skeleton code:
--begin avltree.h--
1 /*
2 * An implementation of the AVL tree.
3 */
4
5 #include "btree.h"
6
7 template<typename T>
8 class AVLTree : public BinaryTree<T> {
9 public:
10 ///////////////////////////////////////
11 // constructor
12 ///////////////////////////////////////
13 AVLTree(T data) : BinaryTree<T>(data) { lh = rh = 0; }
14
15
16 ///////////////////////////////////////
17 //operators
18 ///////////////////////////////////////
19 bool operator<(AVLTree<T> &rhs) {
20 return this->getData() < rhs.getData();
21 }
22
23 bool operator>(AVLTree<T> &rhs) {
24 return this->getData() > rhs.getData();
25 }
26
27 bool operator<=(AVLTree<T> &rhs) {
28 return this->getData() <= rhs.getData();
29 }
30
31 bool operator>=(AVLTree<T> &rhs) {
32 return this->getData() >= rhs.getData();
33 }
34
35 bool operator==(AVLTree<T> &rhs) {
36 return this->getData() == rhs.getData();
37 }
38
39
40 ///////////////////////////////////////
41 // wrappers (to avoid typecasts)
42 ///////////////////////////////////////
43 AVLTree<T> *getLeft() {
44 return (AVLTree<T> *) BinaryTree<T>::getLeft();
45 }
46
47 AVLTree<T> *getRight() {
48 return (AVLTree<T> *) BinaryTree<T>::getRight();
49 }
50
51 AVLTree<T> *getParent() {
52 return (AVLTree<T> *) BinaryTree<T>::getParent();
53 }
54
55 AVLTree<T> *getUncle() {
56 return (AVLTree<T> *) BinaryTree<T>::getUncle();
57 }
58
59 ///////////////////////////////////////
60 //methods
61 ///////////////////////////////////////
62
63 //inserts a new subtree, and returns the new avl root
64 AVLTree<T> *insert(T data) {
65 /* to be done by intrepid students */
66 }
67
68
69 //searchs for an item in an avl tree. Returns the node pointer on
70 //success, returns NULL if the item is not in the tree
71 AVLTree<T> *search(T item) {
72 /* to be done by intrepid students */
73 }
74
75
76 private:
77 ///////////////////////////////////////
78 //private methods
79 ///////////////////////////////////////
80
81 //do the standard bst insert using a node
82 void bstInsert(AVLTree<T> *node) {
83 /* to be done by intrepid students */
84 }
85
86 //rebalance the tree with root node
87 void rebalance(AVLTree<T> *node) {
88 /* to be done by intrepid students */
89 }
90
91 //rotate the tree to the left
92 void rotateLeft(AVLTree<T> *node) {
93 /* to be done by intrepid students */
94 }
95
96 //rotate the tree to the right
97 void rotateRight(AVLTree<T> *node) {
98 /* to be done by intrepid students */
99 }
100
101 ///////////////////////////////////////
102 //private data members
103 ///////////////////////////////////////
104 int lh; //left tree height
105 int rh; //right tree height
106 };
--end avltree.h--
To test your avl tree, rewrite the btreeTest.cpp file so that
it uses your insert. Also, add code to test the search function.
So I should be able to build a tree, and then search for items. If
the item is not in the tree, it should tell me so.
So in the end, you'll need to submit the following:
- btree.h
- avltree.h
- btreeTest.cpp
- avltreeTest.cpp
HINTS:
- Devise some way to test your tree rotations. Get the rotations
working before trying anything else.
- You will establish links using the linkLeft and linkRight
methods. This will help ensure that you don't lose your parent
links.
- Review your pseudocode! I've told you how to do most, if not
all, of this stuff!
Extra Credit
------------
Notice anything missing? That's right, there is no delete
function. Add it, and you'll get 10 points additional credit on the
challenge portion of the lab! My function signature for this is:
