View Source: BinaryTree - Waikato Linux Users Group

Edit PageHistory Diff Info LikePages

A binary tree is an efficient way of storing sorted data that will be frequently read/written.

The idea of a binary tree is that you have a "node" which contains some data and two pointers to more nodes, or NULL (called "Left" and "Right" respectively).  You have one node which is the "Root" of the tree.

When inserting data you start at the root, comparing against the data in the node, if the data is less than you go down the "left" branch, and if the data is greater you go down the right branch.  When you find a "NULL" you create a new node with Left and Right pointing to NULL, and the data pointing to the data you wanted to add.

When searching for data you do approximately the same thing, except if you find the data, you're done, if you find 'NULL' it doesn't exist at all.

A Binary tree that you insert data into randomly should have about O(log n) complexity for insert/delete.  See O(1) for more details.

Note, a BinaryTree will degrade into a LinkedList if you insert data into it in sorted order.  Doh.

There are specialisations on BinaryTree's such as RedBlackTree's, [BTree]'s, [AVLTree]'s, SplayTree's etc.  Lots of fun for the entire family.

2 pages link to BinaryTree:

Last edited on Wednesday, October 8, 2003 7:32:58 pm by StuartYeates

Edit PageHistory Diff Info LikePages