Binary Search Trees

From

(Difference between revisions)
Jump to: navigation, search
(Searching for an Element in a Binary Search Tree)
(Searching for an Element in a Binary Search Tree)
Line 6: Line 6:
Binary Search Tree Property: If '''N''' is a node in the tree, and '''N''' contains data '''D''', then all nodes in the left subtree of '''N''' contain data that is less than or equal to '''D''' and all nodes in the right subtree of '''N''' contain data that is greater than '''D'''.
Binary Search Tree Property: If '''N''' is a node in the tree, and '''N''' contains data '''D''', then all nodes in the left subtree of '''N''' contain data that is less than or equal to '''D''' and all nodes in the right subtree of '''N''' contain data that is greater than '''D'''.
</blockquote>
</blockquote>
 +
== Example Binary Search Tree ==
 +
...IMAGE HERE...
 +
<br/><br/>
 +
== Searching for an Element in a Binary Search Tree ==
== Searching for an Element in a Binary Search Tree ==
Suppose I want to know if a value X is in the tree. I can search for X using the following algorithm.
Suppose I want to know if a value X is in the tree. I can search for X using the following algorithm.

Revision as of 15:57, 28 March 2009

An important and frequently used specialization of a binary tree is a Binary Search Tree. A binary search tree contains data that is comparable, for example numbers or text, and has the following property:

Binary Search Tree Property: If N is a node in the tree, and N contains data D, then all nodes in the left subtree of N contain data that is less than or equal to D and all nodes in the right subtree of N contain data that is greater than D.

Contents

Example Binary Search Tree

...IMAGE HERE...

Searching for an Element in a Binary Search Tree

Suppose I want to know if a value X is in the tree. I can search for X using the following algorithm.

LET Found = false
LET P = the root of the tree
WHILE not Found and P is not NULL do
    IF P.Data equals X 
        set Found to TRUE
    ELSE IF P.Data < X 
        set P to P.right
    ELSE 
        set P to P.left
    ENDIF
ENDWHILE


Why is a search tree such a good organization for data? Suppose I have a list of names that are stored in a binary search tree and suppose there are 1,000,000 names in the tree. I am given a name, and I want to know if that name is in the list. What is the most number of checks I will have to make to determine if the name is in the list or not? At most, log2(1,000,000) = 20 checks will have to be made.

Inserting an Element into a Binary Search Tree

Removing an Element from a Binary Search Tree

This operation is a little more complex. First we must find the node to be removed. Let P be a node pointer that starts at the root and traverses the tree until it finds the node to be removed. We need to consider three cases.

First case: The node pointed to by P has no children. This means that P points to a leaf node and is easy to delete. We just set P’s parent pointer to null and we are done. Of course there is an implementation issue: If P points to the node to be deleted, how do we access the parent of P? One solution to is problem is to use a second pointer Q. When P traverses the tree looking for the node to be deleted, Q is set to P before moving P. In this way, Q always points to the parent of the node that P points to.

Second case: The node pointed to by P has one child. In this case, we just set P’s parent to point to P’s child.

Third case: P has two children. First find the node in the tree that is the next largest. To do this let T be a node pointer that is initialized to P’s right child. As long as T.Left is not null, let T = T.Left. Now swap the values in the nodes pointed to by P and T and delete the node pointed to by T.

Example In the tree above, with 21 and 44 added, remove 32 and 42.

One difficulty of a BST is that frequent insertions and deletions tend to make the tree out of balance. The search time for an out-of-balance BST degenerates to that of a linked list. Two approaches to this are AVL trees and Red-Black trees.

Personal tools
MediaWiki Appliance - Powered by TurnKey Linux