Unit 9 — Data Structures

Lesson 1 — Stacks and queues

Division: Junior and above.

Two ways to keep a pile

A stack works like the returns cart: the last item put on is the first one taken off. This is called LIFO, "last in, first out".

A queue works like the line at the help desk: the first item put in is the first one taken out. This is called FIFO, "first in, first out".

ACSL uses the same two commands for both:

If the stack or queue is empty, POP() has nothing to take, and the value it gives is NIL. POP() on its own line, with no X =, still takes the item off: the value is just not kept.

Names in a script. A one-letter name that was given a value by = POP() (such as X) stands for that value. Any other letter or word inside PUSH( ) is pushed as itself. ACSL's own page writes pushed letters in quotes, PUSH("A"); this book leaves the quotes off, so PUSH(A) pushes the letter A.

Tracing a stack

Write the stack bottom to top, left to right, after every command. Here is the returns cart from the problem:

The third book shelved is A.

Tracing a queue

Write the queue front to back, left to right. New items join on the right, and POP() takes from the left. Here is the help-desk line:

The third student helped is P. The same commands gave a different answer, because only the rule for POP changed.

Watch out: one more POP() on either structure would empty it, and a POP() after that gives NIL.

Arithmetic on popped values

Division: Intermediate and above.

Intermediate and Senior questions do sums with the popped values and push the results back. This is the sample from ACSL's own page:

So Z = −2. Work out the sum when it is pushed, using the values the names have at that moment, and push only the answer.

A stack in Python

Unit 4 kept a stack as a Python list stack together with a count top, and never shrank the list:

• push: if top equals len(stack), append; otherwise write over stack[top]. Then add 1 to top.
• pop: if top is 0 the stack is empty (NIL); otherwise take 1 from top, and the value is stack[top].

This program runs a script of commands, each one either "PUSH x" or "POP", and prints every popped value.

script = ["PUSH 2", "PUSH 9", "PUSH 5", "POP", "PUSH 3", "POP", "POP", "POP", "POP"]

stack = []
top = 0
for command in script:
    parts = command.split()
    if parts[0] == "PUSH":
        if top == len(stack):
            stack.append(parts[1])
        else:
            stack[top] = parts[1]
        top = top + 1
    elif top == 0:
        print("NIL")
    else:
        top = top - 1
        print(stack[top])

5
3
9
2
NIL

A queue in Python

A queue is a list plus a head index: the position of the item at the front.

• push: append the value to the end of the list.
• pop: if head equals len(queue), the queue is empty (NIL); otherwise the value is queue[head], and head goes up by 1.

The items before head have already left the line; the program just never looks at them again.

script = ["PUSH R", "PUSH U", "PUSH N", "POP", "PUSH S", "POP", "POP", "POP", "POP"]

queue = []
head = 0
for command in script:
    parts = command.split()
    if parts[0] == "PUSH":
        queue.append(parts[1])
    elif head == len(queue):
        print("NIL")
    else:
        print(queue[head])
        head = head + 1

R
U
N
S
NIL

kind = input()
tokens = input().split()

items = []
top = 0
head = 0
i = 0
while i < len(tokens):
    if tokens[i] == "PUSH":
        value = tokens[i + 1]
        if kind == "STACK":
            if top == len(items):
                items.append(value)
            else:
                items[top] = value
            top = top + 1
        else:
            items.append(value)
        line = "PUSH " + value + " :"
        i = i + 2
    else:
        if kind == "STACK":
            if top == 0:
                popped = "NIL"
            else:
                top = top - 1
                popped = items[top]
        else:
            if head == len(items):
                popped = "NIL"
            else:
                popped = items[head]
                head = head + 1
        line = "POP -> " + popped + " :"
        i = i + 1
    if kind == "STACK":
        for k in range(top):
            line = line + " " + items[k]
    else:
        for k in range(head, len(items)):
            line = line + " " + items[k]
    print(line)

Run it from this unit's folder:

python assets/l1.py < assets/l1/1.in

The input is a stack script whose last line is POP -> NIL :, a pop from an empty stack. assets/l1/2.in runs a queue, and assets/l1/3.in starts with a POP on an empty stack. Trace each one by hand first, then use the program to check your tables.

