'BST'에 해당되는 글 1건

  1. 2014.02.15 [데이터구조] Binary Search Tree (BST) 정리 및 예제

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" );

}


Posted by 실바라
,