Intermediate · 30 minYou are hereRead
Binary search trees
Smaller keys go left and larger keys right at every node, so a search or an insertion follows one path and costs the tree’s height.
Trees
Search trees
Members: · Free account
Lessons on this topic
Intermediate · 25 minYou are hereRead
Deleting from a binary search tree
A leaf is unlinked; a node with one child is replaced by it; a node with two children takes its successor’s key, and the successor is unlinked instead.
Intermediate · 30 minYou are hereRead
AVL trees and rotations
A rotation lifts a child above its parent by changing three pointers, without disturbing the order. An AVL tree rotates wherever two sibling subtrees differ in height by two, so it stays shallow.
Advanced · 30 minYou are hereRead
2-3 trees
Nodes hold one key or two. A node that would hold three splits and pushes its middle key up, so every leaf stays at the same depth and the tree grows only at the root.
Advanced · 30 minYou are hereRead
Red–black trees
Colour each node red or black, with no red node under a red one and the same number of black nodes on every path down, and the height stays below 2 log₂(n + 1). A red node is a key glued to its parent.
Intermediate · 30 minYou are hereRead
B-trees
A B-tree node holds many keys, sized to one disk block, so a tree three or four levels deep indexes a billion keys, and each level costs one read.
Intermediate · 25 minYou are hereRead
B+ trees
A B+ tree keeps every record in its leaves and links the leaves in order, so a range of keys costs one descent and a walk along the leaves.
Related topics