Lesson 2 — Binary search trees

Division: Junior and above.

Building the tree

A binary search tree (BST) stores keys (letters or numbers) in nodes. Each node has at most two children: a left child and a right child. The top node is the root.

To build a BST, insert the keys one at a time, in the order given:

1. The first key becomes the root.
2. Each later key starts at the root. If it is less than or equal to the key there, go left; if it is greater, go right.
3. Keep going down until the place you want is empty, and put the key there.

The "or equal" is ACSL's rule for duplicates: a key equal to one already in the tree goes to the left, as if it were smaller. Letters compare in alphabetical order, so A is less than B.

Example 1. The puzzle's word, SHELF.

• S is the root.
• H comes before S: left of S.
• E: before S, go left; before H, go left. It goes left of H.
• L: before S, go left; after H, go right. It goes right of H.
• F: left at S, left at H, right at E. It goes right of E.

        S
       /
      H
     / \
    E   L
     \
      F

Example 2. ACSL's sample word, PROGRAM. The second R meets the first R, is equal, and goes to its left.

          P
        /   \
       O     R
      /     /
     G     R
    / \
   A   M

Depth, height, leaves and internal path length

• The depth of a node is the number of steps down from the root. The root has depth 0.
• The height of the tree is the greatest depth of any node.
• A leaf is a node with no children.
• The internal path length is the sum of the depths of all the nodes.

Example 3. In SHELF: S has depth 0, H depth 1, E and L depth 2, and F depth 3. The internal path length is 0 + 1 + 2 + 2 + 3 = 8, which answers the second puzzle. The height is 3, and the leaves are F and L.

