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

current.Height = -1;
7)
else
8)
current.Height = Max(Height(current.Left),Height(current.Right)) + 1
9)
end if
10)
if Height(current.Left) - Height(current.Right) > 1
11)
if Height(current.Left.Left) - Height(current.Left.Right) > 0
12)
RightRotation(current)
13)
else
14)
LeftAndRightRotation(current)
15)
end if
16)
else if Height(current.Left) - Height(current.Right) < −1
17)
if Height(current.Right.Left) - Height(current.Right.Right) < 0
18)
LeftRotation(current)
19)
else
20)
RightAndLeftRotation(current)
21)
end if
22)
end if
23) end CheckBalance
7.3
Insertion
AVL insertion operates first by inserting the given value the same way as BST
insertion and then by applying rebalancing techniques if necessary. The latter
is only performed if the AVL property no longer holds, that is the left and right
subtrees height differ by more than 1. Each time we insert a node into an AVL
tree:
1.
We go down the tree to find the correct point at which to insert the node,
in the same manner as for BST insertion; then
2.
we travel up the tree from the inserted node and check that the node
balancing property has not been violated; if the property hasn’t been
violated then we need not rebalance the tree, the opposite is true if the
balancing property has been violated.

---

CHAPTER 7. AVL TREE
59
1) algorithm Insert(value)
2)
Pre: value has passed custom type checks for type T
3)
Post: value has been placed in the correct location in the tree
4)
if root = ∅
5)
root ← node(value)
6)
else
7)
InsertNode(root, value)
8)
end if
9) end Insert
1) algorithm InsertNode(current, value)
2)
Pre: current is the node to start from
3)
Post: value has been placed in the correct location in the tree while
4)
preserving tree balance
5)
if value < current.Value
6)
if current.Left = ∅
7)
current.Left ← node(value)
8)
else
9)
InsertNode(current.Left, value)
10)
end if
11)
else
12)
if current.Right = ∅
13)
current.Right ← node(value)
14)
else
15)
InsertNode(current.Right, value)
16)
end if
17)
end if
18)
CheckBalance(current)
19) end InsertNode
7.4
Deletion
Our balancing algorithm is like the one presented for our BST (defined in §3.3).
The major difference is that we have to ensure that the tree still adheres to the
AVL balance property after the removal of the node. If the tree doesn’t need
to be rebalanced and the value we are removing is contained within the tree
then no further step are required. However, when the value is in the tree and
its removal upsets the AVL balance property then we must perform the correct
rotation(s).

---

CHAPTER 7. AVL TREE
60
1) algorithm Remove(value)
2)
Pre: value is the value of the node to remove, root is the root node
3)
of the Avl
4)
Post: node with value is removed and tree rebalanced if found in which
5)
case yields true, otherwise false
6)
nodeT oRemove ← root
7)
parent ← ∅
8)
Stackpath ← root
9)
while nodeT oRemove 6= ∅ and nodeT oRemove.V alue = V alue
10)
parent = nodeT oRemove
11)
if value < nodeT oRemove.Value
12)
nodeT oRemove ← nodeToRemove.Left
13)
else
14)
nodeT oRemove ← nodeToRemove.Right
15)
end if
16)
path.Push(nodeToRemove)
17)
end while
18)
if nodeT oRemove = ∅
19)
return false // value not in Avl
20)
end if
21)
parent ← FindParent(value)
22)
if count = 1 // count keeps track of the # of nodes in the Avl
23)
root ← ∅ // we are removing the only node in the Avl
24)
else if nodeT oRemove.Left = ∅ and nodeT oRemove.Right = null
25)
// case #1
26)
if nodeT oRemove.Value < parent.Value
27)
parent.Left ← ∅
28)
else
29)
parent.Right ← ∅
30)
end if
31)
else if nodeT oRemove.Left = ∅ and nodeT oRemove.Right 6= ∅
32)
// case # 2
33)
if nodeT oRemove.Value < parent.Value
34)
parent.Left ← nodeT oRemove.Right
35)
else
36)
parent.Right ← nodeT oRemove.Right
37)
end if
38)
else if nodeT oRemove.Left 6= ∅ and nodeT oRemove.Right = ∅
39)
// case #3
40)
if nodeT oRemove.Value < parent.Value
41)
parent.Left ← nodeT oRemove.Left
42)
else
43)
parent.Right ← nodeT oRemove.Left
44)
end if
45)
else
46)
// case #4
47)
largestV alue ← nodeT oRemove.Left
48)
while largestV alue.Right 6= ∅
49)
// find the largest value in the left subtree of nodeT oRemove
50)
largestV alue ← largestV alue.Right

---

CHAPTER 7. AVL TREE
61
51)
end while
52)
// set the parents’ Right pointer of largestV alue to ∅
53)
FindParent(largestV alue.Value).Right ← ∅
54)
nodeT oRemove.Value ← largestV alue.Value
55)
end if
56)
while path.Count > 0
57)
CheckBalance(path.Pop()) // we trackback to the root node check balance
58)
end while
59)
count ← count − 1
60)
return true
61) end Remove
7.5
Summary
The AVL tree is a sophisticated self balancing tree. It can be thought of as
the smarter, younger brother of the binary search tree. Unlike its older brother
the AVL tree avoids worst case linear complexity runtimes for its operations.
The AVL tree guarantees via the enforcement of balancing algorithms that the
left and right subtrees differ in height by at most 1 which yields at most a
logarithmic runtime complexity.

