See also: Tree | Data structure | Programming | Huffman Encoding
A type of structure used by programmers to efficiently search for a specific piece of data out of a larger set of data.
In programming, a type of tree data structure in which each node has zero, one, or two children (subtrees). A balanced binary tree has efficency O = log(N).
The nodes of the binary tree are ordered on some property of the data in each node. Given any node, nodes that are “smaller” than it are to one side, and nodes that are “larger” are to the other. “Smaller” and “larger” are relative to the type of data being stored, while the side each goes on is dependent upon implementation.
The power of a binary tree is that searching it is very fast. With each comparison, approximately half of the potential data set is eliminated from consideration. For example, if we have letters in a tree, and the root is ‘k’, and we are searching for ‘d’, our first comparison (comparing ‘d’ to ‘k’ and finding that ‘d’ is “smaller” than ‘k’) will tell us that we need not consider any of the children to the right of ‘k’.
Binary trees are susceptible to becoming imbalanced. This is often the case when creating a tree from previously sorted data. Imagine inserting a, b, c, … , x, y, z as above. Since ‘a’ is the first character insterted, it would become the root node. Every letter from there on out would be to the right of it (and the same goes for every consecutive character inserted). The result of this insert would essentially be a Linked List.
Contents
Operations
Some pseudo-C pseudo-code for normal binary tree operations.
- each node has a “value” and pointers for “left” and “right”
- nodes without children have “left” and “right” values equal to null
- left is “smaller,” while right is “larger”
Search
<pre>/* search for searchvalue in a binary tree
- return true if we find searchvalue in the tree, false otherwise
- /
searchvalue = the value we are searching forcurrentnode = root
while(currentnode != null) {
if(currentnode.value = searchvalue)
break
if(searchvalue > currentnode.value)
currentnode = currentnode.right
else
currentnode = currentnode.left}
if(currentvalue != null)
return trueelse
return false</pre>
Insert
TODO
Delete
TODO
Example
Taking alphabetic characters as our data set, let “smaller” mean closer to the beginning of the alphabet, and “larger” mean closer to the end. Let “smaller” be to the left, and “larger” be to the right in the tree.
TakeDown.NET -> “Binary-Tree”