What is Binary Tree?

A binary tree is a method of placing and locating files (called records or keys) in a database, especially when all the data is known to be in random access memory (RAM). The algorithm finds data by repeatedly dividing the number of ultimately accessible records in half until only one remains.

In a tree, records are stored in locations called leaves. This name derives from the fact that records always exist at end points; there is nothing beyond them. Branch points are called nodes. The order of a tree is the number of branches (called children) per node. In a binary tree, there are always two children per node, so the order is 2. The number of leaves in a binary tree is always a power of 2. The number of access operations required to reach the desired record is called the depth of the tree. The image to the left shows a binary tree for locating a particular record among seven records in a set of eight leaves. The depth of this tree is 4.

In a practical tree, there can be thousands, millions, or billions of records. Not all leaves necessarily contain a record, but more than half do. A leaf that does not contain a record is called a null. In the example shown here, the eighth leaf is a null, indicated by an open circle.

Binary trees are used when all the data is in random-access memory (RAM). The search algorithm is simple, but it does not minimize the number of database accesses required to reach a desired record. When the entire tree is contained in RAM, which is a fast-read, fast-write medium, the number of required accesses is of little concern. But when some or all of the data is on disk, which is slow-read, slow-write, it is advantageous to minimize the number of accesses (the tree depth). Alternative algorithms such as the B-tree accomplish this.

Also see binary search and tree structure. Compare B-tree, M-tree, splay tree, and X-tree.