Tag: trees

Quadtrees and k-d Trees:Space as a Tree Instead of a Nested Loop

Spatial trees split the plane so range and nearest-neighbor queries skip whole regions. Quadtrees cut into four boxes; k-d trees alternate axis splits.

Data Structures

Treaps:BST Order Plus Heap Priority

A treap is a BST on keys and a heap on random priorities. Rotations restore heap order so the shape stays balanced in expectation without color bits.

Data Structures

Splay Trees:Move What You Touch to the Root

A splay tree is a BST that rotates the accessed node to the root. Recently used keys get cheap; amortized O(log n) without storing balance factors.

Data Structures

Fenwick Trees:Prefix Updates When a Segment Tree Is More Tree Than You Need

A Fenwick tree (BIT) stores prefix aggregates in an array using least-significant-bit jumps. Point update and prefix query in O(log n) with less machinery than a segment tree.

Data Structures

Segment Trees:Range Queries Without Rescanning the Array

A segment tree stores aggregates of array ranges in a binary tree of intervals. Point update and range query in O(log n) without walking the whole slice each time.

Data Structures

Tries:Prefix Search Without Scanning Every String

A trie stores strings by shared prefixes. Autocomplete and dictionary lookup become a walk down characters — not a scan of every word.

Data Structures

B-Trees:Wide Nodes for Disk (and Why Databases Do Not Use BSTs)

A B-tree packs many keys per node so one disk page is one hop. Why databases and filesystems use this shape, and how B+ trees keep values in the leaves.

Data Structures

Red-Black Trees:The Shape Behind `TreeMap` and `TreeSet`

A red-black tree is a BST painted with color rules that keep height logarithmic without AVL’s strict balance. Why TreeMap and TreeSet use this shape.

Data Structures

AVL Trees:Height Balance When You Need Strict Guarantees

An AVL tree is a BST that rebalances on insert and delete so height stays O(log n). Balance factors, rotations, and when the extra strictness is worth it versus red-black.

Data Structures

Binary Search Trees:Ordered Trees That Go Lopsided Under Sorted Input

A BST keeps left < node < right so search is O(height). Why already-sorted inserts become a linked list, and what that does to the bill.

Data Structures

Binary Trees:Shape, Traversals, and What “Balanced” Even Means

A binary tree is a hierarchical layout: left, right, parent. Height vs size, preorder inorder postorder and level-order as operations of the shape, and what balanced actually promises.