BST

BST(binary search tree)#

  • 左子树上所有结点的值均小于或等于它的根结点的值; 右子树上所有结点的值均大于或等于它的根结点的值; 左、右子树也分别为BST

_data_struct# 

typedef struct bst_node_s  bst_node_t;
struct bst_node_s {
    bst_key_t       key;
    bst_node_t     *left;
    bst_node_t     *right;
    bst_node_t     *parent;
    u_char                 data;
};

typedef void (*bst_insert_pt) (bst_node_t *root,
    bst_node_t *node, bst_node_t *sentinel);
typedef struct bst_s  bst_t;
struct bst_s {
    bst_node_t     *root;
    bst_node_t     *sentinel;
    bst_insert_pt   insert;
};

_search# 

bst_node_t *
bst_insert_value(bst_t *tree, bst_key_t *key)
{
    bst_node_t  *p, *sentinel;

    sentinel = tree->sentinel;
    p = tree->root;

    for ( ;; ) {

        if (*p == sentinel) {
            return NULL;
        }

        if (key == p->key) {
            return p;
        }

        p = (node->key < p->key) ? &p->left : &p->right;

    }

}

Time Complexity#

  • best: O(log(n))
  • worst: O(n)

_insert# 

void
bst_insert_value(bst_node_t *temp, bst_node_t *node,
    bst_node_t *sentinel)
{
    bst_node_t  **p;

    for ( ;; ) {

        p = (node->key < temp->key) ? &temp->left : &temp->right;

        if (*p == sentinel) {
            break;
        }

        temp = *p;
    }

    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
}

Time Complexity#

  • best: O(log(n))
  • worst: O(n)

_delete# 

void
bst_delete_value(bst_t *tree, bst_node_t *node)
{
    bst_node_t  **root, *subst, *temp;

    root = &tree->root;
    sentinel = tree->sentinel;

    if (node->left == sentinel) {
        temp = node->right;
        subst = node;

    } else if (node->right == sentinel) {
        temp = node->left;
        subst = node;

    } else {
        subst = bst_min(node->right, sentinel);
        temp = subst->right;
    }

    if (subst == *root) {
        *root = temp;

        node->left = NULL;
        node->right = NULL;
        node->parent = NULL;
        node->key = 0;

        return;
    }

    if (subst == subst->parent->left) {
        subst->parent->left = temp;

    } else {
        subst->parent->right = temp;
    }

    if (subst == node) {

        temp->parent = subst->parent;

    } else {

        if (subst->parent == node) {
            temp->parent = subst;

        } else {
            temp->parent = subst->parent;
        }

        subst->left = node->left;
        subst->right = node->right;
        subst->parent = node->parent;

        if (node == *root) {
            *root = subst;

        } else {
            if (node == node->parent->left) {
                node->parent->left = subst;
            } else {
                node->parent->right = subst;
            }
        }

        if (subst->left != sentinel) {
            subst->left->parent = subst;
        }

        if (subst->right != sentinel) {
            subst->right->parent = subst;
        }
    }
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->key = 0;
}

Time Complexity#

  • best: O(log(n))
  • worst: O(n)