3 ms·

My current favourite balanced tree is the treap: http://en.wikipedia.org/wiki/Treap http://en.wikipedia.org/wiki/Treap In a treap the shape of the tree is uni

by ssp 17y ago

My current favourite balanced tree is the treap: http://en.wikipedia.org/wiki/Treap http://en.wikipedia.org/wiki/Treap In a treap the shape of the tree is uniquely determined by it being heap-ordered according to a random number associated with each node, in addition to the standard search tree ordering. The various operations are fast and simple to implement. For example, deletion is as simple as rotating the node in question down until it is a leaf, then removing it. The rotations only need to preserve heap ordering, a much simpler invariant than the red/black one. The standard description of the treap calls for a field in each node containing a random number, but you can eliminate that by just hashing the address of the node. That's what I did in GSequence in glib (http://git.gnome.org/browse/glib/tree/glib/gsequence.c http://git.gnome.org/browse/glib/tree/glib/gsequence.c).

sorbits 17y ago
For simplicity in implementation but guaranteed upper bounds I highly recommend AA-trees. WikiPedia: http://en.wikipedia.org/wiki/AA_tree http://en.wikipedia.org/wiki/AA_tree Original paper: http://user.it.uu.se/~arnea/ps/simp.pdf http://user.it.uu.se/~arnea/ps/simp.pdf Tutorial giving intuition for this data structure: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_t...
- shadytrees 17y ago
  Other cool balanced trees: rank-balanced trees [1], which have O(1) amortized insertion, deletion, and rebalancing, and ravl trees [2], which do not rebalance on deletion in hopes that insertions will happen soon and seem to rotate fewer times than both red-black trees and rank-balanced trees in experiments. [1]: http://www.cs.princeton.edu/~sssix/papers/rb-trees.pdf http://www.cs.princeton.edu/~sssix/papers/rb-trees.pdf (2009) [2]: http://www.cs.princeton.edu/~sssix/papers/ravl-trees.pdf http://www.cs.princeton.edu/~sssix/papers/ravl-trees.pdf (2010)

by ssp 17y ago

sorbits 17y ago

For simplicity in implementation but guaranteed upper bounds I highly recommend AA-trees. WikiPedia: http://en.wikipedia.org/wiki/AA_tree http://en.wikipedia.org/wiki/AA_tree Original paper: http://user.it.uu.se/~arnea/ps/simp.pdf http://user.it.uu.se/~arnea/ps/simp.pdf Tutorial giving intuition for this data structure: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_t...

shadytrees 17y ago
Other cool balanced trees: rank-balanced trees [1], which have O(1) amortized insertion, deletion, and rebalancing, and ravl trees [2], which do not rebalance on deletion in hopes that insertions will happen soon and seem to rotate fewer times than both red-black trees and rank-balanced trees in experiments. [1]: http://www.cs.princeton.edu/~sssix/papers/rb-trees.pdf http://www.cs.princeton.edu/~sssix/papers/rb-trees.pdf (2009) [2]: http://www.cs.princeton.edu/~sssix/papers/ravl-trees.pdf http://www.cs.princeton.edu/~sssix/papers/ravl-trees.pdf (2010)