CIS3355: Business Data Structures
Fall, 2008
 

A binary tree is a data structure that is split into nodes. The tree gets its name from the similarity it has with a family tree or what a tree looks like upside down. A binary tree is very useful as it can rapidly store data and rapidly retrieve stored data in a link list. A binary tree has leaves or nodes the main node is know as the root. The root then split up into branches and leaves. The branching of the tree is determined by hierarchy. The largest values are place to the right of the tree while the smaller values are to the right of the tree. Any values that follow the original parents are also set by order of highest number. The example below gives a good visual example.

 Typically a balanced tree is the best solution to a link list. An unbalanced tree tends not to be as sufficient as a balanced tree. Balance tree give a faster response when searching for the data or when inserting the data. Binary trees function as an algorithm which is constantly dividing the nodes. The algorithm or function looks for an available place on the tree where to insert the data. The function once the function finds an available space it determines in what order to place it. It usually places it by the level of hierarchy, at the same time the function creates a node or leaf. If the leaf were to be already taken then the function will keep checking to see where to place the data. The data is place in the available node by its key value. In order for the function to work this way it must be set to continuous searching.

Binary trees search time functions on log2n so an average time of search on a binary tree is log2n*2.

References: http://www.cs.usask.ca/resources/tutorials/csconcepts/2001_3/tutorials/introduction.html

http://www2.sis.pitt.edu/~peterb/0015-002/links.html