C++ Week 11

Dynamic Data Structures III

A Deque class

A deque (double-ended queue) is a linear list where we can add items and remove them at both ends. We already have definitions of functions to add-at-the-rear and remove-from-the-front (see last week's definition of the Queue class). It remains to add-at-the-front and remove-from-the-rear. The first of these is fairly straightforward:

void Deque::add_at_front(int x)
{	Node*	p = new Node;
	p->n = x;
	p->link = front;
	if (front == NULL)
		rear = p;
	front = p;
}

The second is more tricky:

int Deque::remove_from_rear()
{	if (front == NULL)
		deal_with_underflow();
	else
	{	int	return_value;
		if (front == rear)	// only one node in the queue	
		{	front = NULL;
			return_value = rear->n;
			delete rear;
		}
		else
		{	Node*	p = front;
			while(p->link != rear)	// find the next-to-the-last node
				p = p->link;
			p->link = NULL;		// and detach the rear node
			return_value = rear->n;
			delete rear;
			rear = p;
		}
		return return_value;
	}
}

Remove-from-the-rear is not only complicated; it is also inefficient. Every time it is called, it has to traverse the full length of the list looking for the next-to-the-last node. This is because of the one-way nature of the singly-linked list.

Doubly-linked lists

An alternative implementation, which removes this particular inefficiency, is to use nodes that have two pointers rather than one, so as to produce a doubly-linked list:

class Binode
{  public:
	int	n;
	Binode*	l, *r;	// "l" and "r" for "left" and "right"
};

And, rather than go through the process of initializing a new Binode explicitly every time we create one, let's have a constructor in the class:

class Binode
{  public:
	Binode(int x) { n = x; l = r = NULL; }
	int	n;
	Binode*	l, *r;
};

Now, to create a new Binode we do something like this:

Binode*  p = new Binode(5);	// creates a new Binode and calls the constructor to initialize it

and we get:

A doubly-linked list looks like this:

Adding or removing nodes is going to be equally easy at either end of the list.

class Deque
{ public:
	Deque() { left = right = NULL; }
	void add_left(int x);
	void add_right(int x);
	int remove_left();
	int remove_right();
  private:
	Binode*	left, *right;	// assuming the above definition of Binode
};

void Deque::add_left(int x)
{	Binode*	p = new Binode(x);
	p->r = left;
	if (left == NULL)	// putting first binode into empty deque
		right = p;
	else	left->l = p;
	left = p;
}

int Deque::remove_left()
{	if (left == NULL)
		deal_with_underflow();
	else
	{	Binode* p = left;
		left = p->r;
		if (left == NULL)	// removing the last binode from the deque
			right = NULL;
		else	left->l = NULL;
		int return_value = p->n;
		delete p;
		return return_value;
	}
}

For the operations at the other end, just switch left and right, and l and r.

public or private data?

A possibly unsatisfactory feature of our Binode class (like our Node class) is that all of its data fields are public. At first sight this seems a bit fishy, as you don't want anything messing with the contents of your deque. As it happens, because the only way to get at the Binode list is through left or right, and since these are private, the data is effectively encapsulated.

If we wanted to make quite certain that nothing except a Deque object could make any use of a Binode, we could make the Binode class private to the Deque class by adding the following code to the declaration of Deque:

private:
   class Binode;

and modifying the declaration of Binode:

class Deque::Binode
{...
};

It would also now be necessary to define the Deque class before the Deque::Binode class.

Now, other parts of the program could define their own Binode classes, but this particular Binode class would be private to the Deque class.

If we were really determined not to have public data in our Binode class – some people would never have public data, as a matter of principle – we could declare the data members as private, but then we would have to arrange for Deque objects to be able to access them. We could do this, obviously, by providing accessor and mutator functions or we could fix it at a stroke by making the Deque class a friend of the Binode class, by modifying the definition of Binode:

class Binode
{  public:
	Binode(int x) { n = x; l = r = NULL; }
   private:
	int	n;
	Binode*	l, *r;
   friend class Deque;
};

This friend line does not define a member of the Binode class, so it is neither public nor private. It declares that the Deque class has special privileges with respect to the members of the Binode class: the member functions of the Deque class can access the private members of a Binode.

Some programmers do not approve of the friend feature of C++. The idea behind object-oriented programming, they would say, is that we can see, from inspecting the interface in a class definition, how the private data members of an object can be altered; we do not need to fear that data will be changed in a way that is not obvious from the class definition. Yet this friend feature, they point out, provides a back-door route into an object; private data can be changed in a way that is not at all obvious from the object's own interface but is only to be found in the function definitions of a different class. On the other hand, it provides a convenient way of permitting close collaboration between objects of two intimately related classes.

Binary trees

Another structure that we can create with Binodes is a binary tree. In the context of binary trees, a Binode* may be:

NULL, in which case it represents an empty binary tree, or
pointing to a Binode, which is the root of a binary (sub)tree

Pointers from one Binode down to Binodes at the next level are called branches. Binodes that don't have any branches are known as leaf nodes. We can also define a binary tree recursively by saying that a binary tree is either empty or consists of a Binode with a binary tree on each side. The nodes are all related to one another as parents, children and siblings (brothers and sisters).

Let's look at how to build a binary tree. We always begin with a NULL pointer and add Binodes:

Binode* root = new Binode;
root->l = root->r = NULL;  // initialise the member pointers to NULL
root->n = 5;

Or we could use the Binode constructor as follows:

Binode*  root = new Binode(5);

We can now start populating the tree:

root->l = new Binode(6);
root->r = new Binode(7);
Binode* p = root->l;
p->l = new Binode(8);
p->r = new Binode(9);

This creates the following structure in memory:

Binary search trees

The nodes in the above tree are in no particular order. However, if we arrange the values so that the values in all the nodes in the subtree to the left of the parent are less than the parent's value (note: all the values in the whole subtree, not just the values in the child nodes) and all the values in the subtree to the right of the parent are greater than the parent's value, it becomes very easy to decide whether a particular value is in the tree. If we rearrange our tree as follows, we turn it into a binary search tree:

Note that, in order for this to be a binary search tree, it is not sufficient merely that the left child of the root has a lower value (6) than the root node (8) but that all of the left child's children (5 and 7) also have values less than the root.

Building a binary search tree

Suppose you have a series of numbers and you want to put them into a binary search tree. You take the first number, whatever it may be, and make it the root node of the tree. Then you take the second number. If it's less than the root number, you hang it on the left of the root; if not, you hang it on the right. With each subsequent number, you start by comparing it with the root number. If it's less, you follow the left pointer; if not, the right. And you repeat this all the way down the tree until you find a NULL pointer. This is where the new number belongs in the tree.

Binode* root = NULL;		// tree initially empty
int x;
while (cin >> x)			// take next value of x from somewhere
	addnode(root, x);		// put it in its right place in the tree

And this is one possible way of writing the addnode procedure:

void addnode(Binode*& t, int x)
{	Binode*	newnode = new Binode(x);
	if (t == NULL)
	{	t = newnode;	// first number becomes the root value
		return;
	}
	Binode* a = t, *b;
	while (a != NULL)
	{	b = a;
		if (x < a->n)
			a = a->l;
		else	a = a->r;
	}
	// We've found where it goes; b points at its parent
	if (x < b->n)
		b->l = newnode;
	else	b->r = newnode;
}

We'll see a neater way of writing the addnode procedure when we've done recursion.

Notes on R. Mitton's lectures by S.P. Connolly, edited by R. Mitton, 2000-8