CSCI203 - Algorithms & Data Structures

What are the different tyoes of standard algorithms?

• Finding the Maximum

• Finding the Minimum

• Linear Search

• Binary Search

• Binary Search with test for termination

What are the different ways to compare algorithms or find the best algorithm to use?

• Fastest?

• Smallest?

• Most general?

• Easiest to understand?

How do we compare the speed of algorithms?

• Every operation takes time

• More operations = more time = slower algorithms

• Fewer operations = faster algorithm

• More operations = slower algorithm

What is Problem Size in algorithms?

• n = how many items the problem contains (number of items)

e.g.

• Sort 10 numbers is n = 10

• Sort 100 numbers is n = 100

What is Algorithm Complexity?

• Describes how the number of operations grow as the problem size (n) increases

• Measures the algorithm’s rate of growth not the exact running time

e.g.

• Small increase in work = better algorithm

• Large increase in work = less efficient

What are Complexity classes of algorithms and their types?

• Groups of algorithms that have approximately the same rate of growth as the problem size (n) increases

Types:

• Constant (1) = problem is independent of n

• Logarithmic (log n) = as n grows, the number of iterations to find the item grows slowly

• Linear (n) = as n grows, number of iterations grows at the same rate

• Linearathmic (nlog n) = time proportional to n

• Quadratic (n²) = number of iterations grows n * n

• Exponential (2^n)

• Factorial (n!)

What are Arrays?

• Fixed number of data items of the same type

• Directly accessible via an index value

• Can have more than one index (multidimensional)

• Initialising one takes n operations for an array of n elements

• Records may appear as an element

What are Lists?

• Collection of items arranged in some order

• Can’t be directlya accessed via an index

• Nodes (items) are recorded containing data and a pointer to the next node

• May also have a pointer to the previous

• Special pointers head and tail (for doubly linked lists) are maintained to point to the first and last elements

What are Stacks?

• Holds multiple elements of a single type

• Removed in reverse order of isnertion (Last In, First out)

• Implemented with an array and integer counter to indicate the current number of elements

What are Queues?

• Holds multiple elements of a single type

• Removed int he order in which they were inserted (First In, First Out)

• Can be implemented with an array and two integer counter to indicate the current start and next insertion positions

What are Records?

• Fixed number of items

• Elements may be of differing types and are named

• Array may appear as a field

• Addressed by a pointer

• Fields are accessible via the field name

What is a Compact String Storage?

• A way to store many strings of different lengths while using memory efficiently

Goals

• Uses the minimum amount of storage

• Allow fast access to any string

• Avoid the overhead of dynamic memory allocation

What are the advantages and disadvantages of using an Array of Strings for Compact String Storage?

Advantages:

• Uses the required amount of string storage

• Quick access

Disadvantages:

• Strings use dynamic memory

What are the advantages and disadvantages of using a 2D Character Array e.g. text[1..N, 1..L] for Compact String Storage?

Advnatages:

• Quick access

• Avoids dynamic memory

Disadvantages:

• N x L may use much more storge than actually required

What is a String Pool?

• A collection of data structures used to efficiently store a large number of strings of different lengths (variable-length strings)

• Stores many strings efficiently

• Different implementations have small differences but are about equally efficient

What is an Insertion Sort?

The strategy

• Starts with the second element in the list

• Insert it in the right place in the preceding list

• Repeat with the next unsorted element

• Keep going until we have placed the last element in the list

Characteristics

• Sorting n elements require n - 1 iterations

• In the worst case, each element may need comparison with every preceding element

• Total comparisons roughly equal n² / 2

• Worst-case time complexity: O(n²)

What is a Merge Sort?

The strategy

• Uses a second array to hold the sort results

• Works recursively by dividing the unsorted array into two parts and merging them.

• Divides all the way down before merging back up so the final result is a sorted array

Characteristics

• Operates on all n items in the array

• As each level divides the array in two, there are log n levels.

• Requires n * log n operations

What is a Heap?

• A complete binary tree (all levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible) with an additional property

