Special

Introducing the “Welcome to Xojo” Bundle!

New to Xojo and looking for guidance? We've put together a terrific bundle to welcome you! Xojo Bundle

This bundle includes six back issues of the magazine -- all of year 17 in printed book and digital formats -- plus a one-year subscription (beginning with 18.1) so you'll be learning all about Xojo for the next year. It's the perfect way to get started programming with Xojo. And you save as much as $35 over the non-bundle price!

This offer is only available for a limited time as supplies are limited, so hurry today and order this special bundle before the offer goes away!

Article Preview


Buy Now

Issue 3.2

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. The root 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 called leaves. 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.