美文网首页
Concerning Binary Search Trees(B

Concerning Binary Search Trees(B

作者: 刘煌旭 | 来源:发表于2020-12-26 00:23 被阅读0次

    The range query function's skipped because I haven't decided in what form to return the results.

    /**
    * Here I present a full impl of a binary search tree ADT in C.
    */
    typedef struct BSTNodeStruct {
        struct BSTNodeStruct *left;
        struct BSTNodeStruct *right;
        int key;
        int value;
        int count;
    }*BSTNode;
    
    typedef BSTNode BSTree;
    
    BSTree BSTreeCreate(int key, int val) {
        BSTree bst = (BSTree)malloc(sizeof(*bst));
        bst->left = bst->right = NULL;
        bst->value = val;
        bst->key = key;
        bst->count = 1;
        return bst;
    }
    
    void BSTNodeRelease(BSTNode node) { if (node != NULL) free(node); }
    
    void BSTreeRelease(BSTree bst) { 
        if (bst == NULL) return;
        if (bst->left != NULL) BSTreeRelease(bst->left);
        if (bst->right != NULL) BSTreeRelease(bst->right);
        BSTNodeRelease(bst); 
    }
    
    int BSTreeCount(BSTree bst) { return bst == NULL ? 0 : bst->count; }
    
    int BSTreeGet(BSTree bst, int key) {
        if (bst == NULL) return INT_MIN;
        int com = key - bst->key;
        if (com < 0) {
            return BSTreeGet(bst->left, key);
        } else if (com > 0) {
            return BSTreeGet(bst->right, key);
        } else {
            return bst->value;
        }
    }
    
    BSTree BSTreeSet(BSTree bst, int key, int val) {
        if (bst == NULL) return BSTreeCreate(key, val);
        int com = key - bst->key;
        if (com < 0) {
            bst->left = BSTreeSet(bst->left, key, val);
        } else if (com > 0) {
            bst->right = BSTreeSet(bst->right, key, val);
        } else {
            bst->value = val;
        }
        bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
        return bst;
    }
    
    BSTNode BSTreeMin(BSTree bst) {
        if (bst == NULL) return NULL;
        if (bst->left == NULL) {
            return bst;
        } else {
            return BSTreeMin(bst->left); 
        }
    }
    
    BSTNode BSTreeMax(BSTree bst) {
        if (bst == NULL) return NULL;
        if (bst->right == NULL) {
            return bst;
        } else {
            return BSTreeMax(bst->right); 
        }
    }
    
    int BSTreeFloor(BSTree bst, int key) {
        if (bst == NULL) return INT_MIN;
        int com = key - bst->key;
        if (com < 0) {
            return BSTreeFloor(bst->left, key);
        } else if (com > 0) {
            int floor = BSTreeFloor(bst->right, key);
            return floor == INT_MIN ? bst->key : floor;
        } else {
            return bst->key;
        }
    }
    
    int BSTreeCeiling(BSTree bst, int key) {
        if (bst == NULL) return INT_MIN;
        int com = key - bst->key;
        if (com < 0) {
            int ceiling = BSTreeCeiling(bst->left, key);
            return ceiling == INT_MIN ? bst->key : ceiling;
        } else if (com > 0) {
            return BSTreeCeiling(bst->right, key);
        } else {
            return bst->key;
        }
        return 0;
    }
    
    /**
     * The definitions of rank&selection are somewhat confusing...
    */
    int BSTreeSelect(BSTree bst, int rank) {
        if (bst == NULL) return INT_MIN;
        int count = BSTreeCount(bst->left);
        if (rank < count) {
            return BSTreeSelect(bst->left, rank);
        } else if (rank > count) {
            return BSTreeSelect(bst->right, rank - 1 - count);
        } else {
            return bst->key;
        }
    }
    
    int BSTreeRank(BSTree bst, int key) {
        if (bst == NULL) return 0;
        int com = key - bst->key;
        if (com < 0) {
            return BSTreeRank(bst->left, key);
        } else if (com > 0) {
            return BSTreeRank(bst->right, key) + 1 + (bst->left != NULL ? bst->left->count : 0);
        } else {
            return bst->left == NULL ? 0 : bst->left->count;
        }
    }
    
    BSTNode BSTreeDeleteMin(BSTree bst) {
        if (bst == NULL) return NULL;
        if (bst->left == NULL) {
            if (bst->right == NULL) {//last node
                free(bst);
                return NULL;
            } else {
                return bst->right;
            }
        } else {
            BSTNode x = bst->left;
            bst->left = BSTreeDeleteMin(bst->left);
            bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
            if (x != bst->left) { BSTNodeRelease(x); }
            return bst;
        }
    }
    
    BSTNode BSTreeDeleteMax(BSTree bst) {
        if (bst == NULL) return NULL;
        if (bst->right == NULL) {
            if (bst->left == NULL) {//last node
                free(bst);
                return NULL;
            } else {
                return bst->left;
            }
        } else {
            BSTNode x = bst->right;
            bst->right = BSTreeDeleteMax(bst->right);
            bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
            if (x != bst->right) { BSTNodeRelease(x); }
            return bst;
        }
    }
    
    /**
     * The deletion process work by moving the contents of the min node in the right sub bst and delete this min node.
    */
    BSTNode BSTreeDelete(BSTree bst, int key) {
        if (bst == NULL) return NULL;
        if (key < bst->key) {
            bst->left = BSTreeDelete(bst->left, key);
        } else if (key > bst->key) {
            bst->right = BSTreeDelete(bst->right, key);
        } else {
            if (bst->left == NULL) {
                BSTNodeRelease(bst);
                return bst->right;
            }
            if (bst->right == NULL) {
                BSTNodeRelease(bst);
                return bst->left;
            }
            //The order of the following instructions can not be changed.
            BSTNode t = bst;
            bst = BSTreeMin(bst->right);
            bst->right = BSTreeDeleteMin(t->right);
            bst->left = t->left;
        }
        bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
        return bst;
    }
    
    #define L -1
    #define R 1
    #define P 0
    void BSTreePrintLevel(BSTree bst, int level, int k) {
        if (bst == NULL) return;
        int i = level;
        while (i-- > 0) { printf("-"); }
        printf("{%s %i: %i; %i %s}\n", k == L ? "'" : "", bst->key, bst->value, bst->count, k == R ? "'" : "");
        if (bst->left != NULL) { BSTreePrintLevel(bst->left, level + 1, L); }
        if (bst->right != NULL) { BSTreePrintLevel(bst->right, level + 1, R); }
    }
    
    void BSTreePrint(BSTree bst) {
        if (bst == NULL) return;
        BSTreePrintLevel(bst, 0, P);
    }
    

    相关文章

      网友评论

          本文标题:Concerning Binary Search Trees(B

          本文链接:https://www.haomeiwen.com/subject/hwjwnktx.html