Example 4. In PROGRAM (ACSL's sample): P is at depth 0; O and R at depth 1; G and the second R at depth 2; A and M at depth 3. The internal path length is 0 + 2 × 1 + 2 × 2 + 2 × 3 = 12. The leaves are A, M and the second R.

Watch out: a duplicate is a separate node with its own depth. PROGRAM has seven letters, so its tree has seven nodes.

A BST in Python

This book keeps a BST in three parallel lists: key[i] is the key of node i, and left[i] and right[i] are the numbers of its children, with -1 for "no child". Nodes are numbered in the order they are inserted, so node 0 is the root.

insert adds one key and walks down from the root with a while loop, exactly as in the rules above. It returns the depth where the key landed.

def insert(key, left, right, letter):
    key.append(letter)
    left.append(-1)
    right.append(-1)
    new = len(key) - 1
    depth = 0
    node = 0
    placed = new == 0
    while not placed:
        depth = depth + 1
        if letter <= key[node]:
            if left[node] == -1:
                left[node] = new
                placed = True
            else:
                node = left[node]
        else:
            if right[node] == -1:
                right[node] = new
                placed = True
            else:
                node = right[node]
    return depth


key = []
left = []
right = []
total = 0
for letter in "PROGRAM":
    depth = insert(key, left, right, letter)
    print(letter, depth)
    total = total + depth
print("internal path length:", total)
print("key:  ", key)
print("left: ", left)
print("right:", right)

P 0
R 1
O 1
G 2
R 2
A 3
M 3
internal path length: 12
key:   ['P', 'R', 'O', 'G', 'R', 'A', 'M']
left:  [2, 4, 3, 5, -1, -1, -1]
right: [1, -1, -1, 6, -1, -1, -1]

External nodes and external path length

Division: Intermediate and above.

Every empty place where a new node could be attached is an external node. A leaf has two of them, and a node with one child has one. The depth of an external node is one more than the depth of the node it hangs from. The external path length is the sum of the depths of all the external nodes.

Example 5. In SHELF, the external nodes hang from:

There are 6 external nodes, and the external path length is 1 + 3 + 3 + 3 + 4 + 4 = 18.

Two facts make a good check:

• a tree with n nodes always has n + 1 external nodes;
• the external path length is always the internal path length plus 2n. For SHELF, 8 + 2 × 5 = 18.

Traversals

A traversal visits every node once. Each of the three orders is a rule applied at every node, starting from the root:

Example 6. ACSL's word AMERICAN. The second A equals the root and goes left.

        A
       / \
      A   M
         / \
        E   R
       / \  /
      C  I N

• inorder: AACEIMNR
• preorder: AAMECIRN
• postorder: ACIENRMA

The inorder traversal of a BST always lists the keys in sorted order, which is a quick check on your tree. For preorder, a good habit is to write the root first and then finish the whole left side before you touch the right.

Traversals in Python

Each traversal is a recursive function (Unit 2): the traversal of a tree is built from the traversals of its two subtrees. An empty subtree (-1) gives the empty string.

def inorder(node, key, left, right):
    if node == -1:
        return ""
    return inorder(left[node], key, left, right) + key[node] + inorder(right[node], key, left, right)


def preorder(node, key, left, right):
    if node == -1:
        return ""
    return key[node] + preorder(left[node], key, left, right) + preorder(right[node], key, left, right)


key = []
left = []
right = []
for letter in "AMERICAN":
    insert(key, left, right, letter)
print(inorder(0, key, left, right))
print(preorder(0, key, left, right))

AACEIMNR
AAMECIRN

def insert(key, left, right, letter):
    key.append(letter)
    left.append(-1)
    right.append(-1)
    new = len(key) - 1
    depth = 0
    node = 0
    placed = new == 0
    while not placed:
        depth = depth + 1
        if letter <= key[node]:
            if left[node] == -1:
                left[node] = new
                placed = True
            else:
                node = left[node]
        else:
            if right[node] == -1:
                right[node] = new
                placed = True
            else:
                node = right[node]
    return depth


def fill_rows(node, depth, key, left, right, rows):
    if node == -1:
        return
    if depth == len(rows):
        rows.append("")
    fill_rows(left[node], depth + 1, key, left, right, rows)
    rows[depth] = rows[depth] + key[node]
    fill_rows(right[node], depth + 1, key, left, right, rows)


word = input()
key = []
left = []
right = []
total = 0
for letter in word:
    total = total + insert(key, left, right, letter)

rows = []
fill_rows(0, 0, key, left, right, rows)
for depth in range(len(rows)):
    print("depth " + str(depth) + ": " + rows[depth])
print("internal path length: " + str(total))

Run it from this unit's folder:

python assets/l2.py < assets/l2/1.in

The input PROGRAM prints four rows, depth 0: P down to depth 3: AM, then internal path length: 12. assets/l2/3.in holds BOOKSHELF, with a duplicate O; draw its tree by hand first.

Lesson 3 — Heaps, and taking things out

Division: Intermediate and above.

Priority queues and min-heaps

The robot's urgent pile is a priority queue: whatever else happens, the smallest item must always be ready to take. ACSL keeps a priority queue as a heap, a tree where each node has at most two children and:

• every node is less than or equal to both of its children (so the root is the smallest item), and
• the tree has no gaps: every row is full except perhaps the bottom one, which is filled from the left.

This is a min-heap. Unlike a BST, a heap says nothing about left against right: only parent against child.

Inserting. Put the new item in the next free place (the bottom row, as far left as possible). Then, while it is smaller than its parent, swap it with its parent.

Example 1. The urgent pile: 30, 12, 25, 7, 18.

        7
      /   \
    12     25
   /  \
  30   18

Example 2. ACSL's sample: the letters of PROGRAMMING, inserted in order, give a min-heap whose rows are A, GG, MIPM and RORN. The bottom row, left to right, is RORN.

Positions. Number the places row by row, left to right, with the root at position 1. Then the children of position i are at positions 2i and 2i + 1, and the parent of position i is at i // 2. In Example 1, 30 is at position 4 and 18 at position 5.

Max-heaps. A max-heap turns every comparison round: each node is greater than or equal to its children, so the root is the largest. When inserting, swap while the new item is larger than its parent. A question always says which kind it wants; if it just says "heap", it means a min-heap.

A heap in Python

A heap fits neatly in a list: position i of the heap is heap[i]. Slot 0 is left unused (it holds ""), so the children of heap[i] really are heap[2 * i] and heap[2 * i + 1]. Inserting appends, then swaps upward while the parent is larger. The swap uses a tuple, a, b = b, a.

heap = [""]
for letter in "PROGRAMMING":
    heap.append(letter)
    i = len(heap) - 1
    while i > 1 and heap[i // 2] > heap[i]:
        heap[i // 2], heap[i] = heap[i], heap[i // 2]
        i = i // 2
print(heap)

start = 1
while start < len(heap):
    row = ""
    for i in range(start, min(2 * start, len(heap))):
        row = row + heap[i]
    print(row)
    start = 2 * start

['', 'A', 'G', 'G', 'M', 'I', 'P', 'M', 'R', 'O', 'R', 'N']
A
GG
MIPM
RORN

word = input()

heap = [""]
for letter in word:
    heap.append(letter)
    i = len(heap) - 1
    while i > 1 and heap[i // 2] > heap[i]:
        heap[i // 2], heap[i] = heap[i], heap[i // 2]
        i = i // 2

start = 1
while start < len(heap):
    row = ""
    for i in range(start, min(2 * start, len(heap))):
        row = row + heap[i]
    print(row)
    start = 2 * start

Run it from this unit's folder:

python assets/l3.py < assets/l3/1.in

The input PROGRAMMING prints the four rows of Example 2. assets/l3/3.in holds EDCBA: every new letter is the smallest so far, so every insert swaps all the way to the root.

Removing the root of a heap

Division: Senior and above.

Taking the smallest item out of a min-heap is ACSL's heap deletion:

1. Take out the root.
2. Move the last item (the bottom row's right-most item) into the root's place.
3. While it is larger than its smaller child, swap it with that smaller child.

In a max-heap, swap with the larger child while the item is smaller than it. If the two children are equal, this book swaps with the left one; ACSL's page does not say, and the exercises never depend on it.

Example 3. Take 7 out of the urgent pile, 7 / 12 25 / 30 18.

• The last item, 18, moves to the root: 18 / 12 25 / 30.
• Its children are 12 and 25; the smaller is 12, and 18 > 12, so swap: 12 / 18 25 / 30.
• Now 18 has one child, 30, and 18 < 30, so it stops.

The new rows are 12, 18 25, 30, and the robot's next urgent request is 12. That answers the third puzzle.

In Python, the list never shrinks: keep a count size of the items still in the heap, and only look at positions 1 to size.

heap = [0, 7, 12, 25, 30, 18]
size = 5

print("taken out:", heap[1])
heap[1] = heap[size]
size = size - 1
i = 1
done = False
while not done and 2 * i <= size:
    child = 2 * i
    if child + 1 <= size and heap[child + 1] < heap[child]:
        child = child + 1
    if heap[child] < heap[i]:
        heap[i], heap[child] = heap[child], heap[i]
        i = child
    else:
        done = True

for position in range(1, size + 1):
    print(position, heap[position])

taken out: 7
1 12
2 18
3 25
4 30

Deleting from a BST

Division: Senior and above.

ACSL deletes a node p from a BST like this, where f is the parent of p:

• No children: just remove p.
• One child: that child (with everything below it) takes p's place as f's child.
• Two children, a left child l and a right subtree r: l (with everything below it) takes p's place, and r is attached to the l tree where BST order puts it, as the right child of the right-most node of the l tree. To find that node, start at l and keep going right until there is no right child.

If p is the root, the node that takes its place becomes the new root. Items in this book never delete a letter that appears more than once, since ACSL gives no rule for which copy goes.

Example 4. The word MOUNTAINS gives this tree (the second N went left of the first):

          M
        /   \
       A     O
        \   / \
         I N   U
          /   /
         N   T
            /
           S

• Delete I: it is a leaf, so it just goes.
• Delete T: it has one child, S, which takes its place as the left child of U.
• Delete the root M: its left child l is A, and its right subtree r starts at O. A becomes the root. The right-most node of A's tree is found by going right from A: A, then I, which has no right child. So the whole O subtree becomes the right child of I:

      A
       \
        I
         \
          O
         / \
        N   U
       /   /
      N   T
         /
        S

The preorder traversal of the new tree is AIONNUTS. A good check: the new tree's inorder is still the sorted letters, minus the deleted one.