Chapter 8: Data Structures

Chapter 8A

Collection = group of items that we want to treat as conceptual unit

Homogenous ⇒ all items in the collection are of the same type
Heterogeneous ⇒ items can be of different types
E.g. lists in Python

Linear collections

Ordered by positions
E.g. grocery lists; stack of dinner plates; line of customers waiting at a bank

Hierarchical collections

Structure reminiscent of an upside-down tree
D3’s parent is D1
D3’s children are D4, D5, and D6
E.g. a file directory system; a company’s organisational tree; a book’s table of contents

Graph collections

Each data item can have many predecessors & successors
D3’s neighbours are its predecessors and successors
E.g. maps of airline routes between cities; electrical wiring diagrams for buildings

Unordered collections

Items are not in any particular order
One cannot meaningfully speak of an item’s predecessor or successor
E.g. bag of marbles

Operations on collections

Traversal: visits each item in a collection
Search and retrieval: search for a given target item or an item at a given position
Insertion: adds an item to a collection at a given position
Removal: deletes a given item or the item at a given position
Determine the size: determine no. of items a collection contains

To a user, a collection is an abstraction

Collections are abstract data types (ADTs)

ADT users are concerned with learning its interface
Developers are concerned with implementing their behaviour in the most efficient manner possible

“Data structure” and “concrete data type” ⇒ internal representation of an ADT’s data

2 data structures most often used to implement collections:

1. Array

Uses static approaches in storing and accessing data in the computer’s memory
Is the underlying data structure of a Python list, but is more restrictive than Python lists
Represents a sequence of items of the same data type (homogeneous)
Items can be accessed, retrieved, stored, or replaced at given index positions
[Advantage] Random access and contiguous memory
Array indexing is a random access operation
Address of an item: base address + offset
Steps for index operation:
Fetch base address of the array’s memory block
Return result of adding (index*k) to this address, where k = no. of memory cells required by an array item
[Disadvantage] Static Memory: arrays are static ⇒ the capacity or length of the array is determined at compile time, so need to specify the size with a constant
Physical Size and Logical Size:
Physical size of an array = total no. of array cells
Logical size of an array = no. of items currently in it
If logical size = 0, array is empty
Otherwise, at any given time, index of the last item in the array = logical size minus 1
If logical size = physical size, there is no more room for data in the array
To avoid reading garbage, must track both sizes
Operations on arrays: Indexing used in traversal, search and retrieval in an array
E.g. array A has an initial logical size of 0 and a default physical size, of capacity, of 5
Inserting an item into an array
Check for available space before attempting an insertion
Shift items from logical end of array to target index position down by 1
To open hole for new item at target index
Disadvantage if size is large
Assign new item to target index position
Increment logical size by 1
E.g. Insert item D5 at position 1 in an array of 4 items

`# check for available space` IF (logicalSize = physicalSize):¹ OUTPUT “No room for insertion” ELSE `# Shift items down by one position` FOR index ← logicalSize-1 TO targetIndex STEP -1 A[index+1] ← A[index] ENDFOR `# add new item and increment logical size` A[targetIndex] ← newItem logicalSize ← logicalSize + 1 ENDIF

Removing an item from an array
Shift items from next target index position to the logical end of the array up by 1 ⇒ to close hole left by removed item at target index
Disadvantage if size is large
Decrement logical size by 1
E.g. Removal of an item at position 1 in an array of 5 items

`# my ans (index here = index-1 in ans key)<br># shift items up by 1 position` FOR index ← targetIndex TO (logicalSize - 2) A[index] ← A[index + 1] ENDFOR `# decrement logical size` logicalSize ← logicalSize - 1
`# shift items up by 1 position` FOR index ← targetIndex+1 TO logicalSize-1 A[index-1] ← A[index] ENDFOR `# decrement logical size` logicalSize ← logicalSize - 1

2. Linked structure

Uses dynamic approaches in storing and accessing data in the computer’s memory
Like an array, it is a concrete data type used to implement many types of collections, including lists
Decouples logical sequence of items in the structure from any ordering in memory
I.e. Noncontiguous / dynamic memory representation scheme
Memory allocated dynamically during runtime; memory size is not fixed
vs fixed-size arrays

Advantages	Disadvantages
Have dynamic size → can grow and shrink dynamically vs arrays: restricted by its initial size More space efficient as only required space is used to store data vs arrays: have a pre-set amount of space allocated → possible wastage Insertions and deletions are more efficient → do not require shifting elements like arrays do	Require traversal and is slower to read or change vs arrays: allows for direct access and much faster to read or change More complex to implement and manage vs arrays: simpler and straightforward to use Each element in a linked list requires additional memory for storing pointers (or references) to the next element

Node = basic unit of representation in a linked structure
A singly linked node contains a data item and a link to the next node
Note direction of diagonal line
Can set up nodes to use noncontiguous memory in several ways
Using pointers (a null or nil represents the empty link as a pointer value): Memory allocated from the object heap
Using references to objects
In Python, None can mean an empty link
Automatic garbage collection frees programmers from managing the object heap²
Using 2 parallel arrays
-1 for next for D4 means that D4 points to None
Defining a Node Class
Flexibility and ease of use are critical
Node instance variables are usually referenced without method calls, and constructors allow user to set a node’s link(s) when the node is created

“”” File: node.py Node class for one-way linked structures “”” `class Node:` `def __init__(self, data, next = None):` `# Instantiates a Node with default next of None` `self.data = data` `self.next = next`

Using the Node Class
Node variables are initialized to None or a new Node object

# Just an empty link `node1 = None` `# a node containing data and an empty link` `node2 = Node(“A”, None)` `# a node containing data and a link to node2` `node3 = Node(“B”, node2)`

To place the first node at the beginning of the linked structure that already contains node2 and node3:
node1.next = node3 raises AttributeError
⇒ Solution:
node1 = Node(“C”, node3)
OR
node1 = Node(“C”, None)
node1.next = node3
To guard against exceptions:
if nodeVariable != None:
<access a field in nodeVariable>
Like arrays, linked structures are processed with loops

`from node import Node` `head = None` `# Add five nodes to the beginning of the linked structure` `for count in range(1,6): # for count = 1 TO 5` `head = Node(count, head)` `# Print the contents of the structure` `probe = head # initialise the temporary pointer variable` `while probe != None:` `print(probe.data)` `probe = probe.next`

Operations on linked structures: almost all operations on arrays are index based
Traversal and searching operations are similar: both must traverse from the ‘start’ of the structure. Difference: whether to use index or link
The retrieval operation is straightforward for an array but more complicated for a linked structure since traversal is required
Similarly for insertion and removal of a particular item, except no shifting required for a linked structure to perform insertion or removal
Traversal → Use a temporary pointer variable in order to visit each node without deleting it

`probe = head` `while probe != None:` <use or modify probe.data> `probe = probe.next`

None serves as a sentinel that stops the process
Searching → Resembles a traversal, but 2 possible sentinels:
Empty link (i.e. target item is not present)
Data item that equals the target item

