Tree

From Algorithmist
Jump to navigation Jump to search

A tree is a n-ary tree which is generally used to retrieval of things such as dictionaries.

Dictionary Example[edit]

Using the The tree starts out with a root node which points to the start letter nodes of the alphabet. If you add a new word, find the first letter of the node and keep adding node for that specific letter as you go down in the tree. Once you reach the end, tag the specific node you have reached to denote the path to this node is a word.

inserting in it and into

the tree after 'in' is inserted.
       ( )
       /
      i
       \
        n*

tree after 'it' is inserted
       ( )
       /
      i
     / \
    n*  t*
tree after 'into' is inserted
      (  )
       /
      i
     / \
    n*  t*
     \
      t
       \
        o*

If we do a inorder traversal on this tree and keep track of the nodes passed we can get an alphabetically sorted list of words.


related algorithms[edit]

Perhaps the most widely used kind of tree structure is the B tree (and small variations on the B tree). However, before ever mentioning the B tree, most teachers try to gradually build up to it using simpler structures: