# 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;
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->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.

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; }
int remove_left();
int remove_right();
private:
Binode*	left, *right;	// assuming the above definition of Binode
};

{	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 `Binode`s:

```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