Binary Search Tree (BST)
Definition
A binary search tree (BST) is a sorted binary tree that is a node-based binary tree data structure which has the following properties
l The left sub-tree of a node contains only nodes with keys less than the node’s key.
l The right sub-tree of a node contains only nodes with keys greater than the node’s key.
l The left and right sub-tree each must also be a binary search tree.
l There must be no duplicate nodes.
Algorithm
1. bool IsEmpty()
Ø It returns boolean value.
Ø If the tree is empty, returns true.
bool
BST::IsEmpty()
{
return ( root==NULL );
}
2. void Insert( int k )
Ø Insert new node with value k.
Ø If there is a node with value k in the tree, do nothing.
Ø Else,
1. Make a new node.
2. Find the appropriate position in the tree.
3. INSERT!
void
BST::Insert(int k)
{
// check existence
if ( Search(k) != NULL ) return;
node *newNode = new node(k);
if ( IsEmpty() ) {
root = newNode;
return;
} else {
node *iNode = root;
while ( iNode != NULL )
{
if ( k > iNode->value ) {
if ( iNode->right == NULL ) {
iNode->right = newNode;
newNode->parent = iNode;
break;
} else
iNode = iNode->right;
} else {
if ( iNode->left == NULL ) {
iNode->left = newNode;
newNode->parent = iNode;
break;
}
else
iNode = iNode->left;
}
}
}
}
3. void Delete( int k )
Ø It deletes node with value k
1. Search the node with value k.
2. If node doesn’t exists, do nothing.
3. Else, call DeleteNode( Search(k) )
① If Search(k) is leaf tree, skip 2,3.
② It find the node which is a node with the largest value in the left subtree, or a node with the smallest value in the right subtree.
③ Change its value with founded node in 1.
④ Delete the pointer of parent points this.
⑤ DELETE NODE.
void
DeleteNode( node *iNode )
{
if ( iNode == NULL ) return;
while ( iNode->left != NULL || iNode->right != NULL )
{
if ( iNode->left != NULL ) {
node *tNode = iNode->left;
while( tNode->right != NULL ) tNode = tNode->right;
int t = iNode->value;
iNode->value = tNode->value;
tNode->value = t;
DeleteNode( tNode );
return;
} else {
node *tNode = iNode->right;
while( tNode->left != NULL ) tNode = tNode->left;
int t = iNode->value;
iNode->value = tNode->value;
tNode->value = t;
DeleteNode( tNode );
return;
}
}
if ( iNode->parent->left == iNode )
iNode->parent->left = NULL;
else
iNode->parent->right = NULL;
delete iNode;
}
4. node* Search( int k )
Ø Find the node with value k.
Ø If there is no such node, return NULL.
node*
BST::Search(int k)
{
node *iNode = root;
while ( iNode != NULL )
{
if ( k == iNode->value )
return iNode;
else if ( k > iNode->value )
iNode = iNode->right;
else
iNode = iNode->left;
}
return NULL;
}
5. void PrintInorder()
Ø It prints all values in the form “%d,%d,%d, · · ·,%d,\n”
Ø I used recursive function printLVR(node*) to use recursive technique.
Ø It prints left child and itself, and then right child.
void
printLVR( node *iNode )
{
if ( iNode == NULL ) return;
printLVR( iNode->left );
printf( "%d,", iNode->value );
printLVR( iNode->right );
}
void
BST::PrintInorder()
{
printLVR( root );
puts( "\n" );
}
'데이터구조' 카테고리의 다른 글
| [데이터구조] Red-Black Tree ( RB Tree ) 정리 및 예제 (0) | 2014.02.15 |
|---|