`probe = head` `while (probe != None) and (targetItem != probe.data):` `probe = probe.next` `if probe == None:` <targetItem is not in the linked structure>³⁴ `else:` <targetItem has been found>

Accessing the $i^{t h}$ item of a linked structure is also a sequential search operation ⇒ start at first node and count no. of links until the $i^{t h}$ node is reached

`# Assumes 1 <= i <= n, where n is no. of nodes in the linked structure` `probe = head` `for count in range(i-1):` `probe = probe.next` `return probe.data`

If i = 4, since linked list now is 5 → 4 → 3 → 2 → 1, will return 2
Some linked structures do not support random access ⇒ cannot use a binary search
Replacement: employ traversal pattern
If target item is not present: no replacement occurs
If target item is present: the new item replaces it
Insertion: to add a given item at a given position, traverse the list to find the insert position
Insert at front: updates the head pointer
Insert at position i: updates the pointer of the (i-1 $)^{t h}$ node

`# Assumes 1 <= i <= n+1, where n is the no. of nodes in the linked structure` `if i == 1: # case 1: insert at front/head` `head = Node(newItem, head)` `else: # case 2: insert at position i` `# Search for node at position i-1` `probe = head` `for index in range(i-2): # (find (i-1)th node to update pointer)` `probe = probe.next` `# Insert after node at position i-1` `probe.next = Node(newItem, probe.next)`
`# my code to test:` `# inserting node` `# assumes 1 <= i <= n, where n is the number of nodes in the linked structure` `def insert(newItem, i):` global head⁵⁶ `if i == 1:` `head = Node(newItem, head)` `else:` `probe = head` `for index in range(i-2): # find (i-1)th node to update pointer` `probe = probe.next` `probe.next = Node(newItem, probe.next)` insert(‘newItem’, 3) `def display():` `probe = head` `while probe:` `print(probe.data, end=' -> ')` `probe = probe.next` `print('None')` display() OUTPUT: 5 -> 4 -> newItem -> 3 -> 2 -> 1 -> None

# Assumes 1 <= i <= n+1, where n is the no. of nodes in the linked structure

if i == 1: # case 1: insert at front/head
head = Node(newItem, head)
else: # case 2: insert at position i
# Search for node at position i-1
probe = head
for index in range(i-2): # (find (i-1)th node to update pointer)
probe = probe.next
# Insert after node at position i-1
probe.next = Node(newItem, probe.next)

# my code to test:
# inserting node
# assumes 1 <= i <= n, where n is the number of nodes in the linked structure
def insert(newItem, i):
global head⁵⁶
if i == 1:
head = Node(newItem, head)
else:
probe = head
for index in range(i-2): # find (i-1)th node to update pointer
probe = probe.next
probe.next = Node(newItem, probe.next)

insert(‘newItem’, 3)
def display():
probe = head
while probe:
print(probe.data, end=' -> ')
probe = probe.next
print('None')
display()
OUTPUT: 5 -> 4 -> newItem -> 3 -> 2 -> 1 -> None

E.g. a trace of the insertion of an item at position 3 in a linked structure containing 3 items:
Deletion: to remove a given item or the item at a given position, traverse the list to search for the node to be deleted
Delete at front – updates the head pointer
Delete at position i – updates the pointer of the (i-1 $)^{t h}$ node, i.e. the predecessor node

# Assumes that the linked structure has at least 1 item⁷⁸

if head.data == targetItem:
head = head.next
else:
# Search for predecessor of the node to be deleted
probe = head
while (probe.next != None) and (targetItem != probe.next.data):
probe = probe.next
if probe.next == None:
<targetItem is not in the linked structure>
else:
# Delete after predecessor node
probe.next = probe.next.next

E.g. a trace of the removal of data item D3 in a linked structure containing 4 items
E.g. Linked list insert / delete by position

# 1. write: node class
class Node:
def __init__(self, data, next):
self.data = data
self.next = next

# linked list class
class LinkedList:
# 2. write: init method
def __init__(self):
self.head = None

# 4. write: insert method
# takes parameters: value, p
# insert value at position p, same as notes
def insert(self, value, p):
if p == 1:
self.head = Node(value, self.head)
else:
probe = self.head
for i in range(p - 2):
probe = probe.next
probe.next = Node(value, probe.next)

# 5. write: delete method
# takes parameter: p
# delete the node at position p
# if p = 1, delete head
# if p = 2, delete the second node
# similar to notes insertion code
# NOTE: THIS IS FOR 1-BASED INDEXING!!!
def delete(self, p):
if p == 1:
self.head = self.head.next
else:
probe = self.head
for i in range(p - 2):
probe = probe.next
probe.next = probe.next.next

# 3. write: show method
# output all contents from head
def show(self):
probe = self.head
while probe != None:
print(probe.data)
probe = probe.next

# create an empty linked list
link = LinkedList()

E.g. linked list insert / delete by value

`# Using probe` `# node class` `class Node:` `def __init__(self, data, next):` `self.data = data` `self.next = next` `# linked list class` `class LinkedList:` `# init method` `def __init__(self):` `self.head = None` `# 1. write: insert method` `# takes parameters: value` `# insert value in alphabetical order` `def insert(self, value):` `if self.head == None or value < self.head.data:` `self.head = Node(value, self.head)` `else:` `probe = self.head` `while probe.next != None and value > probe.next.data:` `probe = probe.next` `probe.next = Node(value, probe.next)` `# 2. write: delete method` `# takes parameter: value` `# delete the node with value` `# if not found, print error message` `# same as notes` `def delete(self, value):` `if self.head == None: # LinkedList has no head` `print('LinkedList is empty.')` `elif value == self.head.data:` `self.head = self.head.next` `else:` `probe = self.head` `while probe.next != None and value > probe.next.data:` `probe = probe.next` `if probe.next == None:` `print('this item is not in the linked list')` `else:` `probe.next = probe.next.next` `⇒ change to while probe``.next` `!= None?` `# show method` `# output all contents from head` `def show(self):` `probe = self.head` `while probe != None:` `print(probe.data)` `probe = probe.next` `# create an empty linked list` `link = LinkedList()` `# test insert method` `link.insert('banana')` `link.insert('apple')` `link.insert('carrot')` `print('Linked list after insert:')` `link.show()` `# output should be apple, banana, carrot,` `# test delete method` `link.delete('apple')` `link.delete('durian') # output error message` `print('Linked list after delete:')` `link.show()` `# output should be banana, carrot`
`# Using pre (previous) and cur (current)` `# 1. write: node class` `class Node:` `def __init__(self, data, next):` `self.data = data` `self.next = next` `# linked list class` `class LinkedList:` `# 2. write: init method` `def __init__(self):` `self.head = None` `# 4. write: insert method` `# takes parameters: value` `# insert value in alphabetical order` `def insert(self, value):` `if self.head == None or value < self.head.data:` `self.head = Node(value, self.head)` `else:` `pre = None` `cur = self.head` `while cur != None and value > cur.data:` `pre = cur` `cur = cur.next` `pre.next = Node(value, cur)` `# 5. write: delete method` `# takes parameter: value` `# delete the node with value` `# if not found, print error message` `def delete(self, value):` `if value == self.head.data:` `self.head = self.head.next` `else:` `pre = None` `cur = self.head` `while cur != None and value > cur.data:` `pre = cur` `cur = cur.next` `if cur == None:` `print('this item is not in the linked list')` `else:` `pre.next = cur.next` `# 3. write: show method` `# output all contents from head` `def show(self):` `probe = self.head` `while probe != None:` `print(probe.data)` `probe = probe.next`
`class Node:` `def __init__(self, data, next):` `self.data = data` `self.next = next` `class LinkedList:` `def __init__(self):` `self.head = None` `def insert(self, value):` `if self.head == None or value < self.head.data:` `self.head = Node(value, self.head)` `else:` `probe = self.head` `while probe.next != None and value > probe.next.data:` `probe = probe.next` `probe.next = Node(value, probe.next)` `def delete(self, value):` `if self.head == None: # linked list has no head` `print("LinkedList is empty.")` `elif self.head.data == value: # target value is at head` `self.head = self.head.next` `else:` `probe = self.head` `while (probe.next != None) and (probe.next.data != value):` `probe = probe.next` `if probe.next == None:` `print("target item not in linked list")` `else:` `probe.next = probe.next.next` `def display(self):` `probe = self.head` `while probe != None:` `print(probe.data)` `probe = probe.next` `list = LinkedList()` list.insert(1) list.insert(2) list.insert(3) list.delete(2) list.display() `# Note: Adding a head parameter to the constructor (i.e., __init__(self, head=None)) is unnecessary because a linked list typically starts empty, with no head node. Allowing external code to set head directly may expose internal structure that should remain encapsulated.`

