Trees

Reporter: What is a tree?
Layman: A tree is a perennial woody plant growing on the ground that has a main stem, many branches from the stem and leaves.
Reporter: What is a tree?
Mathematician: A tree is a connected undirected acyclic graph.
Reporter: What is a tree?
Computer Engineer: A tree is a data structure used to organize the data (numbers, strings etc) in a tree format so as to make the data insertion or deletion or search faster.

Yes. This post is not about the trees of Nature, but, about the trees of Computer Science. I would like to give a comprehensive list of different concepts of trees, different types of trees and different applications of trees.

Applications of Trees
Trees are one of the most useful data structures in Computer Science. Some of the common applications of trees are:

  1. The library database in a library, a student database in a school or college, an employee database in a company, a patient database in a hospital or any database for that matter would be implemented using trees.
  2. The file system in your computer i.e folders and all files, would be stored as a tree.
  3. When you search for a word in a file or misspell a word and you get a list of possible correct words, you are using a tree. Because, the file would be indexed as a tree and for the same reason you get answers instantly.
  4. When you watch a youtube video or surf anything on the internet, the data which would be present in a computer somewhere in the world would travel to your computer passing through many intermediate computers called routers. The routers heavily use trees for routing.
  5. Most probably, Google maps uses trees (apart from using graphs) for all the locations in it. Then it would be very easy to answer questions like
    a) which is the nearest restaurant to this place?
    b) list all schools which are present within 5  miles of radius from this place
    c) and so on

Types of Trees
People come up with different concepts and different types of trees so that they can be made use for a variety of applications. If you are not a technical person, I recommend you to know at least one tree (say binary search trees). If you are a technical person but not a Computer Science person, I recommend you to know at least three trees (say binary search trees, B trees and suffix trees). If you are a Computer Science person, I recommend you to know all known trees.

  1. 2-3 heap
  2. 2-3 trees
  3. 2-3-4 trees
  4. (a-b) trees
  5. AA trees
  6. Abstract syntax trees
  7. Adaptive k-d trees
  8. Additive trees
  9. And-or trees
  10. AVL trees
  11. Alternating decision trees
  12. B trees
  13. B+ trees
  14. B* trees
  15. B# trees
  16. bb-a trees
  17. Balanced trees
  18. Banana trees
  19. Beap
  20. Binary heap
  21. Binary search trees
  22. Binary trees
  23. Binomial heap
  24. BK trees
  25. BSP trees
  26. Buffer trees
  27. Buffered repository trees
  28. Bx trees
  29. Cartesian trees
  30. Caterpillar
  31. Cayley trees
  32. Centipede
  33. Claw graph
  34. Cover trees
  35. Ctrie
  36. Dancing trees
  37. D-ary heap
  38. Decision trees
  39. Enfilade
  40. Expectiminimax trees
  41. Exponential trees
  42. Fenwick trees
  43. Fibonacci heap
  44. Finger trees
  45. Fractal trees
  46. Fusion trees
  47. Gomory Hu trees
  48. Hash / merkle trees
  49. Heap
  50. Hilbert R trees
  51. Implicit k-d trees
  52. Interval trees
  53. K trees
  54. K+ trees
  55. k-ary  trees
  56. K-d trees
  57. Kdb tres
  58. Leftlist heap
  59. Linear octrees
  60. Link / cut trees
  61. Lobster
  62. M trees
  63. Metric trees
  64. Min / max k-d trees
  65. Minimax trees
  66. Minimum spanning trees
  67. Octrees
  68. Pagoda
  69. Pairing heap
  70. Parse trees
  71. Prefix trees / tries
  72. Prefix hash trees
  73. Phylogenetic /evolutionary trees
  74. Qd trees
  75. Quadtrees
  76. Queap
  77. R trees
  78. R+ trees
  79. R* trees
  80. Range trees
  81. Radix trees
  82. Randomized binary search trees
  83. Rapidly exploring random trees
  84. Red black trees
  85. Rope
  86. Scapegoat trees
  87. Segment trees
  88. Self balancing binary search trees
  89. SKD trees
  90. Skew heap
  91. Soft heap
  92. Spaghetti stack / in-tree
  93. Spider
  94. Splay trees
  95. SPQR trees
  96. Star graph
  97. Steiner trees
  98. Succinct suffix trees
  99. Suffix trees
  100. Syntax trees
  101. T trees
  102. Tango trees
  103. Ternary heap
  104. Ternary search trees
  105. Thin heap
  106. Threaded binary trees
  107. Top trees
  108. Treap
  109. TV trees
  110. UB trees
  111. Ultrametric trees
  112. Van Emde Boas trees
  113. VP trees
  114. Weight balanced B trees
  115. Weight balanced trees
  116. Weighted binary trees
  117. X trees
  118. X-fast trie
  119. Y trees
  120. Y-fast trees
  121. Y-fast trie

Enjoy. :)

Follow

Get every new post delivered to your Inbox.

Join 48 other followers

%d bloggers like this: