tree

Articles

SRT Algorithm Heapsort A heap right in the array: n log n in the worst case with no extra memory, the insurance of introsort and the Linux kernel's sort. O(n log n) 2 problems DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems DS Data structure Binary search tree Smaller to the left, larger to the right: search, order and the k-th element in the tree's height, from log n to n. O(h): from O(log n) to O(n) 2 problems DS Data structure AVL tree A search tree where the branch heights at a node differ by at most 1: height up to ~1.44·log₂ n. O(log n) for search, insertion and deletion 2 problems DS Data structure B-tree A tree with hundreds of keys in a page-sized node: a search among a billion keys reads five pages. O(log n) comparisons, O(log_B n) page reads 2 problems DS Data structure Disjoint set union Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks. O(α(n)) 2 problems GRA Algorithm Heavy paths Path queries on trees: heavy paths cut any path into O(log n) array stretches under a segment tree. O(log² n) per query 1 problem GRA Algorithm Centroid decomposition Splitting a tree by centroids: log₂ n levels, and the nearest marked vertex in O(log n) after every mark. O(log n) per mark and per question 1 problem STR Data structure BK-tree All passwords one or two edits from a given one: the triangle inequality cuts off whole branches, and where it stops helping. O(N · depth) to build 1 problem STR Algorithm Huffman code The optimal prefix code for character frequencies: the two rarest trees are glued together until one is left. O(n log n) 2 problems ML Algorithm Decision tree Answers with a chain of questions “feature ≤ threshold?”; each question is chosen so that uncertainty falls the most. O(h · F · n log n) to build; O(h) to answer 2 problems

Problems

Rotations on the conveyor The best first question The floors of an index A password's neighbours A tree by Gini Decoding from code lengths How many pages has the index The quadtree of a photo Two swapped keys Where the k-th can lie A described relative Flood watch Loading in order The height without the tree

Often together

classic 8 interviews 6 science and physics 5 in production 4 range queries 4 heap 3 array 3 operating systems 3 search tree 3 searching 3 databases 2 graph 2