Check out my first novel, midnight's simulacra!

Trees: Difference between revisions

From dankwiki
No edit summary
(16 intermediate revisions by the same user not shown)
Line 3: Line 3:
* AVL (Adelson-Velsky + Landis)
* AVL (Adelson-Velsky + Landis)
* pq
* pq
* [https://lwn.net/Articles/845507/ maple]
* top
* top
* fat
* fat
Line 11: Line 12:
* splay
* splay
* trie
* trie
* up-sweep (Blelloch 1990)
* kd
* kd
* (minimal) spanning
* (minimal) spanning
* [[Gomory-Hu Tree|Gomory-Hu]]
* decision
* Hilbert R
* game
* aa
* finger
* Trémaux
* Steiner
* Order statistic
* [https://en.wikipedia.org/wiki/Log-structured_merge-tree LSM] (log-structured merge)
* [https://en.wikipedia.org/wiki/Cartesian_tree Cartesian]
==[[Compiler Design|Compiling]]==
==[[Compiler Design|Compiling]]==
* abstract syntax
* abstract syntax
* doubly logarithmic
* dominator
* dominator
...
...
==Theory==
* Finite/Pushdown [[automata#Tree_automata|Tree Automata]]
* Algebraic tree systems

Revision as of 04:23, 22 August 2021

Trees? We've got all the trees you need! I'm thinking about writing a pop computer science book, one chapter on each of these.

  • red-black
  • AVL (Adelson-Velsky + Landis)
  • pq
  • maple
  • top
  • fat
  • b / b+ / 2-3
  • vEB (van Emde Boas)
  • radix
  • dancing
  • splay
  • trie
  • up-sweep (Blelloch 1990)
  • kd
  • (minimal) spanning
  • Gomory-Hu
  • decision
  • Hilbert R
  • game
  • aa
  • finger
  • Trémaux
  • Steiner
  • Order statistic
  • LSM (log-structured merge)
  • Cartesian

Compiling

  • abstract syntax
  • doubly logarithmic
  • dominator

...

Theory