Trees (OCR A-Level Computer Science): Flashcards

Hierarchical structure consisting of nodes

Topmost node in tree

Node with no children

Each node has at most two children (left and right)

Left child < parent, right child > parent

$O(\log n)$

$2*i + 1$

$2*i + 2$

Left subtree → Right subtree → Root

Level by level, left to right

Start at root, traverse left if smaller/right if larger, insert at leaf

Remove it directly

Replace it with its child

Replace with in-order successor (smallest in right subtree)

Degrades to $O(n)$