Glossary

23 terms that recur across the curriculum. Skim before starting; refer back as needed.

amortized

Average cost over many operations

Some operations are expensive but rare. Dynamic array resize is O(n), but happens so rarely that the average insert is still O(1) amortized.

balance factor

Height difference between subtrees

In AVL trees: balance_factor = height(left) - height(right). Must be -1, 0, or 1 for every node. Violations trigger rotations to restore balance.

Big O

Upper bound on algorithm complexity

Describes worst-case growth rate. O(n) means time grows linearly with input size. O(1) is constant time, O(log n) is logarithmic, O(n^2) is quadratic.

chaining

Collision resolution using linked lists

Each hash table bucket stores a linked list. Colliding keys are added to the list. Simple but uses extra memory for pointers.

collision

Multiple keys mapping to same bucket

Hash tables use a hash function to map keys to array indices. When two different keys hash to the same index, we have a collision that must be resolved.

contiguous

Adjacent memory locations

Arrays store elements contiguously - one after another in memory. This enables O(1) index access but makes insertion expensive (must shift elements).

dynamic allocation

Memory allocated at runtime

Unlike fixed-size arrays, linked structures grow by allocating new nodes as needed. More flexible but adds overhead for memory management.

edge

Connection between nodes

In graphs, edges connect vertices (nodes). Can be directed (one-way) or undirected (two-way). May have weights representing distance, cost, etc.

head

First element of a list

The entry point to a linked list. All operations start from the head and follow pointers to find other elements.

height

Longest path from root to leaf

Determines tree efficiency. Balanced trees maintain O(log n) height. Unbalanced trees can degrade to O(n) height, losing their advantage over lists.

leaf

Node with no children

Terminal nodes at the bottom of a tree. In a binary tree, a leaf has no left or right child. Leaves are where most data operations terminate.

load factor

Ratio of items to buckets in a hash table

load_factor = n / capacity. Higher load factor means more collisions. Typically resize when load factor exceeds 0.7 to maintain O(1) performance.

node

Basic unit containing data and references

In linked structures, a node holds the actual data plus pointers to other nodes. A linked list node has data + next pointer. A tree node has data + child pointers.

O(1)

Constant time - independent of input size

The holy grail of efficiency. Array index access and hash table lookup (average) are O(1). The operation takes the same time whether you have 10 or 10 million items.

O(log n)

Logarithmic time - halves problem each step

Binary search, balanced tree operations. Incredibly efficient - searching 1 billion items takes only ~30 steps. The result of divide-and-conquer strategies.

O(n)

Linear time - grows with input size

Searching an unsorted list, traversing all elements. If you double the input, you double the time. Still efficient for most practical purposes.

pointer

Memory address reference to another location

Instead of storing data directly, store its address. Enables linked structures where elements can be anywhere in memory. Fundamental to dynamic data structures.

probing

Collision resolution by searching for empty slots

On collision, search for the next available slot (linear, quadratic, or double hashing). No extra memory, but can suffer from clustering.

root

Top node of a tree

The starting point for tree traversal. Unlike lists, trees branch out from the root to multiple children, creating a hierarchical structure.

rotation

Tree rebalancing operation

Restructures a tree to maintain balance without changing the ordering property. Left and right rotations are the building blocks of AVL and Red-Black trees.

tail

Last element of a list

The final node in a linked list (its next pointer is null). Some implementations keep a tail pointer for O(1) append operations.

traversal

Visiting all nodes in a structure

Different orders reveal different information. In-order gives sorted sequence, pre-order for serialization, post-order for deletion, level-order for BFS.

vertex

Node in a graph

A point in a graph, connected to other vertices via edges. Can represent cities, web pages, people, states - any entity with relationships.