Trees, Binary Search Trees and Balanced Trees: every key term you need (+ practice quiz)
25 flashcard terms for Data Structures & Algorithms Topic 6, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
A connected acyclic structure with one distinguished root, where every other node has exactly one parent. A tree on n nodes always has exactly n minus one edges.
Tree height
The number of edges on the longest root-to-leaf path. Search cost in a tree is proportional to height, which is why balancing schemes exist to keep it logarithmic.
Binary tree
A tree where each node has at most a left and a right child. The shape is part of the data, so the same key set can form many different binary trees.
Complete binary tree
A binary tree filled level by level from the left with no gaps except possibly at the end of the last level. This shape lets a tree be packed into an array with no pointers.
Full binary tree
A binary tree in which every node has either zero or two children. Such a tree with i internal nodes has exactly i plus one leaves, a fact used in coding-tree proofs.
In-order traversal
Visits the left subtree, the node, then the right subtree. On a binary search tree it emits keys in sorted order, which is the standard way to verify the search property.
Pre-order traversal
Visits the node before its subtrees, producing a sequence that can rebuild the tree shape when paired with a second order or with explicit null markers.
Post-order traversal
Visits both subtrees before the node, the right order for freeing memory, computing subtree sizes, or evaluating an expression tree bottom up.
Level-order traversal
Visits nodes by increasing depth using a queue, giving breadth-first order. It is the natural way to print a tree by rows or to find the shallowest matching node.
Search tree property
Every key in a node's left subtree is smaller and every key in its right subtree is larger. This invariant is what makes a single downward path sufficient for lookup.
Search tree lookup
Compares the target with the current key and descends one side, costing O(h) time. That is O(log n) when balanced but degrades to O(n) in a stringy tree.
Search tree insertion
Descends as a failed lookup would and attaches the new key at the empty position reached. It preserves the ordering invariant but may worsen the height.
Two-child deletion
Removing a node with both children by replacing its key with its in-order successor, then deleting that successor, which has at most one child and is therefore easy to splice out.
In-order successor
The next larger key, found as the leftmost node of the right subtree or otherwise as the nearest ancestor whose left subtree contains the node.
Degenerate search tree
A tree whose insertions arrived in sorted order, producing a chain of height n minus one. Every operation costs linear time, which motivates self-balancing designs.
Tree rotation
A constant-time local restructuring that shifts a child up and its parent down while preserving the ordering invariant. It is the primitive used by every balancing scheme.
AVL tree
A search tree keeping the height difference of any node's subtrees within one. It stays tightly balanced with fast lookups, at the cost of more rebalancing work on updates.
Balance factor
The height of a node's right subtree minus that of its left. Values outside the range from minus one to one trigger one or two rotations to restore the invariant.
Red-black tree
A search tree colouring nodes red or black so that no root-to-leaf path exceeds twice the length of another, giving O(log n) operations with fewer rotations than a stricter scheme.
Red-black invariants
The root and leaves count as black, a red node never has a red child, and every path from a node to its descendant leaves contains the same number of black nodes.
Splay tree
A self-adjusting tree that rotates each accessed node to the root, giving O(log n) amortized cost per operation and excellent behaviour on skewed access patterns.
Treap
A structure keeping search order on keys and heap order on random priorities, so the shape matches a randomly built tree and expected height is logarithmic.
B-tree
A wide branching search tree where each node holds many keys and children, chosen so a node fills a disk block. Height stays tiny, which minimises expensive block reads.
Trie
A prefix tree where the path from the root spells the key, so lookup costs time proportional to key length rather than to the number of stored keys.
Lowest common ancestor
The deepest node having two given nodes as descendants. In a search tree it is the first node whose key lies between the two targets on the downward walk.