Template talk:CS trees

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

"Trees used in computer graphics"[edit]

... there are much more typical uses for R-trees, in particular in geodata. Given that there is extra space, should we also link R*-tree, R+-tree? In particular, R*-trees are afaict usually preferred to a plain R-tree. --Chire2 (talk) 14:43, 11 May 2010 (UTC)


Should there be a link to "term" (imho, its best explanation is at First-order_logic#Terms, others are at Term (logic) and Term (mathematics)), a notion used in term rewriting, universal algebra, logic, etc.? It is, however, rather an application of the ordinary (non-binary) tree data-structure, rather than a particular data-structure by its own. I'm not quite sure about the scope of this template. Jochen Burghardt (talk) 17:27, 7 June 2013 (UTC)

Messy categorization[edit]

This template's listing of trees uses a rather strange categorization. First come the binary trees, which are actually all binary search trees. Then come the self-balancing BSTs, as if those aren't binary. Then the B-trees, which should really be grouped with the search trees since they too implement dynamic sets and maps on arbitrary ordered datatype.

But the strangest category is that of the "non-binary trees", which does not include the B-trees, but it does include the interval trees, which are really extended search trees: they can be BSTs or B-trees. The same goes for the order statistic tree, which is, however, listed under "other trees".

Finally, several heap data structures are listed, but the main ones aren't, even though all heaps are conceptually trees.

I suggest a reorganization in terms of use case rather than the current, ad-hoc organization:

  • Search trees (binary and B)
  • Tries (digital search trees)
  • Spatial partitioning trees (including the binary ones, and the k-d tree and ball tree should also be listed)
  • Heaps
  • Others/hybrids

Any objections? QVVERTYVS (hm?) 12:01, 18 January 2014 (UTC)