Types:

• Max

• Min

Functions for management

• Siftup

• Siftdown

Operations

• Makeheap/Heapify

• We can store them in an array

  • Heap[1] is the root

  • Heap[2] and Heap[3] are the children of the root

  • Hence, Heap[i] has children Heap[2i] and Heap[2i+1] for root’s index is 1

What is a Max-heap?

The value in any node is less than or equal to the value in its parent node (except for the root node).

What is a Min-heap?

The value in any node is greater than or equal to the value in its parent node (except for the root node).

What is a Sift Up in Min-heap and what is its complexity?

• Insert a new leaf into the correct position

• Time complexity: log(n)

Strategy

• Add the new leaf at the end of the Heap to preserve the binary structure

• Compare it with its parent

• If it is smaller than its parent, swap them

• Keep swapping with the parent until it reaches the correct position (smaller numbers are above bigger numbers)

• Swaps happen along one branch only

• Number of swaps depends on the height of the heap

Hint: Add at the bottom → smaller value bubbles up

What is a Sift Up in Max-heap and what is its complexity?

• Insert a new leaf into the correct position

• Time complexity: log(n)

Strategy

• Add the new leaf at the end of the Heap to preserve the binary structure

• Compare it with its parent

• If it is larger than its parent, swap them (larger numbers are above smaller numbers)

• Swaps happen along one branch only

• Number of swaps depends on the height of the heap

Hint: Bigger values bubble up.

What is a Sift Down in Min-heap and its complexity?

• Insert a new root element into the correct position

• Time complexity: log(n)

• Move the last node to the root temporarily

• Compare it with its children

• If it is larger, swap it with the smaller child

• Keep comparing and swapping down until the heap property is restored

• Swaps occur along one branch only

Hint: Bigger value sinks down towards the smaller child.

What is a Sift Down in Max-Heap and its complexity?

• Insert a new root element into the correct position

• Time complexity: log(n)

• Move the last node to the root temporarily

• Compare it with its children

• If it is smaller than one of its children, swap it with the larger child

• Keep comparing and swapping down until the heap property is restored

• Swaps occur along one branch only

Hint: Smaller value sinks down towards the larger child.

How does Makeheap/Heapify work in Max-heap, and what is its complexity?

• Start at the last parent → Sift down → work back to the root

• Time complexity: n

The strategy

• Create a complete binary tree from the array

• Start from the first non-leaf node at index n/2 - 1

• Set the current element as the largest

• Apply Sift Down

• Repeat for each non-leaf node, moving back towards the root

• Each non-leaf element is progressively moved into its correct position

Hint: Picks bigger child

How does Makeheap/Heapify work in Min-heap, and what is its complexity

• Start at the last parent → Sift down → work back to the root

• Time complexity: n

The strategy

• Create a complete binary tree from the array

• Start from the first non-leaf node at index n/2 - 1

• Set the current element as the smallest

• Apply Sift Down

• Repeat for each non-leaf node, moving back towards the root

• Each non-leaf element is progressively moved into its correct position

Hint: Picks smaller child

What is Heapsort and its complexity?

• Uses the properties of a heap to sort an array

• Time complexity: n + (n-1) * log n

The strategy

• Convert the array into a heap (makeheap/heapify)

Repeatedly

• Swap the first and last elements

• Reduce the size of the heap by 1

• Restore the heap property of the smaller heap (siftdown)

Until the heap contains a single element

• Max-heap: sorts the list in asc order

• Min-hep sorts the list in desc order

What is Time Effiiciency in terms of Theoretical Analysis?

• It is determined by the number of repetitions of the basic operation as a function of input size

• Basic operation - the operation that contributes most towards the algorithm’s running time

What is Time Efficiency in terms of Empirical Analysis?

• Select a specific (typical) sample of inputs

• Use physical units of time (e.g. ms) or count actual number of basic operation’s executions

• Analyse the empirical data.

What is worst case in Time Efficiency?

Maximum number of basic operations over inputs of size n.