# Using probe
# node class
class Node:
def __init__(self, data, next):
self.data = data
self.next = next

# linked list class
class LinkedList:
# init method
def __init__(self):
self.head = None

# 1. write: insert method
# takes parameters: value
# insert value in alphabetical order
def insert(self, value):
if self.head == None or value < self.head.data:
self.head = Node(value, self.head)
else:
probe = self.head
while probe.next != None and value > probe.next.data:
probe = probe.next
probe.next = Node(value, probe.next)

# 2. write: delete method
# takes parameter: value
# delete the node with value
# if not found, print error message
# same as notes
def delete(self, value):
if self.head == None: # LinkedList has no head
print('LinkedList is empty.')
elif value == self.head.data:
self.head = self.head.next
else:
probe = self.head
while probe.next != None and value > probe.next.data:
probe = probe.next
if probe.next == None:
print('this item is not in the linked list')
else:
probe.next = probe.next.next

⇒ change to while probe.next != None?

# show method
# output all contents from head
def show(self):
probe = self.head
while probe != None:
print(probe.data)
probe = probe.next

# create an empty linked list
link = LinkedList()

# test insert method
link.insert('banana')
link.insert('apple')
link.insert('carrot')
print('Linked list after insert:')
link.show()
# output should be apple, banana, carrot,

# test delete method
link.delete('apple')
link.delete('durian') # output error message
print('Linked list after delete:')
link.show()
# output should be banana, carrot

# Using pre (previous) and cur (current)

# 1. write: node class
class Node:
def __init__(self, data, next):
self.data = data
self.next = next

# linked list class
class LinkedList:
# 2. write: init method
def __init__(self):
self.head = None

# 4. write: insert method
# takes parameters: value
# insert value in alphabetical order
def insert(self, value):
if self.head == None or value < self.head.data:
self.head = Node(value, self.head)
else:
pre = None
cur = self.head
while cur != None and value > cur.data:
pre = cur
cur = cur.next
pre.next = Node(value, cur)

# 5. write: delete method
# takes parameter: value
# delete the node with value
# if not found, print error message
def delete(self, value):
if value == self.head.data:
self.head = self.head.next
else:
pre = None
cur = self.head
while cur != None and value > cur.data:
pre = cur
cur = cur.next
if cur == None:
print('this item is not in the linked list')
else:
pre.next = cur.next

# 3. write: show method
# output all contents from head
def show(self):
probe = self.head
while probe != None:
print(probe.data)
probe = probe.next

class Node:
def __init__(self, data, next):
self.data = data
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def insert(self, value):
if self.head == None or value < self.head.data:
self.head = Node(value, self.head)
else:
probe = self.head
while probe.next != None and value > probe.next.data:
probe = probe.next
probe.next = Node(value, probe.next)
def delete(self, value):
if self.head == None: # linked list has no head
print("LinkedList is empty.")
elif self.head.data == value: # target value is at head
self.head = self.head.next
else:
probe = self.head
while (probe.next != None) and (probe.next.data != value):
probe = probe.next
if probe.next == None:
print("target item not in linked list")
else:
probe.next = probe.next.next
def display(self):
probe = self.head
while probe != None:
print(probe.data)
probe = probe.next
list = LinkedList()
list.insert(1)
list.insert(2)
list.insert(3)
list.delete(2)
list.display()

# Note: Adding a head parameter to the constructor (i.e., __init__(self, head=None)) is unnecessary because a linked list typically starts empty, with no head node. Allowing external code to set head directly may expose internal structure that should remain encapsulated.

Free Space List: a linked list that acts as resource and recycle of nodes for data structures (linked list, stack, queue, BST)

Used to:
Take a new node from the free space list
OR when remove a node, add it to free space list
⇒ “extra storage”

Initial Status: empty data structure with full free space list

Adding item: item is placed in the first node in the free space list, and then inserted into the data structure

E.g. add ‘d’ to the linked list below
Note: head refers to the c node; free refers to the d node
CODE: Free = Free.next

Removing item: the node containing the item is removed from the data structure, and added to the front of the free space list

E.g. remove ‘f’ from the linked list below
CODE:
temp.next = Free
I.e. ‘f’ is now the current first node in the free list
So f no longer links to m⁹¹⁰
After f, .next is now a node from the free space list
Free = temp
‘f’ is placed right after the free header
⇒ So now “2 separate routes”
Head c → m → s¹¹
Free f → free space list

Chapter 8B

Stack

Last-in-first-out (LIFO) structure: access is completely restricted to just one end, called the top

Has 2 basic operations (‘methods’): push and pop
E.g.
A stack type is not built into Python, but can use a Python list to emulate a stack
E.g. use list method append to push and pop to pop
However, the extra list operations violate the spirit of a stack as an ADT
2 different implementations of stack:
ArrayStack
LinkedStack
Item joins at top of a list, and is removed from top of list
Last item to join will be released first

Stack interface

Provides push, pop, and these operations
Where s refers to a stack:

Stack method	What it does
s.push(item)	Inserts item at top of stack
s.pop()	Removes and returns item at top of stack Precondition: Stack must not be empty; raises an error if empty
s.peek()	Returns item at top of stack Precondition: Stack must not be empty; raises an error if empty
s.isEmpty()	Returns True if stack is empty, False otherwise
s.__len__()	Same as len(s), returns no. of items currently in stack
s.__str__()	Same as str(s), returns string representation of the stack

Operation	State of stack after operation	Value returned	Comment
			Initially, stack is empty
