Binary Search Trees
From
(→Removing an Element from a Binary Search Tree) |
|||
| Line 11: | Line 11: | ||
== Removing an Element from 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. | ||
| + | <br/><br/> | ||
| + | |||
| + | 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. | ||
| + | <br/><br/> | ||
| + | |||
| + | 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. | ||
| + | <br/><br/> | ||
| + | |||
| + | 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. | ||
| + | <br/><br/> | ||
| + | |||
| + | Example In the tree above, with 21 and 44 added, remove 32 and 42. | ||
| + | <br/><br/> | ||
| + | |||
| + | 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. | ||
| + | <br/><br/> | ||
Revision as of 15:51, 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.
Searching for an Element in a Binary Search Tree
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.
