was observed in the example in the text after inserting 1–8 in order followed by 16, 15, and 14. The
insertions of 15 and 14 cause imbalances necessitating a double rotation.
4.26 AvlNode doubleRotateWithLeft( AvlNode *k3 )
{
AvlNode *k1, *k2;
4.27 After accessing 3,
After accessing 1,
After accessing 5,
4.28
4.31 (a-c) All of these routines take linear time.
int countNodes( Node * t )
{
if (t == nullptr)
return 0;
return 1 + countNodes(t->left) + countNodes(t->right);
}
4.33 Node removeLeaves( Node * t )
4.34 We assume the existence of a method randInt (lower, upper) that generates a uniform random integer
in the appropriate closed interval.
Node * makeRandomTree( int lower, int upper )
}
4.35 // LastNode contains last value that was assigned to a node.
Node * genTree( int height, int & lastNode )
{
Node * t = nullptr;
4.36 There are two obvious ways of solving this problem. One way mimics Exercise 4.34 by replacing
4.37 This is known as one-dimensional range searching. The time is O(K) to perform the inorder traversal, if a
significant number of nodes are found, and also proportional to the depth of the tree, if we get to some leaves
(for instance, if no nodes are found). Since the average depth is O(log N), this gives an O(K + log N) average
bound.
void printRange(Comparable & lower, Comparable & upper, BinaryNode *t)
4.38 This exercise is a likely programming assignments, so we do not provide code here.
4.39 The program below will output the commands Circle(X,Y) and DrawLine(i,j).
const int MAXY= 500;
Comparable element;
Node<Comparable> *right;
Node<Comparable> *left;
};
}
4.40 Put the root on an empty queue. Then repeatedly dequeue a node and enqueue its left and right
4.41 The BPlusNode has a parent pointer which makes promoting keys easier. A print function is included for
debugging.
#include<iostream>
#include<vector>
template <typename Comparable>
struct BPlusNode
{
template <typename Comparable>
class BPlusTree
{
private:
BPlusNode<Comparable> * root;
int maxIn;
int maxEx;
BPlusNode<Comparable> * find(Comparable key, BPlusNode<Comparable> * t)
}
void print(BPlusNode<Comparable> * t)
{
if (t != nullptr)
{
for (int i = 0; i< t->keys.size(); i++)
cout<<t->keys[i]<<” “;
cout<<endl;
{
rt->keys.push_back(tempKeys[i]);
rt->pointers.push_back(tempPtrs[i+1]);
}
rt->keys.push_back(key);
rt->pointers.push_back(n);
for (; i <tempKeys.size(); i++)
BPlusNode<Comparable> * newPtr;
newPtr = new BPlusNode<Comparable>(rt->parent);
tempKeys = rt->keys;
tempPtrs = rt->pointers;
rt->keys.clear();
}
newPtr->pointers.push_back(tempPtrs[tempKeys.size()]);
promote(tempKeys[tempKeys.size()/2], rt–>parent, rt, newPtr);
}// end if to split
}//end else
}// end
{
// split the node
newPtr = new BPlusNode<Comparable>(ptr->parent);
}
public:
4.43
4.44
template<typename Comparable>
struct ChildSibNode
};
template<typename Comparable>
void depth1st(ChildSibNode<Comparable> * t)
4.45 The function shown here is clearly a linear time routine because in the worst case it does a traversal
on both t1 and t 2.
bool similar( Node *t1, Node *t2 )
{
4.46 One can check if two trees are isomorphic by doing a post-order traversal of both trees, and labeling each
node with an integer during the traversal.
The algorithm will use a two dimensional array L[i,j], initially with no values assigned; and an integer k,
initially set 1.
4.47 The easiest solution is to compute, in linear time, the inorder numbers of the nodes in both trees. If
right
subtrees). If dN is the depth of x, then the running time satisfies T (N) = T (i) + T (N − i − 1) + dN,
where i is the size of the left subtree. In the worst case, dN is always O(N), and i is always 0, so the
4.49 (a) You need an extra bit for each thread.
4.50 The code below ignores sidebar comments but not /* */ comments. The list of reserved words can be
changed according to the interpretation of the problem.
#include <fstream>
#include <cctype>
ifstream in;
set<string> idents;
set<string> reserved;
{
pos=line.find(“//”);
if ( pos < line.size()) // there is a sidebar comment
line = line.substr(0,pos);
for (int i = 0; i < line.size(); i++)
}
if (!((toupper(line[i])>=‘A’&& toupper(line[i])<=‘Z’) || line[i] ==‘_’ ||
(i>0 && toupper(line[i-1])>=‘A’ && toupper(line[i-1]) <=‘Z’
&& line[i] >=‘0’ && line[i]<=‘9’)))
line[i] = ‘ ‘;
}
word = “”;
for (int i = 0; i < line.size(); i++)