s.push(a)	a		Stack contains the single item a
s.push(b)	a b		b is top item on stack
s.push(c)	a b c		c is top item
s.isEmpty()	a b c	False	Stack is not empty
len(s)	a b c	3	Stack contains 3 items
s.peek()	a b c	c	Returns top item on stack without removing it
s.pop()	a b	c	Remove top item forms tack and return it. b is now the top item.
s.pop()	a	b	Remove and return b
s.pop()		a	Remove and return a
s.isEmpty()		True	Stack is empty
s.peek()		exception	Peeking at empty stack raises an exception
s.pop()		exception	Popping an empty stack raises an exception
s.push(d)	d		d is the top item

Stack application: Matching Parentheses

Compilers need to determine if bracketing symbols in expressions are balanced correctly

E.g. of expression	Status	Reason
(…)…(…)	Balanced
(…)…(…	Unbalanced	Missing a closing ) at the end
)…(…(…)	Unbalanced	The closing ) at the beginning has no matching opening ( and one of the opening parentheses has no closing parenthesis
[…(…)…]	Balanced
[…(…]…)	Unbalanced	The bracketed sections are not nested properly

Scan expression and keep checking on the matching:
Scan expression; push left brackets (opening brackets) onto a stack
On encountering a closing bracket, if stack is empty or if item on top of stack is not an opening bracket of the same type → brackets do not balance
Pop an item off the top of stack and, if it is the right type, continue scanning expression
When end of expression reached, stack should be empty
Else, brackets do not balance

Stack application: Evaluating Arithmetic Expressions

An arithmetic expression can be represented by 2 forms:
Infix form: each operator located between its operands (e.g. A+B)
Postfix form: an operator immediately follows its operands (e.g. AB+)
I.e. Reverse Polish Notation

Infix form	Postfix form	Value
34	34	34
34 + 22	34 22 +	56
34 + 22 * 2 ⇒ 34 + 44	34 22 2 * + ⇒ 34 44 +	78
34 * 22 + 2	34 22 * 2 +	750
(34 + 22) * 2	34 22 + 2 *	112

In both forms, operands appear in the same order, but operators do not
Infix form sometimes require parenthesis, postfix form never does
Infix evaluation involves rules of precedence, postfix evaluation applies operators as soon as they are encountered
To evaluate infix expression, convert infix to postfix
Start with empty postfix expression and an empty stack
Stack will hold operators +-*/ and left parentheses
Scan across infix expression from left to right
Append any operand (numbers) to postfix expression
Push any ( onto the stack
On encountering an operator:
Pop off the stack all operators with equal or higher precedence
Remember Last-In-First-Out
Append them to postfix expression
Push scanned operator onto stack
On encountering a ), pop operators from stack to postfix expression until meeting matching (, which is discarded
On encountering end of infix expression, pop remaining operators from stack to the postfix expression
E.g.
Note the “+*” from operator stack flips to become “*+” in postfix
E.g.
Evaluating postfix expressions
Steps
Scan across postfix expression from left to right
On encountering an operator, apply it to the 2 preceding operands; replace all 3 by the result
Continue scanning until you reach expression’s end, at which point only the expression’s value remains
Use a stack of operands to express this procedure as a computer algorithm
In the algorithm, token = an operand (number) or operator (+-*/)

Create a new stack While there are more tokens in the expression Get the next token If the token is an operand Push the operand onto the stack Else If token is an operator Pop the top-two operands from stack Apply operator to the 2 operands just popped Push resulting value onto the stack Endif Endif EndWhile Return value as top of stack

E.g.

Stack application: Memory Management

Computer’s run-time system must keep track of various details that are invisible to programmer

Associating variables with data objects stored in memory so they can be located when these variables are referenced
Remembering address of the instruction in which a method or function is called, so control can return to the next instruction when that function or method finishes execution
Allocating memory for a function’s or a method’s arguments and temporary variables, which exist only during the execution of that function or method

When a subroutine (function or method) is called (i.e. activated), an activation record (i.e. stack frame) is created to store the current environment for that function

Its contents include parameters, local/temporary variables, return address, and return value
Data structure should store these activation records so that they can be recovered and the system resets when the function resumes execution

Problem: FunctionA can call FunctionB
FunctionB can call FunctionC
When a function calls another function, it interrupts its own execution and needs to be able to resume its execution in the same state it was when it was interrupted
When FunctionC finishes, control should return to FunctionB
When FunctionB finishes, control should return to FunctionA
⇒ order of returns from a function is the reverse of function invocations
I.e. LIFO behaviour

⇒ use a run-time stack, manipulated at run-time, to store activation records

When a function is called:

Push a copy of its activation record onto the run-time stack
Copy its arguments into the parameter spaces
Transfer control to the starting address of the body of the function

⇒ the top activation record in the run-time stack is always that of the function currently being executed

When a function terminates / returns:

Pop the activation record of terminated function from run-time stack
Use new top activation record to restore the environment of the interrupted function and resume execution of the interrupted function

E.g. recursive function for calculating powers

`def Power(x, n):` `# Power() calculates x to the nth power recursively<br>if n == 0:` `return 1` `else:` `return Power(x, n-1) * x # A (return address is A)` `def main():` `print(Power(4,3)) # B` main()

Return addresses, A and B = locations of instructions where execution is to resume when program or function is reactivated
When execution of main program is initialised, its activation record is created

Used to store values of variables, actual parameters, return address, and so on during the time the program is active
When execution of main program is interrupted by the function call Power(4,3), the parameters 4 and 3 and the return address B (+ other items of information) are stored in the activation record, and this record is pushed onto a stack
The function Power() now becomes active, & an activation record is created for it
When return Power(x, n-1)* x is encountered, the execution of Power() is interrupted. The actual parameter 4 and 2 (i.e. P(4,2)) for this function call with parameter x = 4 and n - 1 = 3 - 1 = 2 and the return address A (and other items of information) are stored in the current activation record, and this record is pushed onto the stack of activation records

Since this is a new call to Power(), another activation record is created, and when this function call is interrupted by the call Power(4,1), this activation record is pushed onto the stack

The call Power(4,1) results in the creation of another activation record, and when its execution is interrupted by the call Power(4,0), this activation record is pushed onto the stack
Execution of Power() with parameters 4 and 0 terminates with no interruptions and calculates the value 1 for Power(4,0). The activation record for this call is then popped from the stack, and the execution resumes at the statement specified by the return address in it:
Execution of the preceding call to Power() with parameters 4 and 1 then resumes and terminates without interruption, so that its activation record is popped from the stack, the value 4 is returned, and the previous call with parameters 4 and 2 is reactivated at statement A:
Process continues until the value 64 is computed for the original call Power(4,3), and execution of the main program is resumed at the statement specified by the return address B in its activation record

Stack implementation using array:

Test Driver

`def main():` `# test either implementation with same code` `s = ArrayStack()` `# s = LinkedStack()` `print("Length:", len(s))` `print("Empty:", s.isEmpty())` `print("Push 1-10")` `for i in range(10):` s.push(i+1) `print("Peeking:", s.peek())` `print("Items(bottom to top):", s)` `print("Length:", len(s))` `print("Empty:", s.isEmpty())` `print("Push 11")` s.push(11) `print("Popping items (top to bottom):", end = ' ')` `while not s.isEmpty(): print(s.pop(), end = ' ')` `print("\nLength:", len(s))` `print("Empty:", s.isEmpty())`
output: Length: 0 Empty: True Push 1-10 Peeking: 10 `# note: items in stack print from bottom to top in the stack’s string representation` Items (bottom to top): 1 2 3 4 5 6 7 8 9 10 Length: 10 Empty: False Push 11 `# note: when popped, they print from top to bottom` Popping items (top to bottom): 11 10 9 8 7 6 5 4 3 2 1 Length: 0 Empty: True

def main():
# test either implementation with same code
s = ArrayStack()
# s = LinkedStack()
print("Length:", len(s))
print("Empty:", s.isEmpty())
print("Push 1-10")
for i in range(10):
s.push(i+1)
print("Peeking:", s.peek())
print("Items(bottom to top):", s)
print("Length:", len(s))
print("Empty:", s.isEmpty())
print("Push 11")
s.push(11)
print("Popping items (top to bottom):", end = ' ')
while not s.isEmpty(): print(s.pop(), end = ' ')
print("\nLength:", len(s))
print("Empty:", s.isEmpty())

output:
Length: 0
Empty: True
Push 1-10
Peeking: 10
# note: items in stack print from bottom to top in the stack’s string representation
Items (bottom to top): 1 2 3 4 5 6 7 8 9 10
Length: 10
Empty: False
Push 11
# note: when popped, they print from top to bottom
Popping items (top to bottom): 11 10 9 8 7 6 5 4 3 2 1
Length: 0
Empty: True

Stack implementation using array structure
Built around items (an array) and 2 integers (top and size)
Initially, array has default capacity of n positions, top = -1, size = 0
To push an item onto the stack, you increment the top and size, and store the item at the location items[top]
Size = no. of items currently in the stack
Top = position of the topmost item in a nonempty stack
An attempt to add an item to a full stack causes an error message ⇒ stack overflow
To pop the stack, return items[top] and decrement top and size
An attempt to delete an item from an empty stack causes an error message ⇒ stack underflow

`# code for ArrayStack (Fixed Size)` `class ArrayStack:` `# array-based stack implementation` `DEFAULT_CAPACITY = 12` `def __init__(self):` `self._items = [''] * ArrayStack.DEFAULT_CAPACITY` `self._top = -1` `self._size = 0` `def push(self, newItem):` `# Inserts newItem at top of stack` `# Precondition: stack is not full` `if self._size == ArrayStack.DEFAULT_CAPACITY:` `# OR if self._top == ArrayStack.DEFAULT_CAPACITY - 1` `print("Stack is full. Abort operation!")` `else:` `# new Item goes at logical end of array` self._top += 1 self._size += 1 self._items[self._top] = newItem `def pop(self):` `# Removes and returns the item at top of stack` `# Precondition: stack is not empty` `if self.isEmpty(): # or if self._top == -1` `print("Stack is empty. Abort operation!")` `return ""` `else:` `oldItem = self._items[self._top]` self._top -= 1 self._size -= 1 `return oldItem` `def peek(self):` `# Returns item at top of stack` `# Precondition: the stack is not empty` `if self.isEmpty():` `print("Stack is empty. Abort operation!")` `return ""` `else:` `return self._items[self._top]` `def __len__(self):` `# Returns no. of items in the stack` `return self._size` `def isEmpty(self):` `return len(self) == 0` `def __str__(self): # display` `# Items strung from bottom to top` `result = ""` `for i in range(len(self)):` result += str(self._items[i]) + ” “ `return result` `# OR Items strung from top of stack (to bottom)` `# for i in range(self._top, -1, -1):` `# print(self._items[i], end = ' ')` `# print()`
`# code for ArrayStack (Dynamic Size)` `class ArrayStack:` `# array-based stack implementation` `def __init__(self):` `self._items = []` `self._top = -1` `self._size = 0` `def push(self, newItem):` `# Inserts newItem at top of stack` `# new Item goes at logical end of array` self._items.append(newItem) self._top += 1 self._size += 1 `def pop(self):` `# Removes and returns the item at top of stack` `# Precondition: stack is not empty` `if self.isEmpty(): # or if self._top == -1` `print("Stack is empty. Abort operation!")` `return ""` `else:` `oldItem = self._items.pop(self._top)` self._top -= 1 self._size -= 1 `return oldItem` `def peek(self):` `# Returns item at top of stack` `# Precondition: the stack is not empty` `if self.isEmpty():` `print("Stack is empty. Abort operation!")` `return ""` `else:` `return self._items[self._top]` `def __len__(self):` `# Returns no. of items in the stack` `return self._size` `def isEmpty(self):` `return len(self) == 0` `def __str__(self): # display` `# Items strung from bottom to top` `result = ""` `for i in range(len(self)):` result += str(self._items[i]) + ” “ `return result` `# OR Items strung from top of stack (to bottom)` `# for i in range(self._top, -1, -1):` `# print(self._items[i], end = ' ')` `# print()`
`s = ArrayStack()` `# test for correct push` `# print(s._top)` s.push(‘a’) s.push(‘b’) s.push(‘c’) `print(s)` `# print(str(s))`

# code for ArrayStack (Fixed Size)
class ArrayStack:
# array-based stack implementation
DEFAULT_CAPACITY = 12
def __init__(self):
self._items = [''] * ArrayStack.DEFAULT_CAPACITY
self._top = -1
self._size = 0
def push(self, newItem):
# Inserts newItem at top of stack
# Precondition: stack is not full
if self._size == ArrayStack.DEFAULT_CAPACITY:
# OR if self._top == ArrayStack.DEFAULT_CAPACITY - 1
print("Stack is full. Abort operation!")
else:
# new Item goes at logical end of array
self._top += 1
self._size += 1
self._items[self._top] = newItem

def pop(self):
# Removes and returns the item at top of stack
# Precondition: stack is not empty
if self.isEmpty(): # or if self._top == -1
print("Stack is empty. Abort operation!")
return ""
else:
oldItem = self._items[self._top]
self._top -= 1
self._size -= 1
return oldItem

def peek(self):
# Returns item at top of stack
# Precondition: the stack is not empty
if self.isEmpty():
print("Stack is empty. Abort operation!")
return ""
else:
return self._items[self._top]

def __len__(self):
# Returns no. of items in the stack
return self._size

def isEmpty(self):
return len(self) == 0

def __str__(self): # display
# Items strung from bottom to top
result = ""
for i in range(len(self)):
result += str(self._items[i]) + ” “
return result
# OR Items strung from top of stack (to bottom)
# for i in range(self._top, -1, -1):
# print(self._items[i], end = ' ')
# print()

# code for ArrayStack (Dynamic Size)
class ArrayStack:
# array-based stack implementation
def __init__(self):
self._items = []
self._top = -1
self._size = 0
def push(self, newItem):
# Inserts newItem at top of stack
# new Item goes at logical end of array
self._items.append(newItem)
self._top += 1
self._size += 1

def pop(self):
# Removes and returns the item at top of stack
# Precondition: stack is not empty
if self.isEmpty(): # or if self._top == -1
print("Stack is empty. Abort operation!")
return ""
else:
oldItem = self._items.pop(self._top)
self._top -= 1
self._size -= 1
return oldItem

def peek(self):
# Returns item at top of stack
# Precondition: the stack is not empty
if self.isEmpty():
print("Stack is empty. Abort operation!")
return ""
else:
return self._items[self._top]

def __len__(self):
# Returns no. of items in the stack
return self._size

def isEmpty(self):
return len(self) == 0

def __str__(self): # display
# Items strung from bottom to top
result = ""
for i in range(len(self)):
result += str(self._items[i]) + ” “
return result
# OR Items strung from top of stack (to bottom)
# for i in range(self._top, -1, -1):
# print(self._items[i], end = ' ')
# print()

s = ArrayStack()
# test for correct push
# print(s._top)
s.push(‘a’)
s.push(‘b’)
s.push(‘c’)
print(s)
# print(str(s))

Code for application of stack on matching parentheses
Assume the module stack includes the class ArrayStack

# brackets.py
# Checks expressions for matching brackets
from stack import ArrayStack
def bracketsBalance(exp):
# exp represents the expression
stk = ArrayStack() # create a new stack
for ch in exp:
if ch in ['[', '(']: # push an opening bracket
stk.push(ch)

# process a closing bracket
elif ch in [']',')']:
if stk.isEmpty(): # not balanced
return False
chFromStack = stk.pop()
# brackets must be of same type and match up
if (ch == ']' and chFromStack != '[') or (ch == ')' and chFromStack != '('):
return False

return stk.isEmpty() # if stack is empty, all brackets matched up (True)
def main():
exp = input("Enter a bracketed expression: ")
if bracketsBalance(exp):
print("OK") # If True
else:
print("Not OK") # If False
main()

Stack implementation using linked structure
Uses a singly linked sequence of nodes with a variable top pointing at the list’s head, and a variable size to track no. of items on the stack
Top is the first node, which contains data a
Linked implementation requires 2 classes: LinkedStack and Node
Node class contains 2 fields:
data: an item on the stack
next: a pointer to the next node
Push and pop by adding and removing nodes at the head of the list

from node import Node
class LinkedStack:
# link-based stack implementation
def __init__(self):
self._top = None
self._size = 0

def push(self, newItem):
# inserts newItem at top of stack
self._top = Node(newItem, self._top)
self._size += 1
def pop(self):
# removes and returns item at top of stack
# precondition: stack is not empty
if self.isEmpty(): # or if self._top == None:
print("Stack is empty. Abort operation")
return ""
else:
oldItem = self._top.data
self._top = self._top.next
self._size -= 1
return oldItem
def peek(self):
# returns item at top of stack
# precondition: stack is not empty
if self.isEmpty(): # or if self._top == None:
print("Stack is empty. Abort operation")
return ""
else:
return self._top.data

def len(self):
# returns no. of items in stack
return self._size

def isEmpty(self):
return len(self) == 0

def __str__(self):
# items strung from bottom to top
result = ''
probe = self._top
while probe != None:
result = str(probe.data) + ' ' + result
# or print(probe.data, end = ' ')
probe = probe.next
return result

Chapter 8C

Queue

Linear collections (like stacks) with the following features:
Insertions are restricted to one end (rear)
Removals are restricted to one end (front)
Queues supports a first-in-first-out (FIFO) protocol
2 fundamental operations:
Enqueue: adds an item to the rear of a queue
Dequeue: removes an item from the front
The following is a queue as it might appear at various stages in its lifetime
Queue’s front is on the left; its rear is on the right
Item dequeued, or served next, is always the item that has been waiting the longest
Most queues involve scheduling access to shared resources
CPU access: Processes are queued for access to a shared CPU
Printer access: Print jobs are queued for access to a shared laser printer

Queue implementation using array structure

(similar to stack) Can use a Python list to emulate a queue
Use list method append to add an element to rear of queue
Use pop to remove an element from front of queue
But the extra list operations violate the spirit of a queue as an ADT
Given a queue named q:

Queue method	What it does
q.enqueue(item)	Inserts item at rear of queue
q.dequeue()	Removes and returns the item at the front of the queue Precondition: the queue must not be empty; error raised if empty
q.peek()	Returns item at front of queue Precondition: the queue must not be empty; error raised if empty
q.isEmpty()	Returns True if queue is empty, False otherwise
q.__len__()	Same as len(q). Returns no. of items currently in queue
q.__str__()	Same as str(q). Returns string representation of the queue

E.g.

Operation	State of queue after operation	Value returned	Comment
			Initially, queue is empty
q.enqueue(a)	a		Queue contains the single item a
q.enqueue(b)	a b		a is at the front of the queue and b is at the rear
q.enqueue(c)	a b c		c is added at the rear
q.isEmpty()	a b c	False	The queue is not empty
len(q)	a b c	3	The queue contains 3 items
q.peek()	a b c	a	Returns front item of queue without removing it
q.dequeue()	b c	a	Remove front item from queue and return it b is now front item
q.dequeue()	c	b	Remove and return b
q.dequeue()		c	Remove and return c
q.isEmpty()		True	The queue is empty
q.peek()		exception	Peeking at an empty queue throws an exception
q.dequeue()		exception	Trying to dequeue an empty queue throws an exception
q.enqueue(d)	d		d is the front item

Queue implementation using linked structure

Enqueue adds a node at the end
For fast access to both ends of a queue’s linked structure, provide external pointers to both ends
Instance variables front and rear of LinkedQueue are given an initial value of None
size variable tracks no. of elements currently in queue
During an enqueue operation, create a new node, set the next pointer of the last node to the new node, then set the variable rear to the new node:

`def enqueue(self, newItem):` `# adds newItem to rear of queue` `newNode = Node(newItem, None)` `if self.isEmpty():` `self._front = newNode` `else:` `self._rear.next = newNode` `self._rear = newNode` self._size += 1

Dequeue is similar to pop: removes first node in the sequence
But if queue becomes empty after a dequeue operation, the front and rear pointers must both be set to None

`def dequeue(self):` `# removes and returns the item at front of queue` `# precondition: queue is not empty` `if self.isEmpty():` `print("Queue is empty. Abort operation!")` `return ""` `else:` `oldItem = self._front.data` `self._front = self._front.next` `if self._front == None:` `self.rear = None` self._size -= 1 `return oldItem`

Complete code for LinkedQueue:

from node import Node
class LinkedQueue:
# Link-based queue implementation
def __init__(self):
self._front = None
self._rear = None
self._size = 0
def enqueue(self, newItem):
# adds newItem to rear of queue
newNode = Node(newItem, None)
if self.isEmpty():
self._front = newNode
else:
self._rear.next = newNode
self._rear = newNode
self._size += 1

def dequeue(self):
# removes and returns the item at front of queue
# precondition: queue is not empty
if self.isEmpty():
print("Queue is empty. Abort operation!")
return ""
else:
oldItem = self._front.data
self._front = self._front.next
if self._front == None:
self.rear = None
self._size -= 1
return oldItem

def peek(self):
# returns the item at front of queue
# precondition: queue is not empty
if self.isEmpty():
print("Queue is empty. Abort operation!")
return ""
else:
return self._front.data

def __len__(self):
# returns number of items in queue
return self._size

def isEmpty(self):
return len(self) == 0

def __str__(self):
# items strung from front to rear
result = ""
probe = self._front
while probe != None:
result += str(probe.data) + ” “
probe = probe.next
return result

NOTE: no traversal needed for linked queue! ⇒ only use head/tail
⇒ cannot write “slower due to traversal” as disadvantage of linked list vs array for queue
NOTE: not having a queue length limit is an advantage, not disadvantage
If we want a limit, we can still set a limit by adding a new attribute to the Queue structure
Thus valid disadvantage for linked queue vs array include:
Linked list has a more complex implementation, while an array is much simpler
There is extra memory overhead in a linked list as extra memory is used for pointers

Queue implementation using array

Must access items at the logical beginning and logical end
Doing this in computationally effective manner is complex
We approach problem in a sequence of 3 attempts
First attempt
Fixes front of queue at position 0
rear variable points to last item at position n-1, where n = no. of items in queue
The enqueue operation is efficient for this implementation
But the dequeue operation entails shifting all but the 1st item in array to the left

class ArrayQueue:
# array-based queue implementation
DEFAULT_CAPACITY = 10 # class variable applies to all queues
def __init__(self):
self._items = [''] * ArrayQueue.DEFAULT_CAPACITY
self._rear = -1
self._size = 0
def enqueue(self, newItem):
# adds newItem to the rear of queue
# precondition: the queue is not full
if self._size == ArrayQueue.DEFAULT_CAPACITY:
print("Queue is full. Abort operation!")
else:
# newItem goes at logical end of array
self._rear += 1
self._size += 1
self._items[self._rear] = newItem
def dequeue(self):
# removes and returns the item at front of queue
# precondition: queue is not empty
if self.isEmpty():
print("Queue is empty. Abort operation!")
return ""
else:
oldItem = self._items[0]
for i in range(len(self) - 1):
self._items[i] = self._items[i+1]
self._rear -= 1
self._size -= 1
return oldItem

def peek(self):
# returns the item at front of queue
# precondition: queue is not empty
if self.isEmpty():
print("Queue is empty. Abort operation!")
return ""
else:
return self._items[0]

def __len__(self):
# returns no. of items in queue
return self._size

def isEmpty(self):
return len(self) == 0

def __str__(self):
# items strung from front to rear
result = ""
for i in range(len(self)):
result += str(self._items[i]) + ” “
return result

Second Attempt
Maintain a 2nd index (front) that points to item at front of queue
Starts at 0 and advances as items are dequeued
Cells to the left of the queue’s front pointer are unused until we shift all elements left, which we do whenever the rear pointer is about to run off the end
Third Attempt (main one to use!!)
Use a circular array implementation
rear starts at -1; front starts at 0
front chases rear pointer through the array
When a pointer is about to run off the end of the array, it is reset to 0
This has the effect of wrapping the queue around to the beginning of the array without the cost of moving any items
Detects when queue becomes full
Maintains a count of the items in the queue
When this count = size of array, queue is full

class ArrayQueue:
# array-based queue implementation (circular-queue)

DEFAULT_CAPACITY = 10 # class variable applies to all queues
def __init__(self):
self._items = [''] * ArrayQueue.DEFAULT_CAPACITY
self._rear = -1
self._front = 0
self._size = 0
def enqueue(self, newItem):
# adds newItem to rear of queue
# precondition queue is not full
if self._size == ArrayQueue.DEFAULT_CAPACITY:
print("Queue is full. Abort operation!")
else:
# end of array?
if self._rear == ArrayQueue.DEFAULT_CAPACITY - 1:
self._rear = 0
else:
self._rear += 1

self._items[self._rear] = newItem
self._size += 1
def dequeue(self):
# removes and returns item at front of queue
# precondition: queue is not empty
if self.isEmpty():
print("Queue is empty. Abort operation!")
return ""
else:
oldItem = self._items[self._front]
# end of array?
if self._front == ArrayQueue.DEFAULT_CAPACITY - 1:
self._front = 0
else:
self._front += 1

self._size -= 1
return oldItem

def peek(self):
# returns item at front of queue
# precondition: queue is not empty
if self.isEmpty():
print("Queue is empty. Abort operation!")
return ""
else:
return self._items[self._front]

def __len__(self):
# returns the no. of items in queue
return self._size

def isEmpty(self):
return len(self) == 0

def __str__(self):
# items strung from front to rear
result = ""
front = self._front
for i in range(self._size):
result += str(self._items[front]) + ” ”

if front == ArrayQueue.DEFAULT_CAPACITY - 1:
front = 0
else:
front += 1
return result

Chapter 8D

Tree

Each item can have multiple children
All items, except its privileged item (root), have exactly 1 parent

Node	An item stored in a tree
Root	Topmost node in a tree The only node without a parent
Child (“successor”)	A node immediately below and directly connected to a given node A node can have >1 child, and its children are viewed as organised in left-to-right order (leftmost child is 1st child; rightmost is last child)
Parent (“predecessor”)	A node immediately above and connected to a given node A node can only have 1 parent
Siblings	The children of a common parent
Leaf	A node that has no children

Interior node	A node that has at least 1 child
Edge / Branch / Link	Line that connects a parent to its child
Descendent	A node’s children, its children’s children, and so on, down to the leaves
Ancestor	A node’s parent, its parent’s parent, and so on, up to the root
Path	The sequence of edges that connects a node and one of its descendants
Path length	No. of edges in a path
Depth or level of a node	= length of the path connecting it to the root ⇒ root depth or level of the root is 0 ⇒ its children are at level 1, and so on
Height	Length of longest path in tree Max level number among leaves in the tree ⇒ Height of a tree containing 1 node = 0 ⇒ Height of an empty tree = -1
Subtree	The tree formed by considering a node and all its descendents

E.g.
E.g. a parse tree describes the syntactic structure of a particular sentence in terms of its parts
E.g. file system structures ⇒ directory are parents, files are children

Binary tree

Each node has at most 2 children (left & right child)
Recursive definition of binary trees: a binary tree is either empty or consists of a root plus a left subtree and a right subtree, each of which are binary trees
E.g. expression trees
Another way to process expressions is to build a parse tree during parsing
Is never empty
An interior node represents a compound expression, consisting of an operator and its operands
Each leaf node represents a numeric operand
Operands of higher precedence usually appear near bottom of tree, unless overridden in source expression by parentheses

Binary Search Trees (BST)

Sorted collection represented as tree-like structures
Each node in the left subtree of a given node is less than that node
Each node in the right subtree of a given node is greater than that node
Can support logarithmic searches and insertions
Its shape depends on its key values and their order of insertion
E.g. order of insertion:
Left subtree if alphabet is “smaller”, right if “larger”
Recursive BST Operations
BSTs can be implemented using left and right pointers at each node

class TreeNode: `def __init__(self, data):` `self.left = None` `self.data = data` `self.right = None` `class Tree:` `def __init__(self):` `self._root = None`

Counting no. of nodes in a BST (i.e. size of tree)

`def CountNodes(self, tree):` `if tree == None:` `return 0` `else:` `return self.CountNodes(tree.left) + self.CountNodes(tree.right) + 1`

Searching for item in BST
Return True if target item is in tree, else False

`def Search(self, tree, item):` `if tree == None:` `return False` `elif item < tree.data:` `return self.Search(tree.left, item)` `elif item > tree.data:` `return self.Search(tree.right, item)` `else: # item = tree.data` `return True`

Inserting an item into BST
Item’s proper place will be in either:
Root node, if tree is already empty
A node in current node’s left subtree, if new item < item in current node
A node in current node’s right subtree, if new item >= item in current node
Item is added as a leaf node

`def Insert(self, newValue, tree): # recursive` `if self._root == None: # insert into empty tree` `self._root = TreeNode(newValue)` `else:` `if newValue < tree.data:` `if tree.left == None:` `tree.left = TreeNode(newValue)` `else:` self.Insert(newValue, tree.left) `else: # newValue > tree.data` `if tree.right == None:` `tree.right = TreeNode(newValue)` `else:` self.Insert(newValue, tree.right)
`def Insert(self, newValue): # non-recursive` `if self.root == None: # for an empty tree` `self.root = TreeNode(newValue)` `return` `probe = self.root` `inserted = False` `while inserted == False:` `if (newValue < probe.data()):` `if (probe.left != None):` `probe = probe.left` `else:` `probe.left = TreeNode(newValue)` `inserted = True` `elif (newValue > probe.data):` `if (probe.right != None):` `probe = probe.right()` `else:` `probe.right = TreeNode(newValue)` `inserted = True`

def Insert(self, newValue, tree): # recursive
if self._root == None: # insert into empty tree
self._root = TreeNode(newValue)
else:
if newValue < tree.data:
if tree.left == None:
tree.left = TreeNode(newValue)
else:
self.Insert(newValue, tree.left)
else: # newValue > tree.data
if tree.right == None:
tree.right = TreeNode(newValue)
else:
self.Insert(newValue, tree.right)

def Insert(self, newValue): # non-recursive
if self.root == None: # for an empty tree
self.root = TreeNode(newValue)
return
probe = self.root
inserted = False
while inserted == False:
if (newValue < probe.data()):
if (probe.left != None):
probe = probe.left
else:
probe.left = TreeNode(newValue)
inserted = True
elif (newValue > probe.data):
if (probe.right != None):
probe = probe.right()
else:
probe.right = TreeNode(newValue)
inserted = True

Putting all nodes in a BST
(my) Way to rmb orders: imagine triangle, top level is root, bottom levels are left and right. Preorder: conductor’s gestures; Inorder: compress into 1 layer, read from left to right; Postorder: Start from bottom layer, then top layer (root)
Preorder traversal: visits root node, then traverses left & right subtree in similar way (root → left → right)

# prints the tree in Preorder `def Preorder(self, tree):` `if tree != None:` `print(tree.data)` self.Preorder(tree.left) self.Preorder(tree.right)

Inorder traversal: traverses left subtree, visits root node, & traverse right subtree
(Appropriate for visiting items in a BST in sorted order) (left → root → right)

`# prints tree in Inorder (ascending order)` `def Inorder(self, tree):` `if tree != None:` self.Inorder(tree.left) `print(tree.data)` self.Inorder(tree.right)
`# to get array of Nodes` `def inOrder(self, tree):` `res = []` `if tree is not None:` res.extend(self.inOrder(tree.left_ptr)) res.append(tree) res.extend(self.inOrder(tree.right_ptr)) `return res`
`# FOR OPPOSITE ORDER: (NOT postorder!)b` `def ReverseOrder(self, tree):` `if tree != None:` `# decreasing order from right to left` self.ReverseOrder(tree.right) `print(tree.value, end = ‘’)` self.ReverseOrder(tree.left) t.ReverseOrder(t.root)
(2025 TPE)

Postorder traversal: traverses left subtree, traverses right subtree, & visits root node (left → right → root)

# prints tree in Postorder `def Postorder(self, tree):` `if tree != None:` self.Postorder(tree.left) self.Postorder(tree.right) `print(tree.data)`

Removing an item from a BST (only understand concept, no need write algorithms/prog)

Deleting a Leaf Node	Set the parent’s reference to the node to be removed to None
Deleting a Node with 1 Child	Set the parent’s reference to the node to be removed to the node’s only child
Deleting a Node with 2 Children	Replace the data value of the node to be removed with the largest value in the left subtree and delete that value’s node from the left subtree (i.e. left subtree, rightmost child) OR right subtree, leftmost child

(NO NEED TO KNOW:)

`# Delete the node referenced to by tree` if tree.left and tree.right are None # case 1 set tree to None else if tree.left is None # case 2 set tree to tree.right else if tree.right is None # case 2 set tree to tree.left else # case 3 find predecessor set tree.data to predecessor.data delete predecessor

Array-based Implementation of Binary Trees

Difficult to define; practical only in some cases
Can be elegant or efficient
Elements are stored as nodes in the array
Each node comprises a left pointer, the data, and a right pointer
Pointers contain the array index of a node, which is stored in Root
-1 indicates a null pointer
Given an arbitrary item at position i in the array, it is easy to determine the location of related items

Item	Location
Parent	(i - 1) / 2
Left sibling (if there is one)	i - 1
Right sibling (if there is one)	i + 1
Left child (if there is one)	i * 2 + 1
Right child (if there is one)	i * 2 + 2

E.g.
Elements are stored by level in the array

Comments from the Word document

Comment by ANDREA TAN KAI XUAN HCI: doesnt IF in pseudocode not have ”:” ↩
Comment by ANDREA TAN KAI XUAN HCI: ? ↩
Comment by ANDREA TAN KAI XUAN HCI: use print statement? ↩
Comment by PUA JUN ZE, RYAN HCI: yes lah bro comment lah bro ↩
Comment by ANDREA TAN KAI XUAN HCI: need this? else unbound local error ↩
Comment by PUA JUN ZE, RYAN HCI: idk probably ↩
Comment by ANDREA TAN KAI XUAN HCI: else must write “if self.head == None: return “list is empty"" or smth like that ↩
Comment by PUA JUN ZE, RYAN HCI: yes lah ↩
Comment by ANDREA TAN KAI XUAN HCI: but isnt c still linked to f ↩
Comment by ANDREA TAN KAI XUAN HCI: need c.next = f.next? ↩
Comment by ANDREA TAN KAI XUAN HCI: no need manually link c back to m meh ↩

Quartz 5

Explorer

01 Chapter 8 - Data Structures

Chapter 8: Data Structures