2.1 Balanced Search Trees
AVL, red-black, splay, scapegoat, B-tree families, treaps, finger trees, persistent balanced trees, and cache-oblivious layouts.
2.1 Balanced search trees, 65
| index | slug | name |
|---|---|---|
| 1 | balanced-search-tree | Balanced Search Tree |
| 2 | avl-tree | AVL Tree |
| 3 | avl-insert | AVL Insert |
| 4 | avl-delete | AVL Delete |
| 5 | avl-rotation | AVL Rotation |
| 6 | avl-balance-factor | Balance Factor |
| 7 | red-black-tree | Red Black Tree |
| 8 | red-black-insert | Red Black Insert |
| 9 | red-black-delete | Red Black Delete |
| 10 | red-black-properties | Red Black Properties |
| 11 | aa-tree | AA Tree |
| 12 | aa-tree-skew | AA Tree Skew |
| 13 | aa-tree-split | AA Tree Split |
| 14 | treap | Treap |
| 15 | treap-insert | Treap Insert |
| 16 | treap-delete | Treap Delete |
| 17 | treap-split | Treap Split |
| 18 | treap-merge | Treap Merge |
| 19 | randomized-bst | Randomized BST |
| 20 | splay-tree | Splay Tree |
| 21 | splay-operation | Splay Operation |
| 22 | zig-rotation | Zig Rotation |
| 23 | zig-zig-rotation | Zig Zig Rotation |
| 24 | zig-zag-rotation | Zig Zag Rotation |
| 25 | scapegoat-tree | Scapegoat Tree |
| 26 | weight-balanced-tree | Weight Balanced Tree |
| 27 | size-balanced-tree | Size Balanced Tree |
| 28 | b-tree | B Tree |
| 29 | b-tree-search | B Tree Search |
| 30 | b-tree-insert | B Tree Insert |
| 31 | b-tree-delete | B Tree Delete |
| 32 | b-tree-split | B Tree Split |
| 33 | b-tree-merge | B Tree Merge |
| 34 | b-plus-tree | B Plus Tree |
| 35 | b-plus-tree-leaf-chain | Leaf Chain |
| 36 | b-star-tree | B Star Tree |
| 37 | two-three-tree | 2-3 Tree |
| 38 | two-three-four-tree | 2-3-4 Tree |
| 39 | finger-tree | Finger Tree |
| 40 | tango-tree | Tango Tree |
| 41 | rope-tree | Rope Tree |
| 42 | rope-split | Rope Split |
| 43 | rope-concat | Rope Concat |
| 44 | implicit-treap | Implicit Treap |
| 45 | implicit-treap-split | Implicit Treap Split |
| 46 | implicit-treap-merge | Implicit Treap Merge |
| 47 | order-maintenance-tree | Order Maintenance Tree |
| 48 | join-based-tree | Join Based Tree |
| 49 | split-join-tree | Split Join Tree |
| 50 | persistent-balanced-tree | Persistent Balanced Tree |
| 51 | concurrent-balanced-tree | Concurrent Balanced Tree |
| 52 | lock-free-balanced-tree | Lock Free Balanced Tree |
| 53 | cache-oblivious-b-tree | Cache Oblivious B Tree |
| 54 | packed-memory-array | Packed Memory Array |
| 55 | van-emde-boas-tree | Van Emde Boas Tree |
| 56 | y-fast-trie | Y Fast Trie |
| 57 | x-fast-trie | X Fast Trie |
| 58 | red-black-invariant-check | Red Black Invariant Check |
| 59 | avl-invariant-check | AVL Invariant Check |
| 60 | b-tree-invariant-check | B Tree Invariant Check |
| 61 | tree-rotation-analysis | Rotation Analysis |
| 62 | tree-height-bound | Height Bound |
| 63 | tree-amortized-analysis | Amortized Analysis |
| 64 | tree-cache-layout | Cache Layout |
| 65 | tree-benchmarking | Tree Benchmarking |