CHAPTER 4
Trees
4.2 For node B:
(a) A.
4.5 Proof is by induction. The theorem is trivially true for h = 0. Assume true for h = 1,2, . . . ,k. A tree of height
4.6 This can be shown by induction. Alternatively, let N = number of nodes, F = number of full nodes,
4.7 This can be shown by induction. In a tree with no nodes, the sum is zero, and in a one-node tree, the root is a
4.8 (a) – * * a b + c d e.
4.9
4.11 The Set class is the BinarySearchTree class with the two classes const_iterator and iterator imbedded
into it as well as a new data member (int Size; ). In the first two code examples are classes for both
iterators with ++ implemented. The third code example shows the new insert and begin member
functions, while the fourth example shows the modified BinaryNode struct. For a fully operational
Set, −− would be implemented along with the functions contains and erase.
(a)
class const_iterator
{
}
else
{
const_iterator operator++ ( int )
{
const_iterator old = *this;
++( *this );
return old;
}
(b)
class iterator : public const_iterator
{
public:
iterator( ) { }
}
else
{
t = current->parent;
cout<<“first parent is ” <<t->element<<endl;
while (t && t-> element < current-> element)
(c)
//This is the public insert
iterator insert( const Comparable & x)
{ Size++; return insert (x, root, root);}
}
else if( x < t–>element )
return (insert( x, t–>left, t ));
else if( t–>element < x )
return(insert( x, t->right, t ));
return iterator (t) ;
(d)
template<typename Comparable>
struct BinaryNode
{
4.12
template <typename KeyType, typename ValueType >
class Map
{
{
for (iterator itr = map.begin(); itr != map.end(); itr++)
if (itr->first == key)
return itr;
return map.end();
}
ValueType & operator[](const KeyType &key)
{
iterator itr = map.find(key);
if(itr != map.end())
4.13
#include <iostream>
using namespace std;
template<typename Comparable>
class Set
{
public:
class const_iterator
{
}
const_iterator & operator— ( )
{
current = current->prev;
return *this;
protected:
BinaryNode<Comparable> *current;
Comparable & retrieve( ) const
{ return current->element; }
friend class Set;
};
}
iterator insert(const Comparable & x)
{
Size++;
return insert(x,root,smallest,largest);
}
iterator begin()
{return iterator(smallest->next);}
iterator end()
{return iterator(largest);}
4.14 (a) Keep a bit array B. If i is in the tree, then B[i] is true; otherwise, it is false. Repeatedly generate random
4.15 Below is code for both b and c (b is commented out) as well as a function to compute the
balance sum of the balance of all the nodes.
BinaryNode<Comparable> * findMax(BinaryNode<Comparable> * t)
}
void remove( const Comparable & x, BinaryNode * & t )
{
// static int counter = 0; // used to alternate removal methods
if( t == nullptr )
return; // Item not found; do nothing
}
//counter %=2;
}
else
{
BinaryNode *oldNode = t;
t = ( t->left != nullptr ) ? t->left : t->right;
delete oldNode;
}
}
};
4.16 The binary node will be contain a field bool deleted, (initially set to false). When the ++
and – must be changed to bypass any node whose deleted is true. The insert must also be
modified to skip any deleted nodes on insert and should allow reinsertion by just flipping
the deleted bit. For delete, the node is found, and then its deleted bit is set to true.
BinaryNode<Comparable> * findMax(BinaryNode<Comparable> * t)
{
if (t == nullptr) return nullptr;
}
4.17 Let the internal path length of a tree with n nodes, be the sum of all the depths of all the
nodes in the tree and denoted Cn . Then the average depth would be Cn/ N. Consider a
binary search tree with keys {1, 2, … n}. If the tree is rooted at node i, then there are i –1
nodes left of the root and n – i nodes to the right of the root. Hence to compute the average
over all possible roots we have
Cn = n – 1 + [(C0 + Cn–1) + (C1 + Cn-2) + (C2 + Cn-3) + … + (Cn-1 + C0)]/n.
Subtraction reveals that nCn – (n–1)Cn-1 = 2(n – 1) + 2Cn–1, or
4.19
4.20 It is easy to verify by hand that the claim is true for 1 k 3. Suppose it is true for k = 1, 2, 3, . . . h. Then
after the first 2h−1 insertions, 2h−1 is at the root, and the right subtree is a balanced tree containing 2h−1 + 1
through 2h−1. Each of the next 2h−1 insertions, namely, 2h through 2h + 2h−1−1, insert a new maximum and get
4.22 We will perform post order traversal and compute the height or each subtree as we go. Since the post order
traversal runs in linear time, this algorithm runs in linear time.
// Fair refers to heights are correct
bool isFairAndBalanced(BinaryNode<Comparable> *p)
}
4.23 One way to do this is keep a stack of pointers to the nodes visited along the insertion path. using a stack.
the pointers can be popped off in reverse order and tested for balance.
template<typename Comparable>
void insert( const Comparable & x, AvlNode * & t )
{
path.push(p);
if (x < p->element )
{p = p->left; lastDir = ‘l’;}
}
4.24 The code in Figure 4.44 implements the AVL deletion algorithm. x is the value to remove, and t is the
(sub)tree in question. We recursively traverse down the tree until t matches x, which means we found the
appropriate node to delete. The actual deletion occurs in the last two else clauses. There are several cases to
consider here. The first case is where t has two children. In this case, as in a binary search tree, we move t’s