Pertemuan5-Binary Search Tree-2101660790

Binary Search Tree:

-          Operations: Search, Insertion, Deletion

-          Program Examples

-          Expression Tree Concept

-          Create Exp. Tree from Prefix

-          Create Exp. Tree from Postfix

-          Create Exp. Tree from Infix

-          Prefix, Postfix, Infix Traversal

-          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 Binary SearchTree  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)

Algorithm:

Step 1:           IF TREE = NULL, then 

                                    Allocate memory for TREE

                        SET TREE->DATA = VAL

                        SET TREE->LEFT = TREE ->RIGHT = NULL

            ELSE

                        IF VAL < TREE->DATA

                                                Insert(TREE->LEFT, VAL)

                        ELSE

                                                Insert(TREE->RIGHT, VAL)

                        [END OF IF]

            [END OF IF]

Step 2: End

Operations: Insertion – Example

Operations: Deletion

•         There are 3 cases which should be considered:

–     If the key is in a leaf, just delete that node

–     If the key is in a node which has one child, delete that node and connect its child to its parent

–     If the key is in a node which has two children, find the right most child of its left sub tree (node P), replace its key with P’s key and remove P recursively. (or alternately you can choose the left most child of its right sub tree)

Algorithm:

Step 1: IF TREE = NULL, then 

            Write “VAL not found in the tree”

        ELSE IF VAL < TREE->DATA

            Delete(TREE->LEFT, VAL)

        ELSE IF VAL > TREE->DATA

            Delete(TREE->RIGHT, VAL)

        ELSE IF TREE->LEFT AND TREE->RIGHT

                        SET TEMP = findLargestNode(TREE->LEFT)

                        SET TREE->DATA = TEMP->DATA

                        Delete(TREE->LEFT, TEMP->DATA)

ELSE

            SET TEMP = TREE

            IF TREE->LEFT = NULL AND TREE ->RIGHT = NULL

                        SET TREE = NULL

            ELSE IF TREE->LEFT != NULL

                        SET TREE = TREE->LEFT

            ELSE

                        SET TREE = TREE->RIGHT

            FREE TEMP

Step 2: End