Article Preview
Buy Now
COLUMN
Binary Trees
A general-purpose searching tool
Issue: 3.2 (November/December 2004)
Author: Thomas Reed
Author Bio: Thomas Reed has been programming as a hobbyist for more than 20 years, and fell in love with the Mac in 1984.
Article Description: No description available.
Article Length (in bytes): 8,376
Starting Page Number: 34
Article Number: 3216
Related Link(s): None
Excerpt of article text...
In issue 1.3, Matt Neuburg covered one specific application of the binary tree in a discussion of the heap sort algorithm. In this issue, I will talk about the binary tree as a search algorithm. A binary tree can be used for searching a set of any kind of objects, provided it makes sense to talk about one object being greater than or less than another.
Let's start with a re-definition of the binary tree. A tree consists of a series of
nodes . A node represents a point where the tree branches. Every node has exactly one parent and may have many children, with one exception. Theroot of the tree is the only node having no parent, and is usually drawn at the top of the tree. The nodes found at the bottom of the tree, having no children, are calledleaves . An example of a tree can be found in Figure 1.All trees have a property called
depth , or height, which is defined simply as the number of nodes between the root and the deepest (or highest) leaf. The tree in Figure 1 would commonly be referred to as having a depth of 2, with the root at depth 0.A
binary tree is a specific kind of tree, in which each node may have a maximum of two children: a left child and a right child. You will notice that the tree in Figure 1 is also an example of a binary tree. No node has more than 2 children.A
binary search tree is a binary tree in which the nodes have a special ordering. The left descendents of any given node have a smaller value than the node, while the right descendents are larger. This makes finding a particular value easy. Simply begin examining nodes, beginning with the root node. If the node's value is less than the desired value, examine the node's left child, and if the value is greater, examine the right child. Continue until a matching node is found.Inserting new values in a binary search tree is similarly easy. To insert, you must traverse the tree in the same manner as you would when searching. When a node is reached that lacks a child in the direction you need to descend, a new node containing the value is inserted as that child. You must decide what to do, however, when the value being inserted is already present in the tree. You could cause the insertion to fail in this case, or perhaps you might store multiple identical values in the same node.
...End of Excerpt. Please purchase the magazine to read the full article.