What is best case in Time Efficiency?

Minimum number of basic operations over inputs of size n.

What is average-case in Time Efficiency?

Depends on assumptions about the probability distribution of all possible inputs not simply/necessarily the average (exptected) of the best and worst cases

What is an exact formula for a basic operation count?

It gives the exact number of basic operations

C(n) = n(n-1) / 2

What is an order-of-growth formula with a specific multiplicative constant?

It shows the order of growth together with a known constant.

C(n) = 0.5^n

What is an order-of-growth formula with an unknown multiplicative constant?

It shows the order of growth using an unknown constant

C(n) = cn²

What is important about the order of growth in basic operations?

• Focuses on the order of growth within a constant multiple as n → ∞

• Helps determine how much longer a problem takes when the input size increases, such as when it doubles.

What is asymptotic order of growth?

A way of comparing functions that ignores constant factors and small input sizes.

What does t(n) ∈ O(g(n)) or Big-O notation mean in asymptotic order of growth?

• This is the class function t(n) that grows no faster than g(n) (upper bound).

• Related to the algorithm’s worst-case behaviour

• Small input sizes before n0 don’t matter

Hint: no faster than

What does t(n) ∈ Ω(g(n)) or Big-Omega notation mean in asymptotic order of growth?

• This is the class of function t(n) that grow at least as fast as g(n) (lower bound)

• Related to the algorithm’s best-case behaviour

• Small input sizes before n0 don’t matter.

Hint: at least as fast

What is Θ(g(n)) or Big-Theta in asymptotic order of growth and how is related to O and Ω?

• The others are loose bounds and this is a tighter bound

• It contains functions that grow at the same rate as g(n)

• Related to average or typical-case behaviour

Hint: squeezed between upper and lower bound → same growth rate

How can a limit be used to compare the order of growth (basic operations) of T(n) and g(n)?

• 0: order of growth of T(n) < order of growth of g(n)

  • Slowe

• c > 0 → order of growth of T(n) = order of growth of g(n)

  • Constant

• ∞: order of growth of T(n) > order of growth of g(n)

  • Faster

Examples compare:

• T(n) = 10n vs. g(n) = n²

• T(n) = n(n+1)/2 vs. g(n) = n²

What is L’Hôpital’s rule in the order of growth (basic operations)?

If the relevant limits of f(n) and g(n) are equal and derivatives f’ and g’ exist e.g. log n vs. n

What is Stirling’s formula in the order of growth (basic operations)?

What are basic asymptotic efficiency classes?

Growth	Class
(1)	Constant
(\log n)	Logarithmic
(n)	Linear
(n\log n)	(n)-log-(n) / linearithmic
(n^2)	Quadratic
(n^3)	Cubic
(2^n)	Exponential
(n!)	Factorial

What is a priority queue and how does it differ from a normal queue?

• It maintains a set of elements, each with an associated key.

• In this type of queue, the element with the largest key is always at the top, regardless of insertion rather than the elements being removed through the first-in-first-out order

• Uses include: OS scheduling, algorithms, Huffman’s algorithm and service for VIPs.

What are the basic operations of a priority queue?

• insert(pQueue, elt): insert an element and place it in the right position in the queue

• remove(pQueue, elt): extract and remove the element with top priority, then adjust the queue as needed

  • How the queue is adjusted depends on the implementation

How is insertion implemented in a naive priority queue, and what is its efficiency?

• Represent it as a linked list L

• Insert simply puts a new element onto the linked list

• The list does not need to bept in any order

• Time efficiency: Θ(1)

How is removal implemented in a naive priority queue, and what is its efficiency?

• Search through the linked list to find the maximum element

• Remove the maximum element and return it

• If the list contains n elements, the algorithm must iterate n times

• Time efficiency: Θ(n)

• Once the element is found, deleting it from a reasonably implemented linked list requires only Θ(1) work.

How does insertion work in a heap-based priority queue, and what is its efficiency?

• A max heap improves the priority queue implementation because it keeps the maximum in the first element

