Changeset 69 for libbst/libbst.c

Timestamp:

09/08/06 17:39:34 (4 years ago)

Author:

aqua

Message:

code clean up finished~

Files:

• libbst/libbst.c (modified) (4 diffs)

libbst/libbst.c

@@ -4 +4 @@
 
 /* get the min value of tree.. */
-bst_ptr bst_get_min( bst_ptr root ){
-
-        bst_ptr tmp;
-
-        tmp = root;
-        
-        if( tmp != NULL ){
-
-                /* go leftest!! */
-                while( tmp->left != NULL )
-                        tmp = tmp->left;
-
-        }
-        return tmp;
+static int bst_get_min( bst_ptr node ){
+
+        /* go leftest!! */
+        if( node != NULL )
+                while( node->left != NULL )
+                        node = node->left;
+
+        return node->var;
 
 }
 
 /* get the max value of tree.. */
-bst_ptr bst_get_max( bst_ptr root ){
-
-        bst_ptr tmp;
-
-        tmp = root;
-        
-        if( tmp != NULL ){
-
-                /* go rightest !! */
-                while( tmp->right != NULL )
-                        tmp = tmp->right;
-
-        }
-        return tmp;
+static int bst_get_max( bst_ptr node ){
+
+        /* go rightest !! */
+        if( node != NULL )
+                while( node->right != NULL )
+                        node = node->right;
+
+        return node->var;
 
 }
@@ -100 +88 @@
 }
 
+static bst_ptr bst_create_node( int var ){
+
+        bst_ptr tmp;
+
+        tmp = (bst_ptr) malloc( sizeof(bst) ); 
+        
+        tmp->var = var;
+        tmp->left = NULL;
+        tmp->right = NULL;
+
+        return tmp;
+
+}
+
+#if 0
+/* this interface will be better in avl tree */
+static bst_ptr bst_real_add( bst_ptr cur, int var ){
+
+        bst_ptr tmp;
+        
+        if( cur == NULL ){
+
+                tmp = bst_create_node( var );
+                return tmp;
+
+        }
+
+        /* if the key is already in this tree... then error! */
+        else if( cur->var == var )
+                return NULL;
+
+        /* if the given key is smaller than current key... traversal right child */
+        else if( cur->var < var ){
+
+                if( (tmp = bst_real_add( cur->right, var )) == NULL )
+                        return NULL;
+                
+                cur->right = tmp;
+                return cur;
+
+        }
+
+        /* if the given key is bigger than current key... traversal left child */
+        else {
+                if( (tmp = bst_real_add( cur->left, var )) == NULL )
+                        return NULL;
+
+                cur->left = tmp;
+                return cur;
+        }
+
+}
+#endif
+
 /* add */
 int bst_add( bst_ptr* root, int var ){
@@ -105 +147 @@
         bst_ptr tmp;
 
+        /* 
+         * simple way (this will be use in AVL)
+         *
+         * (*root) = bst_real_add( *root, var );
+         * return 1;
+         *
+         * simple way finished 
+         */
+
+        /* if tree is empty, then create node & make it root node of tree */
         if( (*root) == NULL ){
-
-                if( (*root) = (bst_ptr) malloc( sizeof( bst ) ) ){
-                
-                        (*root)->var = var;
-                        (*root)->left = NULL;
-                        (*root)->right = NULL;
-                        (*root)->mother = NULL;
-
-                        return 1;
-
-                }
-                else
+                (*root) = bst_create_node( var );
+                return 1;
+        }
+
+        tmp = (*root);
+        do {
+
+                /* if given key is bigger than current key */
+                if( tmp->var > var ){
+
+                        /* follow left child, if exists */
+                        if( tmp->left != NULL )
+                                tmp = tmp->left;
+                        
+                        /* if not, create node & attach it as left child */
+                        else{
+                                tmp->left = bst_create_node( var );
+                                break;
+                        }
+                        
+                }
+
+                /* if given key is same as current key then error! */
+                else if( tmp->var == var )
                         return ERROR;
-
-        }
-        else{
-
-                tmp = (*root);
-
-                while( tmp != NULL ){
-
-                        if( tmp->var > var ){
-
-                                if( tmp->left != NULL )
-                                        tmp = tmp->left;
-                                
-                                else{
-                                                
-                                        tmp->left = (bst_ptr) malloc( sizeof( bst ) );
-                                        
-                                        tmp->left->mother = tmp;
-                                        tmp = tmp->left;
-                                        break;
-
-                                }
-                                
+                
+                /* if given key is bigger than current key */
+                else {
+
+                        /* if this node has right child, then follow it */
+                        if( tmp->right != NULL )
+                                tmp = tmp->right;
+                        
+                        /* else create node and attach it as right child */
+                        else{
+                                tmp->right = bst_create_node( var );
+                                break;
                         }
-                        else if( tmp->var == var )
-                                return ERROR;
-                        
-                        else{
-
-                                if( tmp->right != NULL )
-                                        tmp = tmp->right;
-                                
-                                else{
-                                                
-                                        tmp->right = (bst_ptr) malloc( sizeof( bst ) );
-                                        
-                                        tmp->right->mother = tmp;
-                                        tmp = tmp->right;
-                                        break;
-
-                                }
-
-                        }
-
-                }
-                tmp->var = var;
-                tmp->left = NULL;
-                tmp->right = NULL;
-
-                return 1;
-                
-        }
+
+                }
+
+        } while( tmp != NULL );
+
+        return 1;
         
 }
@@ -177 +208 @@
 int bst_del( bst_ptr* root, int var ){
 
-        bst_ptr tmp, tmp_var;
-
-        /* empty tree.. */
-        if( ( tmp_var = (bst_ptr) bst_search( *root, var ) ) == NULL )
+        bst_ptr mother, cur;
+        int tmp;
+
+        mother = NULL;
+        cur = (*root);
+
+        /* find the node */
+        while( cur != NULL ){
+                /* searching complete.. */
+                if( cur->var == var )
+                        break;
+                /* go left */
+                else if( cur->var > var ){
+                        mother = cur;
+                        cur = cur->left;
+                }
+                /* go right */
+                else if( cur->var < var ){
+                        mother = cur;
+                        cur = cur->right;
+                }
+        }
+
+        /* if can't find given key, then error */
+        if( cur == NULL )
                 return ERROR;
 
-        /* nonempty tree */
-        else{
-
-                /* has no child.. */
-                if( tmp_var->left == NULL && tmp_var->right == NULL ){
-                                
-                        tmp = tmp_var;
-                        
-                        /* if it's root */
-                        if( tmp_var->mother == NULL ){
-
-                                (*root)=NULL;
-
-                        }
-
-                        /* if its mother's left */
-                        else if( tmp_var->mother->left != tmp_var )
-                                tmp_var->mother->right = NULL;
-
-                        /* if its mother's right */
-                        else
-                                tmp_var->mother->left = NULL;
-                        
-                        free( tmp );
-
-                                
-                }
-
-                /* has one child */
-                else if( tmp_var->left == NULL ){
-
-                        tmp = tmp_var;
-        
-                        /* if it's root */
-                        if( tmp_var->mother == NULL ){
-
-                                (*root) = tmp->right;
-                                tmp->right->mother = NULL;
-                                
-                        }
-
-                        /* it's mother's left child.. */
-                        else if( tmp_var->mother->left == tmp_var ){
-
-                                tmp_var->mother->left = tmp_var->right;
-                                tmp_var->mother = tmp->mother;
-                                
-                        }
-
-                        /* it's mother's right child */
-                        else{
-                                        
-                                tmp_var->mother->right = tmp_var->right;
-                                tmp_var->mother = tmp->mother;
-
-                        }
-                        
-                        
-                }
-
-                /* has only right child.. */
-                else if( tmp_var->right == NULL ){
-                                
-                        tmp = tmp_var;
-                        
-                        if( tmp_var->mother == NULL ){
-
-                                (*root) = tmp->left;
-                                (*root)->mother = NULL;
-                                
-                        }
-                        else if( tmp_var->mother->left == tmp_var ){
-
-                                tmp_var->mother->left = tmp_var->left;
-                                tmp_var->mother->left->mother = tmp_var->mother;
-                                
-                        }
-                        else{
-                                        
-                                tmp_var->mother->right = tmp_var->left;
-                                tmp_var->mother->right->mother = tmp_var->mother;
-
-                        }
-
-                        
-                }
-                /* has two child.. */
-                else{
-                                
-                        /* get left's max value.. & swap.. */
-                        tmp = (bst_ptr)bst_get_max( tmp_var->left );
-                        tmp_var->var = tmp->var;
-
-                        /* & delete the left's max var */
-                        if( tmp_var->left != tmp )
-                                tmp->mother->right = NULL;
-
-                        else
-                                tmp_var->left = NULL;
-                        
-                        free( tmp );
-
-                }
-                return 1;
-                
-        }
-
-}
+        /* if has left child */
+        else if( cur->left != NULL ){
+                tmp = bst_get_max(cur->left);
+                bst_del( &(cur->left), tmp );
+
+                cur->var = tmp;
+                return 1;
+        }
+        /* if has right child */
+        else if( cur->right != NULL ){
+                tmp = bst_get_min(cur->right);
+                bst_del( &(cur->right), tmp );
+
+                cur->var = tmp;
+                return 1;
+        }
+        /* if has no child */
+        else {
+                if( mother == NULL )
+                        (*root) = NULL;
+
+                else if( cur == mother->left )
+                        mother->left = NULL;
+
+                else 
+                        mother->right = NULL;
+
+                free(cur);
+                return 1;
+        }
+
+}
+