On day 7, you learned how to create a binary tree and how to print its class members. Limitations exist in binary trees; you can use other structures to help solve some of these restrictions. Today you will learn:
On day 7, you learned two ways to print a tree. The first way was rather awkward. The second way treated printing as a special case of walking the tree, which can be done in any number of sequences. You can imagine walking the tree in key-sequence order-alphabetical, in most cases. You also can imagine depth-first (go down the tree before you go across any levels) or width-first (go across a level before you go down.)
Today you will see two printing methods in more detail. The first method uses a first-in-first-out (FIFO) queue, and the second method revisits day 7's approach.
A queue is a structure in which objects enter one side, and leave the same or the other side. A last-in-first-out (LIFO) queue works so that the last thing added to the queue is the first thing to come out. A stack is a LIFO queue.
A first-in-first-out (FIFO) queue is like a line at a theater, as in figure 8.1 (and the British, in fact, talk about queuing up at a theater). The first person on line should be the first person through the door.
The easiest way to implement a FIFO queue is with an unsorted linked list. Listing 8.1 illustrates the interface to a simple FIFO queue. Listing 8.2 shows the implementation of the queue's methods, and listing 8.3 shows a driver program for the queue.
Figure 8.1 A FIFO queue.
Listing 8.1 FIFO Queue Header
1: // **************************************************
2: // PROGRAM: FIFO queue header
3: // FILE: queue.hpp
4: // PURPOSE: provide first in first out queue
5: // NOTES:
6: // AUTHOR: Jesse Liberty (jl)
7: // REVISIONS: 10/24/94 1.0 jl initial release
8: // **************************************************
9:
10: template <class T>
11: class Node
12: {
13: public:
14: Node (T*);
15: ~Node();
16: void InsertAfter(Node *);
17: Node * GetNext() const { return itsNext; }
18: void SetNext(Node * next) { itsNext = next; }
19: T* GetObject() const { return itsObject; }
20:
21: private:
22: T * itsObject;
23: Node * itsNext;
24: };
25:
26: template <class T>
27: class Queue
28: {
29: public:
30: Queue();
31: ~Queue();
32: void Push(T &);
33: T* Pop();
34:
35: private:
36: Node<T> itsHead;
37: };
Listing 8.2 FIFOImplementation
1: // **************************************************
2: // PROGRAM: FIFO queue implementation
3: // FILE: queue.cpp
4: // PURPOSE: provide first in first out queue
5: // NOTES:
6: // AUTHOR: Jesse Liberty (jl)
7: // REVISIONS: 10/24/94 1.0 jl initial release
8: // **************************************************
9:
10: #include "queue.hpp"
11: template <class T>
12: Node<T>::Node(T * pObject):
13: itsObject(pObject),
14: itsNext(0)
15: {}
16:
17: template <class T>
18: Node<T>::~Node()
19: {
20: itsObject = 0;
21: itsNext = 0;
22: }
23:
24: template <class T>
25: void Node<T>::InsertAfter(Node* newNode)
26: {
27: newNode->SetNext(itsNext);
28: itsNext=newNode;
29: }
30:
31: template<class T>
32: Queue <T>::Queue():
33: itsHead(0) // initialize head node to have no Object
34: {}
35:
36: template<class T>
37: Queue <T>::~Queue()
38: {
39: }
40:
41: template<class T>
42: void Queue<T>::Push(T & Object)
43: {
44: Node<T> * NewNode = new Node<T>(&Object);
45:
46: for (Node<T> * pNode = &itsHead;;pNode = pNode->GetNext())
47: {
48: if (pNode->GetNext() == NULL)
49: {
50: pNode->InsertAfter(NewNode);
51: break;
52: }
53: }
54: }
55:
56: template<class T>
57: T* Queue<T>::Pop()
58: {
59: Node<T> * first = itsHead.GetNext();
60: Node<T> * second = first->GetNext();
61: if (first)
62: {
63: T* object = first->GetObject();
64: if (second)
65: itsHead.SetNext(second);
66: else
67: itsHead.SetNext(0);
68: delete first;
69: return object;
70: }
71: else
72: return 0;
73: }
Listing 8.3 Queue Driver Program
1: #include "word.hpp"
2: #include "queue.cpp"
3:
4: int main(int argc, char **argv)
5: {
6: Queue<rWord> myQueue;
7:
8: for (int i = 1; i< argc; i++)
9: {
10: rWord* word = new rWord(argv[i]);
11: myQueue.Push(*word);
12: }
13:
14: for (i = 1; i< argc; i++)
15: cout << myQueue.Pop()->GetText()<< "\n";
16:
17: return 0;
18: }
Output:
d:\>0803 eternal vigilance is the price of liberty
eternal
vigilance
is
the
price
of
liberty
Analysis:
Listing 8.1 provides a template-based FIFO queue. The Node class is very close to the Node class for the sorted linked list, and you could well make this new one a base class of that more complex node.
The Queue class itself is far simpler than the linked list: it offers Push(), which adds the entry to the end of the queue, and Pop(), which removes and returns the first item on the queue.
On day 7, you saw how to print the binary tree, using static members to keep track of indentation. The FIFO queue enables you to walk the tree horizontally. With this capability, you can print the tree, spacing out the words appropriately, or you can print it sideways by using gotoxy() to position each word in turn. Because the sideways approach provides space for a deeper tree, it is the one I'll use here. I'll leave as an exercise at the end of the chapter the job of printing this tree vertically, using the FIFO queue.
Listing 8.4 provides the interface to a Binary Tree class, where each node holds an rWord. A third class, BinaryNodeWrapper, also is provided, which will be the object placed into the FIFO queue. The BinaryNodeWrapper has a wordNode pointer, along with information about the indentation and level of the entry in the tree.
Listing 8.5 provides the implementation of these three classes, and listing 8.6 provides a driver program that walks the tree and prints the chart.
Listing 8.4 The Interfaces for a Binary Tree of Words
1: #include "word.hpp"
2: #include <conio.h>
3:
4: class WordNode; // forward declaration
5:
6: class BinaryTree
7: {
8: public:
9: BinaryTree():myHead(0),myCount(0){}
10: ~BinaryTree(){}
11: long GetCount() const { return myCount; }
12: void Insert (rWord &);
13: void Delete (rWord &);
14: void Iterate(void (rWord::*f)() const);
15: WordNode* FindObject( rWord& target);
16: void PrintTree();
17:
18: private:
19: WordNode* myHead;
20: long myCount;
21: };
22:
23: class WordNode
24: {
25: public:
26: WordNode(rWord* word);
27: WordNode(rWord& word);
28: WordNode( WordNode&);
29: ~WordNode() {}
30: rWord* GetWord() { return myWord; }
31: const rWord* const GetWord() const { return myWord; }
32: void SetWord(rWord* target) { myWord = target;}
33:
34: void InsertSmaller(WordNode* NewNode);
35: void InsertBigger(WordNode* NewNode);
36:
37: const WordNode* const GetSmaller() const { return mySmaller; }
38: const WordNode* const GetBigger() const { return myBigger; }
39: const WordNode* const GetParent() const { return myParent; }
40:
41: WordNode* GetSmaller() { return mySmaller; }
42: WordNode* GetBigger() { return myBigger; }
43: WordNode* GetParent() { return myParent; }
44:
45:
46: void SetSmaller(WordNode* target) {mySmaller = target; }
47: void SetBigger(WordNode* target) {myBigger = target; }
48: void SetParent(WordNode* target) {myParent = target; }
49:
50: int operator<(const WordNode &rhs) const
51: {return *myWord < *(rhs.GetWord());}
52: int operator>(const WordNode &rhs) const
53: {return *myWord > *(rhs.GetWord());}
54: BOOL operator==(const WordNode &rhs) const
55: { return *myWord ==*(rhs.GetWord());}
56: BOOL operator==(const rWord& target) const
57: {return *myWord == target.GetText();}
58:
59: private:
60:
61: WordNode * mySmaller;
62: WordNode * myBigger;
63: WordNode * myParent;
64: rWord * myWord;
65: };
66:
67: class WNWrapper
68: {
69: public:
70: WNWrapper(WordNode* wn):myWordNode(wn){}
71: ~WNWrapper(){}
72: // WordNode& GetMyWordNode() { return myWordNode; }
73: int GetLevel() { return myLevel; }
74: void SetLevel (int level) {myLevel = level; }
75: int GetIndent() { return myIndent; }
76: void SetIndent (int Indent) {myIndent = Indent; }
77: WordNode* GetSmaller() { return myWordNode->GetSmaller(); }
78: WordNode* GetBigger() { return myWordNode->GetBigger(); }
79: WordNode* GetWordNode() { return myWordNode; }
80:
81: private:
82: WordNode* myWordNode;
83: int myLevel;
84: int myIndent;
85: };
Listing 8.5 The Implementation of the Binary Tree of Words
1: #include "btree.hpp"
2: #include "queue.cpp"
3:
4:
5: WordNode::WordNode(rWord* word):
6: mySmaller(0),
7: myBigger(0),
8: myParent(0),
9: myWord(word)
10: { }
11:
12: WordNode::WordNode(rWord &word):
13: mySmaller(0),
14: myBigger(0),
15: myParent(0),
16: myWord(&word)
17: { }
18:
19: WordNode::WordNode( WordNode& rhs)
20: {
21: mySmaller=rhs.GetSmaller();
22: myBigger=rhs.GetBigger();
23: myParent=rhs.GetParent();
24: myWord = rhs.GetWord();
25: }
26:
27:
28: void WordNode::InsertSmaller(WordNode* newNode)
29: {
30: newNode->SetSmaller(mySmaller);
31: newNode->SetParent(this);
32: mySmaller=newNode;
33: }
34:
35:
36: void WordNode::InsertBigger(WordNode* newNode)
37: {
38: newNode->SetBigger(myBigger);
39: newNode->SetParent(this);
40: myBigger=newNode;
41: }
42:
43:
44: void BinaryTree::Insert(rWord& rhs)
45: {
46: WordNode* newNode = new WordNode(&rhs);
47:
48: if (myHead == 0)
49: {
50: myHead = newNode;
51: return;
52: }
53:
54: WordNode* node = myHead;
55: while (node)
56: {
57: // duplicate? replace
58: if (newNode == node)
59: {
60: newNode->SetSmaller(node->GetSmaller());
61: newNode->SetBigger(node->GetBigger());
62: newNode->SetParent(node->GetParent());
63: if (node == myHead)
64: myHead = newNode;
65: else
66: {
67: if ( node->GetParent()->GetSmaller() == node)
68: node->GetParent()->SetSmaller(newNode);
69: else
70: node->GetParent()->SetBigger(newNode);
71: }
72: delete node;
73: break;
74: }
75: if (*newNode < *node)
76: {
77: if (!node->GetSmaller())
78: {
79: node->SetSmaller(newNode);
80: newNode->SetParent(node);
81: break;
82: }
83: else
84: node = node->GetSmaller();
85: }
86: else
87: {
88: if (!node->GetBigger())
89: {
90: node->SetBigger(newNode);
91: newNode->SetParent(node);
92: break;
93: }
94: else
95: node = node->GetBigger();
96: }
97: } // end while
98: } // end function
99:
100:
101: WordNode* BinaryTree::FindObject(rWord& rhs)
102: {
103: WordNode* node = myHead;
104:
105:
106: while (node)
107: {
108: if (*node == rhs)
109: break;
110:
111: if (*node < rhs)
112: node = node->GetBigger();
113: else
114: node = node->GetSmaller();
115: }
116: return node;
117: }
118:
119: void BinaryTree::Delete (rWord & target)
120: {
121: WordNode* node = FindObject(target);
122:
123: if (node)
124: {
125: if (!node->GetBigger())
126: {
127: if (!node->GetSmaller())
128: {
129: if (node == myHead)
130: myHead = 0;
131: else
132: {
133: if (node->GetParent()->GetSmaller() == node)
134: node->GetParent()->SetSmaller(0);
135: else
136: node->GetParent()->SetBigger(0);
137: }
138: }
139: else // has a smaller
140: {
141: if (node == myHead)
142: myHead = node->GetSmaller();
143: else
144: {
145: if (node->GetParent()->GetSmaller() == node)
146: node->GetParent()->SetSmaller(node->GetSmaller());
147: else
148: node->GetParent()->SetBigger(node->GetSmaller());
149: }
150: }
151: }
152: else // node does have a bigger
153: {
154: if (!node->GetSmaller())
155: {
156: if (node == myHead)
157: myHead = node->GetBigger();
158: else
159: {
160: if (node->GetParent()->GetSmaller() == node)
161: node->GetParent()->SetSmaller(node->GetBigger());
162: else
163: node->GetParent()->SetBigger(node->GetBigger());
164: }
165: }
166: else // node has both!!
167: {
168: WordNode * next = node->GetBigger();
169:
170: while (next->GetSmaller())
171: next=next->GetSmaller();
172:
173: if (next->GetParent()->GetSmaller() == next)
174: next->GetParent()->SetSmaller(next->GetBigger());
175: else
176: next->GetParent()->SetBigger(next->GetBigger());
177:
178: node->SetWord(next->GetWord());
179:
180: if (next->GetBigger())
181: next->GetBigger()->SetParent(node);
182:
183: node = next;
184: }
185: } // end else does have bigger
186: } // end if node
187: delete node;
188: } // end function
189:
190: // walk the tree horizontally and create wrappers in FIFO
191: void BinaryTree::PrintTree()
192: {
193: Queue<WNWrapper> FIFO;
194: if (!myHead)
195: {
196: cout << "Nothing in tree.\n" << endl;
197: return;
198: }
199:
200: WNWrapper* theWrapper = new WNWrapper(myHead);
201: int level = 1;
202: theWrapper->SetLevel(level);
203: int indent = level;
204: theWrapper->SetIndent(indent);
205: FIFO.Push(*theWrapper);
206:
207: WNWrapper* wnr;
208:
209: // ignore warning here!
210: while (wnr = FIFO.Pop())
211: {
212: WordNode* pWN = wnr->GetSmaller();
213: level = wnr->GetLevel();
214: indent = wnr->GetIndent();
215: if (pWN)
216: {
217: theWrapper = new WNWrapper(pWN);
218: theWrapper->SetLevel(level+1);
219: theWrapper->SetIndent(indent+1);
220: FIFO.Push(*theWrapper);
221: }
222: pWN = wnr->GetBigger();
223: if (pWN)
224: {
225: theWrapper = new WNWrapper(pWN);
226: theWrapper->SetLevel(level+1);
227: theWrapper->SetIndent(indent-1);
228: FIFO.Push(*theWrapper);
229: }
230: int indent = wnr->GetIndent();
231: gotoxy(5*level,indent+10);
232: cout << wnr->GetWordNode()->GetWord()->GetText();
233: delete wnr;
234: }
235: gotoxy(1,24);
236: }
Listing 8.6 A Driver Program to Print a Binary Tree of Words
1: // A Driver Program to Print a Binary Tree of Words
2: int main(int argc, char **argv)
3: {
4: BinaryTree tree;
5: for (int i = 1; i< argc; i++)
6: {
7: rWord* word = new rWord(argv[i]);
8: tree.Insert(*word);
9: }
10:
11: tree.PrintTree();
12:
13: return 0;
14: }
Output:
d:\>0806 now is the time for all good men to
to
time
the
now men
is good
for
all
d:\>0806 now is the time for all good men to come to the aid of
to
to
time
the the
now ofn
is good
for come
all
aid
Analysis:
The first printout demonstrates the use of the program.
In line 5 of listing 8.6, each word of the command line is used to create an rWord pointer, which then is inserted into the tree. The Insert() method works as discussed on day 7, and the word is moved into the right position in the tree.
After all the words are in the tree, the function PrintTree() is called in line 11. The implementation of this method is in lines 191 through 236 of listing 8.5.
A FIFO queue is instantiated in line 193, and the tree is checked to see whether it has any members. If not, a message is printed and the program ends.
Assuming that there is a head of the tree, a WNWrapper pointer is created based on the head word node in the tree. A number of local counting variables are initialized, and the wrapper is set to level 1 and indentation 1. Finally, in line 205, the wrapper is put into the queue.
The first WNWrapper is popped out of the queue and is assigned to the pointer to wrapper. Note that this assignment generates a warning with many compilers. The compiler is concerned that you might have confused the assignment operator (=) with the equal operator (==), but in this case, you do want the assignment operator.
If there is a smaller member, a new wrapper is created and its level and indentation are set based on the current wrapper, and the new (child) wrapper is pushed into the FIFO list.
In line 222, the bigger child is extracted in the same way. Now that the children have been wrapped up and put in the queue, the current word can be printed.
If you wanted to avoid using gotoxy(), you would rewrite this to indent according to the indentation level, and use new lines when the level variable changes.
This program is somewhat complex. You may want to run it a few times and then study the output, trying to understand line by line how the items are put on and then taken off the tree, and how they are pushed into and popped off of the queue.
The second run of the program includes a larger set of text and reveals a bug in this approach. When the child of the is extracted (men), its level is 3 and its indentation is 0. This makes sense: the parent had a level of 2 and an indentation of 1as the left child 1 is reduced from the parent's indentation, it returns to 0.
When the bigger child of is (of) is extracted, it too has a level of 3 and an indentation of 0. Its parent had a level of 2 and an indentation of -1, so the bigger child adds 1 to the indentation. Unfortunately, this position level 3, indentation 0 already is taken, and the word of overwrites the first two letters of men.
Because symmetrical actions are taken on each level of the program, collisions are inevitable. It is possible to overcome this problem using complex algorithms, but the next set of programs uses a simpler solution.
Listing 8.7 provides a simple solution to printing the tree. The premise is to walk all the way down the left leg of the tree, print the last entry, then its parent, and then its sibling, working back up the tree.
Examine this tree from the previous listing:
d:\>0807 now is the time for all
all
for
is
now
the
time
One way to print this is to get to the top of the tree (now) and to pass it to the PrintNode() function. In PrintNode(), get the smaller child (is) and call PrintNode() on that; then call DoPrint() (which actually prints) and then call PrintNode() on the larger child.
When the first node, now, calls PrintNode() on the child, is, it in turn calls PrintNode() on its smaller child, for, which calls PrintNode() on its smaller child, all. Because all has no children, it prints itself, and then returns. The word for prints, has no larger child, and so returns, and so on up the recursion tree. Here's the listing. Note that only the declaration of the PrintTree and its implementation need to change.
Listing 8.7 Using Regression To Print the Tree
1: // Listing 8.7 - Using Regression To Print the Tree
2:
3: #include "word.hpp"
4: #include "queue.cpp"
5: #include <conio.h>
6:
7: class WordNode; // forward declaration
8:
9: class BinaryTree
10: {
11: public:
12: BinaryTree():myHead(0),myCount(0){}
13: ~BinaryTree(){}
14: long GetCount() const { return myCount; }
15: void Insert (rWord &);
16: void Delete (rWord &);
17: void Iterate(void (rWord::*f)() const);
18: WordNode* FindObject( rWord& target);
19:
20: // the changes are the next three!
21: void PrintTree();
22: static void PrintNode(WordNode* pNode, int indent);
23: static void DoPrint(WordNode* pNode, int indent);
24:
25: private:
26: WordNode* myHead;
27: long myCount;
28: };
29:
30: class WordNode
31: {
32: public:
33: WordNode(rWord* word);
34: WordNode(rWord& word);
35: WordNode( WordNode&);
36: ~WordNode() {}
37: rWord* GetWord() { return myWord; }
38: const rWord* const GetWord() const { return myWord; }
39:
40: void SetWord(rWord* target) { myWord = target;}
41:
42: void InsertSmaller(WordNode* NewNode);
43: void InsertBigger(WordNode* NewNode);
44:
45: WordNode* GetSmaller() const { return mySmaller; }
46: WordNode* GetBigger() const { return myBigger; }
47: WordNode* GetParent() const { return myParent; }
48:
49: void SetSmaller(WordNode* target) {mySmaller = target; }
50: void SetBigger(WordNode* target) {myBigger = target; }
51: void SetParent(WordNode* target) {myParent = target; }
52:
53: int operator<(const WordNode &rhs) const
54: {return *myWord < *(rhs.GetWord());}
55: int operator>(const WordNode &rhs) const
56: {return *myWord > *(rhs.GetWord());}
57: BOOL operator==(const WordNode &rhs) const
58: { return *myWord ==*(rhs.GetWord());}
59: BOOL operator==(const rWord& target) const
60: {return *myWord == target.GetText();}
61: private:
62: WordNode * mySmaller;
63: WordNode * myBigger;
64: WordNode * myParent;
65: rWord * myWord;
66: };
67:
68: WordNode::WordNode(rWord* word):
69: mySmaller(0),
70: myBigger(0),
71: myParent(0),
72: myWord(word)
73: { }
74:
75: WordNode::WordNode(rWord &word):
76: mySmaller(0),
77: myBigger(0),
78: myParent(0),
79: myWord(&word)
80: { }
81:
82: WordNode::WordNode( WordNode& rhs)
83: {
84: mySmaller=rhs.GetSmaller();
85: myBigger=rhs.GetBigger();
86: myParent=rhs.GetParent();
87: myWord = rhs.GetWord();
88: }
89:
90: void WordNode::InsertSmaller(WordNode* newNode)
91: {
92: newNode->SetSmaller(mySmaller);
93: newNode->SetParent(this);
94: mySmaller=newNode;
95: }
96:
97: void WordNode::InsertBigger(WordNode* newNode)
98: {
99: newNode->SetBigger(myBigger);
100: newNode->SetParent(this);
101: myBigger=newNode;
102: }
103:
104:
105: void BinaryTree::Insert(rWord& rhs)
106: {
107: WordNode* newNode = new WordNode(&rhs);
108:
109: if (myHead == 0)
110: {
111: myHead = newNode;
112: myHead->SetBigger(0);
113: myHead->SetSmaller(0);
114: return;
115: }
116:
117: WordNode* node = myHead;
118: while (node)
119: {
120: // duplicate? replace
121: if (newNode == node)
122: {
123: newNode->SetSmaller(node->GetSmaller());
124: newNode->SetBigger(node->GetBigger());
125: newNode->SetParent(node->GetParent());
126: if (node == myHead)
127: myHead = newNode;
128: else
129: {
130: if ( node->GetParent()->GetSmaller() == node)
131: node->GetParent()->SetSmaller(newNode);
132: else
133: node->GetParent()->SetBigger(newNode);
134: }
135: delete node;
136: break;
137: }
138: if (*newNode < *node)
139: {
140: if (!node->GetSmaller())
141: {
142: node->SetSmaller(newNode);
143: newNode->SetParent(node);
144: break;
145: }
146: else
147: node = node->GetSmaller();
148: }
149: else
150: {
151: if (!node->GetBigger())
152: {
153: node->SetBigger(newNode);
154: newNode->SetParent(node);
155: break;
156: }
157: else
158: node = node->GetBigger();
159: }
160: } // end while
161: } // end function
162:
163:
164: WordNode* BinaryTree::FindObject( rWord& rhs)
165: {
166: WordNode* node = myHead;
167:
168:
169: while (node)
170: {
171: if (*node == rhs)
172: break;
173:
174: if (*node < rhs)
175: node = node->GetBigger();
176: else
177: node = node->GetSmaller();
178: }
179: return node;
180: }
181:
182: void BinaryTree::Delete (rWord & target)
183: {
184: WordNode* node = FindObject(target);
185:
186: if (node)
187: {
188: if (!node->GetBigger())
189: {
190: if (!node->GetSmaller())
191: {
192: if (node == myHead)
193: myHead = 0;
194: else
195: {
196: if (node->GetParent()->GetSmaller() == node)
197: node->GetParent()->SetSmaller(0);
198: else
199: node->GetParent()->SetBigger(0);
200: }
201: }
202: else // has a smaller
203: {
204: if (node == myHead)
205: myHead = node->GetSmaller();
206: else
207: {
208: if (node->GetParent()->GetSmaller() == node)
209: node->GetParent()->SetSmaller(node->GetSmaller());
210: else
211: node->GetParent()->SetBigger(node->GetSmaller());
212: }
213: }
214: }
215: else // node does have a bigger
216: {
217: if (!node->GetSmaller())
218: {
219: if (node == myHead)
220: myHead = node->GetBigger();
221: else
222: {
223: if (node->GetParent()->GetSmaller() == node)
224: node->GetParent()->SetSmaller(node->GetBigger());
225: else
226: node->GetParent()->SetBigger(node->GetBigger());
227: }
228: }
229: else // node has both!!
230: {
231: WordNode * next = node->GetBigger();
232:
233: while (next->GetSmaller())
234: next=next->GetSmaller();
235:
236: if (next->GetParent()->GetSmaller() == next)
237: next->GetParent()->SetSmaller(next->GetBigger());
238: else
239: next->GetParent()->SetBigger(next->GetBigger());
240:
241: node->SetWord(next->GetWord());
242:
243: if (next->GetBigger())
244: next->GetBigger()->SetParent(node);
245:
246: node = next;
247: }
248: } // end else does have bigger
249: } // end if node
250: delete node;
251: } // end function
252:
253:
254: void BinaryTree::PrintTree()
255: {
256: PrintNode(myHead,1);
257: }
258: void BinaryTree::PrintNode(WordNode* pNode, int indent)
259: {
260: WordNode* pWN = pNode->GetSmaller();
261: if (pWN)
262: PrintNode(pWN, indent+1);
263: DoPrint(pNode, indent);
264: pWN = pNode->GetBigger();
265: if (pWN)
266: PrintNode(pWN, indent+1);
267:
268: }
269: void BinaryTree::DoPrint(WordNode* pNode, int indent)
270: {
271: for (int i = 0; i<2*indent; i++)
272: cout << " ";
273: cout << pNode->GetWord()->GetText() << "\n";
274: }
275:
276:
277: int main(int argc, char **argv)
278: {
279: BinaryTree tree;
280: for (int i = 1; i< argc; i++)
281: {
282: rWord* word = new rWord(argv[i]);
283: tree.Insert(*word);
284: tree.PrintTree();
285:
286: }
287: tree.PrintTree();
288: return 0;
289: }
290:
Output:
d:\>0807 now is the time for all good men to come to the aid of their party
aid
all
come
for
good
is
men
now
of
party
the
the
their
time
to
to
Analysis:
This listing is much like the previous, except that the WNwrapper class no longer is needed, and the print methods have changed.
In line 254, the single line of PrintTree() calls PrintNode(), with the pointer to the first node in the tree, and the indentation level of 1.
In line 258 of PrintNode(), the current node provides its smaller pointer, and PrintNode() is called recursively in line 260. DoPrint() is called right after the recursive call returns, and then the larger child is obtained and PrintNode() is again called, on the larger child.
The DoPrint() mechanism is simple: it counts off two spaces for each level of indentation and then prints the word.
The biggest single problem with binary trees is that they can become badly out of balance. Suppose that you need to add the words is hurry the how dog cat to a binary tree. The tree would look like this:
cat
dog
how
hurry
is
the
Finding the or hurry would be fairly quick, but finding cat would take many more searches than it should. It would be nice to be able to rebalance this tree so that there were fewer levels, like this:
cat
dog
how
hurry
is
the
This provides three levels overall, rather than five. With larger trees, of course, the results can be even more dramatic.
AVL trees promise that they will be no more than one level out of balance. That is, while the left node may have a child when the right does not, it will never be true, at any point in the tree, that one side has two levels of descendants when the other side has none.
The trick with writing the AVL tree is that after each insert and each deletion, the tree must be in balance, or must be rebalanced. Recursion makes this possible, although it is by no means easy.
In order to write the AVL tree, the Node class must be modified to account for the imbalance in the tree. Listing 8.8 includes the declarations for the new node and the AVL tree itself. Note that this first attempt has not yet been parameterized; again, it is easier to develop and debug a class like this using actual types, rather than templates. Later, when you are confident the class is working well, you always can parameterize it.
Listing 8.9 provides the implementation, and listing 8.10 shows a short driver program. The analysis following listing 8.10 explains how the AVL tree works.
Listing 8.8 Declaring the AVL Tree
1: // Listing 8.8 - Declaring the AVL Tree
2:
3: #include "word.hpp"
4: enum Tilt { tNone, tLeft, tRight};
5:
6: class WordNode; // forward declaration
7:
8: class AVLTree
9: {
10: public:
11: AVLTree():myHead(0),myCount(0),insertedOK(FALSE){}
12: ~AVLTree(){}
13:
14: long GetCount() const { return myCount; }
15: void Insert (rWord &);
16: void Delete (rWord &);
17: void PrintTree();
18:
19: protected:
20: void InsertNode(WordNode*, WordNode*&);
21: void DeleteBothChildren(WordNode*& target, WordNode* ptr, BOOL
&deleteok);
22: void RemoveNode(WordNode*& target, WordNode* doomed, BOOL &deleteok);
23:
24: void leftBalance(WordNode*& target, BOOL &deleteok);
25: void rightBalance(WordNode*& target,BOOL &deleteok);
26: void RightRotate(WordNode *&);
27: void LeftRotate(WordNode *&);
28:
29: void PrintNode(WordNode* pNode, int indent);
30: void DoPrint(WordNode* pNode, int indent);
31:
32: private:
33: WordNode* myHead;
34: long myCount;
35: BOOL insertedOK;
36: };
37:
38: class WordNode
39: {
40: public:
41: // Constructors
42: WordNode(rWord* word);
43: WordNode(rWord& word);
44: WordNode( WordNode&);
45: ~WordNode() {}
46:
47: // Accessors
48: rWord* GetWord() { return myWord; }
49: const rWord* const GetWord() const { return myWord; }
50: void SetWord(rWord* target) { myWord = target;}
51: WordNode*& GetSmaller() { return mySmaller; }
52: WordNode*& GetBigger() { return myBigger; }
53: WordNode* GetParent() const { return myParent; }
54:
55: void SetSmaller(WordNode* target) {mySmaller = target; }
56: void SetBigger(WordNode* target) {myBigger = target; }
57: void SetParent(WordNode* target) {myParent = target; }
58:
59: Tilt GetTilt() { return myTilt; }
60: void SetTilt (Tilt theTilt) { myTilt = theTilt; }
61:
62: // Insertion
63: void InsertSmaller(WordNode* NewNode);
64: void InsertBigger(WordNode* NewNode);
65:
66: // overloaded operators
67: int operator<(const WordNode &rhs) const
68: {return *myWord < *(rhs.GetWord());}
69: int operator<=(const WordNode &rhs) const
70: {return *myWord <= *(rhs.GetWord());}
71:
72:
73:
74: int operator>=(const WordNode &rhs) const
75: {return *myWord >= *(rhs.GetWord());}
76: int operator>(const WordNode &rhs) const
77: {return *myWord > *(rhs.GetWord());}
78: BOOL operator==(const WordNode &rhs) const
79: { return *myWord ==*(rhs.GetWord());}
80: BOOL operator==(const rWord& target) const
81: {return *myWord == target.GetText();}
82:
83: private:
84: WordNode * mySmaller;
85: WordNode * myBigger;
86: WordNode * myParent;
87: Tilt myTilt;
88: rWord * myWord;
89: };
90:
Listing 8.9 Implementing the AVL Tree
1: // Implementing the AVL tree
2: #include "avl.hpp"
3:
4: WordNode::WordNode(rWord* word):
5: mySmaller(0),
6: myBigger(0),
7: myParent(0),
8: myTilt(tNone),
9: myWord(word)
10: { }
11:
12: WordNode::WordNode(rWord &word):
13: mySmaller(0),
14: myBigger(0),
15: myParent(0),
16: myWord(&word)
17: { }
18:
19: WordNode::WordNode(WordNode& rhs)
20: {
21: mySmaller=rhs.GetSmaller();
22: myBigger=rhs.GetBigger();
23: myParent=rhs.GetParent();
24: myWord = rhs.GetWord();
25: }
26:
27: void WordNode::InsertSmaller(WordNode* newNode)
28: {
29: newNode->SetSmaller(mySmaller);
30: newNode->SetParent(this);
31: mySmaller=newNode;
32: }
33:
34: void WordNode::InsertBigger(WordNode* newNode)
35: {
36: newNode->SetBigger(myBigger);
37: newNode->SetParent(this);
38: myBigger=newNode;
39: }
40:
41:
42: void AVLTree::RightRotate(WordNode*& target)
43: {
44: WordNode *p2, *p3;
45: p2 = target->GetBigger();
46: if(p2->GetTilt()==tRight) // single rotation
47: {
48: target->SetBigger(p2->GetSmaller());
49: p2->SetSmaller(target);
50: target->SetTilt(tNone);
51: target = p2;
52: }
53: else // double rotation
54: {
55: p3 = p2->GetSmaller();
56: p2->SetSmaller(p3->GetBigger());
57: p3->SetBigger(p2);
58: target->SetBigger(p3->GetSmaller());
59: p3->SetSmaller(target);
60: p2->SetTilt(p3->GetTilt() == tLeft? tRight : tNone);
61: target->SetTilt(p3->GetTilt() == tRight? tLeft: tNone);
62: target = p3;
63: }
64: target->SetTilt(tNone);
65: }
66:
67: void AVLTree::LeftRotate(WordNode*& target)
68: {
69: WordNode *p2, *p3;
70: p2 = target->GetSmaller();
71: if(p2->GetTilt()==tLeft) // single rotation
72: {
73: target->SetSmaller(p2->GetBigger());
74: p2->SetBigger(target);
75: target->SetTilt(tNone);
76: target = p2;
77: }
78: else // double rotation
79: {
80: p3 = p2->GetBigger();
81: p2->SetBigger(p3->GetSmaller());
82: p3->SetSmaller(p2);
83: target->SetSmaller(p3->GetBigger());
84: p3->SetBigger(target);
85: p2->SetTilt(p3->GetTilt() == tRight? tLeft : tNone);
86: target->SetTilt(p3->GetTilt() == tLeft? tRight: tNone);
87: target = p3;
88: }
89: target->SetTilt(tNone);
90: }
91:
92: void AVLTree::Delete(rWord& rhs)
93: {
94: BOOL deleteok = FALSE;
95: WordNode* doomed = new WordNode(&rhs);
96: RemoveNode(myHead,doomed,deleteok);
97: }
98:
99: void AVLTree::RemoveNode(WordNode*& target, WordNode* doomed, BOOL
&deleteok)
100: {
101: WordNode* p;
102: if (!target)
103: deleteok = FALSE;
104: else
105: {
106: if (*target == *doomed)
107: {
108: p = target;
109: if (!target->GetBigger())
110: {
111: target = target->GetSmaller();
112: deleteok = TRUE;
113: delete p;
114: p = 0;
115: }
116: else if (!target->GetSmaller())
117: {
118: target = target->GetBigger();
119: deleteok = TRUE;
120: delete p;
121: p = 0;
122: }
123: else
124: {
125: DeleteBothChildren(target, target->GetSmaller(), deleteok);
126: if (deleteok)
127: rightBalance(target,deleteok);
128: }
129: }
130: else if (*doomed < *target)
131: {
132: RemoveNode(target->GetSmaller(), doomed, deleteok);
133: if (deleteok)
134: rightBalance(target,deleteok);
135: }
136: else if (*doomed > *target)
137: {
138: RemoveNode(target->GetBigger(),doomed, deleteok);
139: if (deleteok)
140: leftBalance(target,deleteok);
141: }
142: }
143: }
144:
145: void AVLTree::DeleteBothChildren(WordNode*& target, WordNode* ptr, BOOL
&deleteok)
146: {
147: if (!ptr->GetBigger())
148: {
149: target->SetWord(ptr->GetWord());
150: ptr=ptr->GetSmaller();
151: deleteok = TRUE;
152: }
153: else
154: {
155: DeleteBothChildren(target, ptr->GetBigger(),deleteok);
156: if (deleteok)
157: leftBalance(ptr,deleteok);
158: }
159: }
160:
161:
162: void AVLTree::leftBalance(WordNode*& target,BOOL &deleteok)
163: {
164: WordNode *p2, *p3;
165: Tilt tilt2, tilt3;
166:
167: switch (target->GetTilt())
168: {
169: case tRight:
170: target->SetTilt(tNone);
171: break;
172: case tNone:
173: target->SetTilt(tLeft);
174: deleteok = FALSE;
175: break;
176: case tLeft:
177: p2 = target->GetSmaller();
178: tilt2 = p2->GetTilt();
179: if (tilt2 != tRight)
180: {
181: target->SetSmaller(p2->GetBigger());
182: p2->SetBigger(target);
183: if (tilt2 == tNone)
184: {
185: target->SetTilt(tLeft);
186: p2->SetTilt(tRight);
187: deleteok = FALSE;
188: }
189: else
190: {
191: target->SetTilt(tNone);
192: p2->SetTilt(tNone);
193: }
194: target = p2;
195: }
196: else
197: {
198: p3=p2->GetBigger();
199: tilt3=p3->GetTilt();
200: p2->SetBigger(p3->GetSmaller());
201: p3->SetSmaller(p2);
202: target->SetSmaller(p3->GetBigger());
203: p3->SetBigger(target);
204: p2->SetTilt(tilt3 == tRight? tLeft : tNone);
205: target->SetTilt(tilt3 == tLeft?tRight:tNone);
206: target=p3;
207: p3->SetTilt(tNone);
208: }
209: break;
210: }
211: }
212:
213: void AVLTree::rightBalance(WordNode*& target,BOOL &deleteok)
214: {
215: WordNode *p2, *p3;
216: Tilt tilt2, tilt3;
217:
218: switch (target->GetTilt())
219: {
220: case tLeft:
221: target->SetTilt(tNone);
222: break;
223: case tNone:
224: target->SetTilt(tRight);
225: deleteok = FALSE;
226: break;
227: case tRight:
228: p2 = target->GetBigger();
229: tilt2 = p2->GetTilt();
230: if (tilt2 != tLeft)
231: {
232: target->SetBigger(p2->GetSmaller());
233: p2->SetSmaller(target);
234: if (tilt2 == tNone)
235: {
236: target->SetTilt(tRight);
237: p2->SetTilt(tLeft);
238: deleteok = FALSE;
239: }
240: else
241: {
242: target->SetTilt(tNone);
243: p2->SetTilt(tNone);
244: }
245: target = p2;
246: }
247: else
248: {
249: p3=p2->GetSmaller();
250: tilt3=p3->GetTilt();
251: p2->SetSmaller(p3->GetBigger());
252: p3->SetBigger(p2);
253: target->SetBigger(p3->GetSmaller());
254: p3->SetSmaller(target);
255: p2->SetTilt(tilt3 == tLeft?tRight:tNone);
256: target->SetTilt(tilt3 == tRight?tLeft:tNone);
257: target=p3;
258: p3->SetTilt(tNone);
259: }
260: break;
261: }
262: }
263:
264:
265: void AVLTree::Insert(rWord& rhs)
266: {
267: WordNode* newNode = new WordNode(&rhs);
268: InsertNode(newNode, myHead);
269: }
270:
271: void AVLTree::InsertNode(WordNode* newNode, WordNode*& target)
272: {
273: if (!target)
274: {
275: target = newNode;
276: target->SetSmaller(0);
277: target->SetBigger(0);
278: target->SetTilt(tNone);
279: insertedOK=TRUE;
280: myCount++;
281: }
282: else if ((*newNode) <= (*target))
283: {
284: InsertNode(newNode,target->GetSmaller());
285: switch(target->GetTilt())
286: {
287: case tLeft:
288: LeftRotate(target);
289: insertedOK=FALSE;
290: break;
291: case tRight:
292: target->SetTilt(tNone);
293: insertedOK=FALSE;
294: break;
295: case tNone:
296: target->SetTilt(tLeft);
297: }
298: }
299: else
300: {
301: InsertNode(newNode,target->GetBigger());
302: switch(target->GetTilt())
303: {
304: case tRight:
305: RightRotate(target);
306: insertedOK=FALSE;
307: break;
308: case tLeft:
309: target->SetTilt(tNone);
310: insertedOK=FALSE;
311: break;
312: case tNone:
313: target->SetTilt(tRight);
314: }
315: }
316: }
317:
318: void AVLTree::PrintTree()
319: {
320: PrintNode(myHead,1);
321: }
322: void AVLTree::PrintNode(WordNode* pNode, int indent)
323: {
324: WordNode* pWN = pNode->GetSmaller();
325: if (pWN)
326: PrintNode(pWN, indent+1);
327: DoPrint(pNode, indent);
328: pWN = pNode->GetBigger();
329: if (pWN)
330: PrintNode(pWN, indent+1);
331:
332: }
333:
334: void AVLTree::DoPrint(WordNode* pNode, int indent)
335: {
336: for (int i = 0; i<2*indent; i++)
337: cout << " ";
338: cout << pNode->GetWord()->GetText() << "\n";
339: }
340:
Listing 8.10 Driver Program for the AVL Tree
1: // Listing 8.10 - Driver Program for the AVL Tree
2:
3: int main(int argc, char **argv)
4: {
5: AVLTree tree;
6:
7: // populate the tree
8: for (int i = 1; i< argc; i++)
9: {
10: rWord* word = new rWord(argv[i]);
11: tree.Insert(*word);
12: }
13:
14: tree.PrintTree();
15:
16: // decimate the tree
17: for (i = argc-1; i>=1; i-=3)
18: {
19: cout << "!! deleting " << argv[i] << endl;
20: rWord *word = new rWord(argv[i]);
21: tree.Delete(*word);
22: }
23:
24: tree.PrintTree();
25: return 0;
26: }
Output:
d:\>0810 now is the time for all good men to
all
for
good
is
men
now
the
time
to
!! deleting to
!! deleting good
!! deleting for
!! deleting the
for
good
is
now
the
the
to
Analysis:
In line 4 of listing 8.8, an enumerated constant Tilt is created, with three potential values: tNone, tLeft, and tRight. Every node tilts to the left or to the right, or has no tilt. Tilting to the left means that the left node has one depth greater than the right node.
The WordNode is declared in lines 42 through 89. In line 87, a new data member, myTilt, is declared to hold the individual node's tilt. Two new comparison operators are added: greater-than-or-equals in lines 74 and 75, and less-than-or-equals in lines 69 and 71.
Accessors for the Tilt are provided in lines 62 and 63; and GetSmaller() and GetBigger(), in lines 51 and 52, are modified to return a reference to the WordNode pointers, thus allowing the pointer to be changed by the calling program.
The AVL tree itself is declared in lines 8 through 40. A local variable, insertedOK, is created to keep track of when the tree needs balancing.
There is a simple set of public accessors, such as Insert() and Delete(), that call a suite of protected implementation methods. leftRotate() and rightRotate() are used by the insertion methods, and leftBalance() and rightBalance() are used by the deletion methods.
Take careful note that the left... and right... methods are complementary mirror images of each other.
Examine the Insert() method in lines 264 through 268. The object, in this case an rWord, is passed in and a node is created. InsertNode() is called with the new node and the pointer to the head of the list.
InsertNode() repeatedly tries to find a place for the new object, recursing into itself each time it descends a level. When objects are added, the parent object has its tilt set appropriately, and when the tilt becomes too great, the node is rotated.
In line 287, for example, if the node already has a left tilt, and another node is added to the left, then LeftRotate() is called.
Examine LeftRotate() in lines 66 through 89. The node is passed in, and its left node is examined. If the left node also has a left tilt, a single rotation is performed; otherwise a double rotation is performed.
Tip: When examining AVL trees and related binary trees, it is best to write down the structure on paper and manually walk through how nodes will be added and deleted.
There are a host of other binary trees, but the truth is the only important remaining structure is the one you almost always will use when creating a program for storing items on disk: the B-tree. This structure is explained in detail on day 10 when Collection classes are covered.
Today you learned what a FIFO queue is and how to use it to print a binary tree. You also learned how to print a binary tree recursively, and what the primary limitations are in using binary trees. You learned what balanced trees are, and how to build one of the most powerful balanced trees: the AVL tree.
Q: Why is an unsorted linked list the easiest way to implement a FIFO queue?
A: The alternative is to use an array, either of the objects or of pointers. Either you have to shuffle the array forward for each element removed from the list (or for each one added to the list, depending on which side you considered to be the front), or you have to use two pointers that represent the front and back, and they rotate around the list as if it were circular. Neither of these methods is terribly hard to implement, but the first one is inefficient and they both have the problem of the list filling up. Using a linked list is efficient and it never is full, because you always can add another node.
Q: Is there any way to traverse a binary tree breadth-first without using a FIFO queue?
A: Well, anything is possible, but it is very hard. You end up doing partial depth-first traversals many times, always keeping track of what depth you are supposed to be "traversing" in a breadth-first manner.
Q: Why are there only three values in the enum Tilt, used in an AVL tree? Don't we need to know how much it tilts?
A: Because an AVL tree is going to be kept nearly balanced, no one node will ever be left tilting by more than one in either direction.
Q: How does the AVL tree perform in the case that is the nemesis of the regular binary treethat is, where the elements being inserted already are sorted (or reverse sorted)?
A: The AVL tree has no problem. Work it out (on paper, or using the program from the chapter) for inserting the letters A through O, in order. Although it does a fair bit of rebalancing, it ends up with a perfectly bushy tree.
Q: When would an AVL tree be a good choice?
A: An AVL tree is a great choice when the data structure is small enough to remain all in memory, but big enough and accessed commonly enough that performance is still an issue. If the data structure is too big for all of it to be in memory at once, then it is better to use a technique that is optimized for disk access (which you see on day 10). If the data structure will never get very big, or if it is not accessed frequently, then you shouldn't bother with the extra code and extra complication of a AVL tree over a binary tree.
The Workshop provides quiz questions to help you solidify your understanding of the material covered, and exercises to provide you with experience in using what you have learned. Try to answer the quiz and exercise questions before checking the answers in Appendix A, and make sure that you understand the answers before continuing to the next chapter.
Go to: Table of Contents | Next Page