pertemuan 5 Binary search trees

       A.    Binary Search Tree Operations

 •         Binary Search Tree has the following basic operations:

–     find(x)                  : find key x in the BST

–     insert(x)      : insert new key x into BST

–     remove(x)   : remove key x from BST

   Operations: Search

•         Because of the property of BST, finding/searching in BST is easy.

•         Let the key that we want to search is X.

–     We begin at root

–     If the root contains X then search terminates successfully.

–     If X is less than root’s key then search recursively on left sub tree, otherwise search recursively on right sub tree.

struct node* search (struct node *curr, int X) {

  if ( curr == NULL ) return NULL;

  // X is found

  if ( X == curr->data ) return curr;

  // X is located in left sub tree

  if ( X  < curr->data ) return find(curr->left, X);

  // X is located in right sub tree

  return find(curr->right, X);

}

Operations: Insertion

•         Inserting into BST is done recursively.

•         Let the new node’s key be X,

–     Begin at root

–     If X is less than node’s key then insert X into left sub tree, otherwise insert X into right sub tree

–     Repeat until we found an empty node to put X (X will always be a new leaf)

Example :