---

Part II
Algorithms
62

---

Chapter 8
Sorting
All the sorting algorithms in this chapter use data structures of a specific type
to demonstrate sorting, e.g. a 32 bit integer is often used as its associated
operations (e.g. <, >, etc) are clear in their behaviour.
The algorithms discussed can easily be translated into generic sorting algo-
rithms within your respective language of choice.
8.1
Bubble Sort
One of the most simple forms of sorting is that of comparing each item with
every other item in some list, however as the description may imply this form
of sorting is not particularly effecient O(n
2
). In it’s most simple form bubble
sort can be implemented as two loops.
1) algorithm BubbleSort(list)
2)
Pre: list 6= ∅
3)
Post: list has been sorted into values of ascending order
4)
for i ← 0 to list.Count − 1
5)
for j ← 0 to list.Count − 1
6)
if list[i] < list[j]
7)
Swap(list[i], list[j])
8)
end if
9)
end for
10)
end for
11)
return list
12) end BubbleSort
8.2
Merge Sort
Merge sort is an algorithm that has a fairly efficient space time complexity -
O(n log n) and is fairly trivial to implement. The algorithm is based on splitting
a list, into two similar sized lists (lef t, and right) and sorting each list and then
merging the sorted lists back together.
Note: the function MergeOrdered simply takes two ordered lists and makes
them one.
63

---

CHAPTER 8. SORTING
64
54
2
74
75
4
0
1
2
3
4
54
2
74
75
4
0
1
2
3
4
54
2
75
74
4
0
1
2
3
4
54
75
2
74
4
0
1
2
3
4
75
54
2
74
4
0
1
2
3
4
75
54
2
74
4
0
1
2
3
4
75
54
2
74
4
0
1
2
3
4
75
54
74
2
4
0
1
2
3
4
75
74
54
2
4
0
1
2
3
4
75
74
54
2
4
0
1
2
3
4
75
74
54
4
2
0
1
2
3
4
75
74
54
4
2
0
1
2
3
4
75
74
54
4
2
0
1
2
3
4
75
74
54
4
2
0
1
2
3
4
75
74
54
4
2
0
1
2
3
4
Figure 8.1: Bubble Sort Iterations
1) algorithm Mergesort(list)
2)
Pre: list 6= ∅
3)
Post: list has been sorted into values of ascending order
4)
if list.Count = 1 // already sorted
5)
return list
6)
end if
7)
m ← list.Count / 2
8)
lef t ← list(m)
9)
right ← list(list.Count − m)
10)
for i ← 0 to lef t.Count−1
11)
lef t[i] ← list[i]
12)
end for
13)
for i ← 0 to right.Count−1
14)
right[i] ← list[i]
15)
end for
16)
lef t ← Mergesort(lef t)
17)
right ← Mergesort(right)
18)
return MergeOrdered(lef t, right)
19) end Mergesort

---

CHAPTER 8. SORTING
65
54
2
74
75
4
75
4
54
2
74
4
75
74
54
2
2
5
4
Divide
54
2
75
4
74
54
2
75
74
54
4
2
Impera
(Merge)
Figure 8.2: Merge Sort Divide et Impera Approach
8.3
Quick Sort
Quick sort is one of the most popular sorting algorithms based on divide et
impera strategy, resulting in an O(n log n) complexity. The algorithm starts by
picking an item, called pivot, and moving all smaller items before it, while all
greater elements after it. This is the main quick sort operation, called partition,
recursively repeated on lesser and greater sub lists until their size is one or zero
- in which case the list is implicitly sorted.
Choosing an appropriate pivot, as for example the median element is funda-
mental for avoiding the drastically reduced performance of O(n
2
).

---

CHAPTER 8. SORTING
66
54
2
74
75
4
Pivot
54
2
74
75
4
Pivot
75
2
74
54
4
Pivot
75
54
74
2
4
Pivot
75
74
54
2
4
Pivot
2
4
Pivot
4
2
Pivot
75
74
Pivot
75
74
75
74
54
4
2
Pivot
Figure 8.3: Quick Sort Example (pivot median strategy)
1) algorithm QuickSort(list)
2)
Pre: list 6= ∅
3)
Post: list has been sorted into values of ascending order
4)
if list.Count = 1 // already sorted
5)
return list
6)
end if
7)
pivot ←MedianValue(list)
8)
for i ← 0 to list.Count−1
9)
if list[i] = pivot
10)
equal.Insert(list[i])
11)
end if
12)
if list[i] < pivot
13)
less.Insert(list[i])
14)
end if
15)
if list[i] > pivot
16)
greater.Insert(list[i])
17)
end if
18)
end for
19)
return Concatenate(QuickSort(less), equal, QuickSort(greater))
20) end Quicksort

---

CHAPTER 8. SORTING
67
8.4
Insertion Sort
Insertion sort is a somewhat interesting algorithm with an expensive runtime of
O(n
2
). It can be best thought of as a sorting scheme similar to that of sorting
a hand of playing cards, i.e. you take one card and then look at the rest with
the intent of building up an ordered set of cards in your hand.
54
2
74
75
4
54
2
74
75
4
54
2
74
75
4
74
54
2
75
74
4
2
75
54
75
74
4
2
54
75
74
54
4
2
4
Figure 8.4: Insertion Sort Iterations
1) algorithm Insertionsort(list)
2)
Pre: