Robert Maclean has a couple of posts on binary trees. In the first post, he explains the basics of a binary tree:
As a binary tree has some flexibility in it, a number of classifications have come up to have a consistent way to discuss a binary tree. Common classifications are:
- Full binary tree: Each node in a binary tree can have zero, one, or two child nodes. In a fullbinary tree, each node can only have zero or two child nodes.
- Perfect binary tree: This is a full binary tree with the additional condition that all leaf nodes (i.e. nodes with no children) are at the same level/depth.
- Complete binary tree: The complete binary tree is where each leaf node is as far left as possible.
- Balanced binary tree: A balanced binary tree is a tree where the height of the tree is as small a number as possible.
Then, he looks at binary search trees:
So, why should we care about a BST? We should care because searching is really performant in it as each time you move a depth down, you eliminate approximately 50% of the potential nodes.
So, for example, if we wanted to find the item in our example with the key 66, we could start at the root (50) and move right. At that point, we have eliminated 8 possible nodes immediately. The next is to the left from the node with the 70 (total possible nodes removed 12). Next is to the right of the node with the value of 65, and then to 66 to the left of 67. So we found the node with 5 steps.
Going to Big O Notation, this means we achieved a performance of close to O(log n). It is possible to have a worst case of O(n), when the tree is not Optimal or Unbalanced.
Binary search trees are an easy to understand, reasonably efficient model for searching for data. Even when there are better options, this is an easy algorithm to implement and can often be good enough to solve the problem.