D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

O(1), additionally enqueuing an item to the front of the queue is also an O(1)
operation.
A deque is a wrapper data structure that uses either an array, or a doubly
linked list. Using an array as the backing data structure would require the pro-
grammer to be explicit about the size of the array up front, this would provide
an obvious advantage if the programmer could deterministically state the maxi-
mum number of items the deque would contain at any one time. Unfortunately
in most cases this doesn’t hold, as a result the backing array will inherently
incur the expense of invoking a resizing algorithm which would most likely be
an O(n) operation. Such an approach would also leave the library developer

---

CHAPTER 6. QUEUES
52
Figure 6.2: Deque data structure after several mutations

---

CHAPTER 6. QUEUES
53
to look at array minimization techniques as well, it could be that after several
invocations of the resizing algorithm and various mutations on the deque later
that we have an array taking up a considerable amount of memory yet we are
only using a few small percentage of that memory. An algorithm described
would also be O(n) yet its invocation would be harder to gauge strategically.
To bypass all the aforementioned issues a deque typically uses a doubly
linked list as its baking data structure. While a node that has two pointers
consumes more memory than its array item counterpart it makes redundant the
need for expensive resizing algorithms as the data structure increases in size
dynamically. With a language that targets a garbage collected virtual machine
memory reclamation is an opaque process as the nodes that are no longer ref-
erenced become unreachable and are thus marked for collection upon the next
invocation of the garbage collection algorithm. With C++ or any other lan-
guage that uses explicit memory allocation and deallocation it will be up to the
programmer to decide when the memory that stores the object can be freed.
6.4
Summary
With normal queues we have seen that those who arrive first are dealt with first;
that is they are dealt with in a first-in-first-out (FIFO) order. Queues can be
ever so useful; for example the Windows CPU scheduler uses a different queue
for each priority of process to determine which should be the next process to
utilise the CPU for a specified time quantum. Normal queues have constant
insertion and deletion run times. Searching a queue is fairly unusual—typically
you are only interested in the item at the front of the queue. Despite that,
searching is usually exposed on queues and typically the run time is linear.
In this chapter we have also seen priority queues where those at the front
of the queue have the highest priority and those near the back have the lowest.
One implementation of a priority queue is to use a heap data structure as its
backing store, so the run times for insertion, deletion, and searching are the
same as those for a heap (defined in §4).
Queues are a very natural data structure, and while they are fairly primitive
they can make many problems a lot simpler. For example the breadth first
search defined in §3.7.4 makes extensive use of queues.

---

Chapter 7
AVL Tree
In the early 60’s G.M. Adelson-Velsky and E.M. Landis invented the first self-
balancing binary search tree data structure, calling it AVL Tree.
An AVL tree is a binary search tree (BST, defined in §3) with a self-balancing
condition stating that the difference between the height of the left and right
subtrees cannot be no more than one, see Figure 7.1. This condition, restored
after each tree modification, forces the general shape of an AVL tree. Before
continuing, let us focus on why balance is so important. Consider a binary
search tree obtained by starting with an empty tree and inserting some values
in the following order 1,2,3,4,5.
The BST in Figure 7.2 represents the worst case scenario in which the run-
ning time of all common operations such as search, insertion and deletion are