• Insert adds the new element and then restores the heap property

• Restoring the heap may move an element from a leaf up to the root

• Time efficiency: O(log n)

• This is slower than the other version which is: O(1)

How does removing the maximum element work in a heap-based priority queue, and what is its efficiency?

• Taking the first element takes O(1)

• The heap property is restored using siftDown(), which takes O(log n)

• Overall time efficiency: O(log n)

What is a simulation?

• The production of a computer model of something, esepcially for the purpose of study.

• 2 types: continuous and discrete

What is a Continuous Simulation?

• This is where time is broken into discrete chunks called ticks

• Usually used to model a continuous process whose state changes smoothly and continuously over time

• Often depends on complex mathematics and may require extreme computing resources i.e. supercomputers

• e.g. missile trajectory: differential equations model the missile’s continuous motion, including factors i.e. gravity and air resistance and then the simulation calculates its position and velocity at very small, fixed time intervals.

What is a Discrete Simulation?

• This is when time can take any value

• Usually used to model a system as a sequence of discrete events, where the system state changes when an event occurs

• Less mathematically complex and requires fewer computer resources

• e.g. bank operations: customers arrive and join a queue, tellers serve customers and customers leave after being served and then the simulation can help determine optimal queue lengths, the number of tellers needed, and resource allocation

How does a single-server queue simulation work?

• Customer arrives

  • If server is idle, teller serves immediately

  • If server is busy, join the end of the queue

• When service finishes, customer leaves and tell serves the next customer in the queue, if any

How does a single-server simulation decide what happens next?

• Compares the next arrival time and service-end time:

  • Next arrival first → process customer’s arrival

  • Service end earlier → process the service completion

• Then update the system and compare the next events again

What is the basic model for a single-queue multi-server simulation?

• One first-in-first-out (FIFO) queue feeds multiple identical servers at the same time

• 2 main events are: customer arrival and service completion

• When a customer arrives:

  • If a server is idle, the customer is served immediately by an idle server

  • If all servers are busy, the customer joins the FIFO queue

• When a server finishes:

  • If the queue is not empty, the server immediately serves the customer at the head of the queue

  • If the queue is empty, the server becomes idle

• The simulation moves from one event to the next and can tracks things i.e. waiting time, queue length and server utilisation

Why is a heap used to manage events in a multi-server simulation?

• A min-heap (priority queue) stores events according to their time, with the earliest event always at heap[0]

• This lets the simulation quickly determine what happens next i.e.:

  • A customer arrival or

  • A server completing service

• 2 approaches for tracking servers are:

  • Array using busy[i] and end_time[i]: tells us which server is doing what, but finding the next event takes O(n).

  • Heap of end times: keeps the smallest/earliest time on top, so finding what happens next takes O(log n), but by itself does not tell us which server the event belongs to

• To get both benefits, the heap can be used with a second id array:

  • id = 0 → the next event is a customer arrival

  • id > 0 → the next event is a service completion for that server

• Whenever a heap entry moves, its corresponding id entry must also move so the event time and event identity stay together

Key idea: the heap makes it efficient to answer the main question in an event-driven simulation: “Which event happens earliest?“

What is a binary tree and what are its main terms?

• This is a tree where each node has a max of 2 children: right child and left child.

• Root = top node

• Parent = node with a child

• Child = node below a parent

• Leaf = node with no children

• Subtree = a tree rooted at a node within the main tree

• Path = sequence of connected nodes

What are level, depth, height and key in a binary tree?

Level

• Represents the generation of a node

• Root = level 0

• Child of root = level 1

• Grandchild of root = level 2

Depth of a node:

• Length of the simple path from the root to that node

Height of a tree:

• Length of the longest simple path from the root to a leaf

Height of a node

• Maximum depth within the subtree rooted at that node

Key

• A node’s value sued for searching

What are the main ways to implement a binary tree?

• Array

  • tree = array of values

  • Root = tree[1]

  • Children of tree[i] = tree[2*i] and tree[2*i+1]

