Tree structure

From DmWiki

In programming, a tree is a data structure containing nodes. At the top of the tree, a root node is defined. This node will have child nodes, which in turn will also have children. This results in a branch-like structure; hence the name "tree".

There are many different types of tree that can be used in programming. Some are listed below:

  • B-tree (http://en.wikipedia.org/wiki/B-tree)
  • Binary tree (http://en.wikipedia.org/wiki/Binary_search_tree)
  • KD-tree (http://en.wikipedia.org/wiki/Kd-tree)
  • Quadtree (http://en.wikipedia.org/wiki/Quadtree)
  • Octree (http://en.wikipedia.org/wiki/Octree)
  • trie

An interesting application of the binary tree data structure is the Binary Space Partition (http://en.wikipedia.org/wiki/Binary_space_partitioning) tree, used for a lot of different tasks in 3D graphics (for example: frustum culling, collision detection, sorting of transparent surfaces and so on).

Quadtree and Octree structures are also often used in the spatial partitioning area. For fast queries like (somewhat simplified): "where is this object, and who are its neighbours?".

This article is a stub. You can help improve the article by expanding it.


Retrieved from "http://www.devmaster.net/wiki/Tree_structure"
DevMaster navigation