• Collection of dynamic records

  • Each node stores:

    • Contents

    • Pointer/reference to left child

    • Pointer/reference to right child

  • The tree stores a point/reference to the root

• Array of records

  • Each record stores:

    • Contents

    • Index of left child

    • Index of right child

What makes a binary tree a Binary Search Tree (BST)?

• This is a binary tree with an extra ordering rule.

• For every non-leaf node: left child’s value <= node’s value <= right child’s value

• e.g.

15

/ \

9 33

/ \ /

5 13 21

/

11

What are the basic operations performed on a Binary Search Tree?

• Insert → add an element/create a tree

• Find → search for an element

• Delete → remove an element

• Traversal → visit nodes in a particular order.

What are the type of traversals in Binary Search Trees?

• Preorder: root → left → right

  • Pre = root comes before the children

• Inorder: left → root → right

  • In = root is in between left and right children

• Postorder: left → right → root

  • Post = root comes after the children

How do you insert nodes when building a Binary Search Tree (BST)?

Nodes are added one at a time:

1. Search the existing BST for the value/key to insert

2. If the value is not found, create a new node

3. Compare the new value with the last valid node examined

4. Add the new node as the appropriate left or right child

The comparison determines which child to select

Special case — first node:

• Create the first node

• Make the root point to it

What is traversal in Binary Search Trees (BST)?

• This is the process of visiting all nodes of a tree

• It can be used to search/locate a key or print all values in the tree.

• Nodes are connected by edges/links so nodes cannot be randomly accessed and need to be accessed according to the traversal types (pre, in and post)

  • In-order traversal can list nodes in a sorted order (sorting)

What is In-Order traversal in Binary Search Trees?

What is Pre-Order traversal in Binary Search Trees?

What is Pre-Order traversal in Binary Search Trees?

Why can an ordinary Binary Search Tree become inefficient?

• The order that keys are inserted can create a severly unbalanced / skewed BST

  • e.g. inserting values in certain orders can make most nodes fall mainly to the left or right.

• BST has the operation complexity of Θ(logn) when the tree is balanced.

• So we want to adjust the BST as we operate on it to keep it more or less balanced.

What balance condition does an AVL Tree use?

• This type of tree is named after Adelson-Velsky and Landis

• The AVL balance rule is: “At every node, the heights of the left and right subtrees differ by at most 1“

  • So this is allowed: [height(left)−height(right)] ≤ 1

  • A tree is not AVL if even one node breaks this rule

How is the balance factor of an AVL node calculated?

Balance Factor = Height(left subtree) - height(right subtree)

• The height of an empty tree is defined as: -1

• For an AVL tree, every node’s balance factor must be : -1, 0 or 1

  • -1 = right side is one level higher

  • 0 = both sides have equal height

  • 1 = left side is one level higher

  • Any other value means the tree requires restructuring/balancing

What balancing operations can be used when an AVL tree becomes unbalanced?

• If the balance factor is outside -1, 0 or 1, the tree must be restructured using rotations.

• These balancing rotations are

  • Right rotations (RR)

  • Left rotation (LL)

  • Right-left double rotation (RL)

  • Left-right double rotation (LR)

What are the 4 ways an insertion can unbalance an AVL tree node β?

An insertion can occur in:

• Left subtree of β’s left child → Left-left case (LL)

• Right subtree of β → Left-right case (LR)

• Left subtree of β’s right child → Right-left case (RL)

• Right subtree of β’s right child → Right-right case (RR)

The cases are structurally related:

• Cases 1 and 4 are equivalent

• Cases 2 and 3 are equivalent

What is the basic process for building an AVL tree?

1. Initialise an AVL tree

2. Repeat for each key:

   1. Create a node from the key

   2. Insert the node into a tree

   3. Balance the tree through right, left, right-left, and left-right rotations

Simple flow:

• Create → Insert → Balance → Repeat

How can an algebraic expression be represented using a binary tree?

In an expression tree:

• Internal nodes = operatores i.e. +, -, *

• Leaf nodes = variables/values

How do you evaluate an expression in a Binary Search Tree using a stack?

1. Start with an empty stack

2. Process each symbol from left to right:

   1. If it is a letter/value → push it onto the stack

   2. If it is an operator

      1. Pop the top element as R

      2. Pop the next element as L

      3. Evaluate: L operator R

3. Push the result back onto the stack

4. Continue until the whole expression is processed

What is a Finite State Machine?

• This is a reactive system whose response to an input depends on its current state

• Its behaviour is described using:

  • A set of possible states

  • A set of possible inputs

  • The action/transition taken for a given input and current state

  • The new state entered

• This machine is useful for processing streams of data i.e. vending machines, traffic lights etc

• This is also called a finite-state automation

How is the behaviour of a system represented using a Finite State Machine?

• This describes the observable behaviour of a system as a sequence of states

• The current state can be determined from one or more state variables

  • e.g. states

    • q1 = waiting

    • q2 = reading

    • q3 = searching

    • q4 = writing

  • Possible sequence:

    • waiting → reading → searching → writing → waiting

      q1 q2 q3 q4 q1

• So these machines are special cases of automata (abstract machines)

• The states, inputs, actions and next states can also be represented using a table

What formally defines a Finite State Machine?

• Q = finite set of dates: {q0,q1,q2,…,qn​}

• F = subset of final/accepting states in Q

• q0 = the single start state in Q

• S = the input/output alphabet

• δ = the transition function: Q * S → Q

  • It maps: current state + current input → next state

What is a state table and how do you read it?

This type of table represents the complete behaviour of an FSM in table form

• Rows = current states

• Columns = inputs

• Each cell = the next state for that current state + input

• Φ / null = there is no transition

e.g.

Current state	Input a	Input b
q1	q2	q3
q2	q2	Φ
q3	Φ	Φ

e.g. (q1, a) → q2 and (q1, b) → q3

What is a 2-4/2-3-4 tree, and what node types can it contain?

• This tree is a balanced search tree (BST) where all leaf nodes are at the same level

• 3 node types:

  • 2-node: 1 key, 2 children

  • 3-node: 2 keys, 3 children

  • 4-node: 3 keys, 4 children

• A k-node has k-1 keys and if internal, k children

What ordering rules must a 2-4 tree follow/

• Keys inside each node are sorted smallest to largest

• Every internal node has one fewer key than children

• Each key lies conceptually between two consecutive children; values in the left subtree are smaller and values in the right subtree are larger

• This order means an in-order traversal produces they keys in sorted

How do you search a 2-4 tree?

• Compare the target value with the keys in the current node

  • If value = key, return its data

  • If value < key, search the subtree to the left of that key (recursively)

  • If value > key, compare the next key but if there’s no next key search the last/rightmost subtree and repeat until found or search ends

What are the basic steps for inserting into a 2-4 tree?

• Find the leaf where the item is to be inserted

• Insert the item

• Update/rebalance the node

  • Insertion into a 2-node becomes a 3-node

  • Insertion into a 3-node becomes 4-node

  • Insertion into a 4-node becomes 5-node which must be repaired

What happens if insertion makes the root a 5-node?

• Split the root and create a new root containing the median key of the old root

• This is the worst-case insertion scenario and increases the height of the tree by 1

How does deletion work in a 2-4 tree?

• Find the item

• If it is an internal node, swap it with its immediate in-order successor

  • Repeat until the item is in a leaf

• Delete it

• Update/rebelance the tree

  • 4-node becomes 3-node

  • 3-node becomes 2-node

  • 2-node becomes 1-node

How is a 1-node repaired after deletion?

• If an immediate sibling has more than 1 key, move a sibling key up to the parent and a parent key down into the 1-node

• Otherwise, remove the 1-node and move a parent key down into a sibling, which may make the parent a 1-node — repair recursively

• If the root becomes a 1-node, remove it

What is the efficiency of a 2-4 tree?

• Height = O(log n)

• Search = O(log n)

• Insertion = O(log n) because splitting is O(1) per level with at most log n splits

• Deletion = O(log n) because merging is O(1) per level with at most log n merges

What is a B-tree of order m, and what properties must it satisfy?

• A B-tree is an m-ary balance balanced search tree (BST) that generalises a 2-4 tree

  • Root: either a leaf or has at least 2 children

  • Other internal nodes: between ⌈m/2⌉ and m subtrees

  • Non-root nodes: between ⌈m/2⌉ - 1 and m - 1 keys

• All leaves are at the same level

Key idea: wide + shallow + balanced

How do you search a B-tree?

• Compare the target value with each key in the nodoe:

  • If value = key, return data

  • If value < key, recursively search the subtree left of that key

  • If value > key, compare the next key and if there is no next key, search the last subtree

Key idea: compare → choose child

How do you insert into a B-tree?

• Find the leaf where the item belongs

• Insert the item

  • If the node overflows and now has m keys, split it into 2 and move the mediak ney up to the parent

    • Repeat with the parent if necessary

    • Create a new root layer if neccessary

Key idea: leaf → overflow → split + median up

How do you delete from a B-tree?

• Find the key

  • If it is not in a leaf, swap/move it down to a leaf

• Delete it from the leaf

  • If the node underflows (now has [m/2] - 1 keys):

    • First try to borrow from a sibling with spare keys and adjust the parent

    • If no sibling has spare keys, merge with a sibling and reduce the parent’s key by 1

    • If the parent underflows, repeat the procedure upward

Key idea: leaf → underflow → borrow or merge

What is a B+ tree?

• In this type of tree, the actual data associated with keys is stored only in the leaf nodes

• Internal nodes contain copies of the first key of each child to guide searching

• In the image shown, nodes contain between 3 and 5 keys

Key data: data only in leaves

Why are B-trees useful for data stored on disk?

• Very large data may be too large to fit into memory, so only one node at a time may be loaded from disk

• Disk reads/writes are expensive, so we want as few as possible

• B-trees have a high branching factor, giving them a small height, so fewer nodes (and fewer disk accesses) are needed to travel from the root to a leaf.

Key idea: more children → smaller height → fewer disk reads

Why are B-trees useful in databases, and what does m = 100 show?

• Databases may contain millions or billions of disk-stored records

• B-trees allow access using a small number of disk reads, so they are commonly used as a database storage mechanism

• If m = 100 we can store in:

  • Level 1 = 100 records

  • Level 2 = 10,000 records

  • Level 3 = 1,000,000 records

What is a quadtree and how is it structured?

• This is a geometric/spatial data structure that is most often used to partition a 2D space.

• It is a 4-way tree: every internal node, including the root has exactly 4 children, usually representing 4 regions: NW, NE, SW, SE

Key idea: exactly 4 children

What do leaf nodes represent in a quadtree?

• This stores the information associated with the region/cell it represents

• The leaf contains the “interesting“ info about that particular area of the 2D space

Key idea: stores info about its region

What is a Region Quadtree?

• This type of quadtree recursively subdivides a 2D space into squares.

• The process continues where further subdivision is needed.

• Each leaf node stores info about the space/cell it represents

• This type of tree are often used in image processing

Key idea: recursively split into squares

What are quadtrees used for?

• Applications of geometric/spatial structures:

  • Computer graphics

  • Games and movies (mesh generation and 2D collision detection)

  • Computer vision

  • CAD

  • Street maps i.e. Google Maps/Earth

  • Image representation and processing

  • HCI design

  • Virtuality reality

  • Visualisation of complex functions

Key idea: spatial/image processing

What is a Point-Region (PR) Quadtree, and what node types does it use?

• This quadtree type leaf cells store the point that exists within that cell

• It uses 3 node types:

  • Point node: A leaf representing a point (point exists)

  • Empty node: A leaf representing a region containing no point

  • Region node: An internal node representing a region; it always has 4 children, which may be point, empty or region nodes (split into 4)