Search Tree ADT--Binary Search Tree

An important application of binary trees is their use in search.

The properties of binary lookup tree: For each node X in the tree, the value of all items in its left subtree is smaller than that in X, while the value of all items in its right subtree is larger than that in X. This means that all elements of the tree can be sorted in a consistent way.

The average depth of the binary search tree is O(logN). Binary lookup trees require that all items be sorted. Two items in the tree can always be compared using the compareTo method in the Comparable interface.

ADT's statement:

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMax(SearchTree T);
Position FindMin(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);

struct TreeNode{
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};

1. Implementation of MakeEmpty

SearchTree MakeEmpty(SearchTree T){
    if(T != NULL){
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

2. Realization of Find

Position Find(ElementType X, SearchTree T){
    if(T == NULL)
        return NULL;
    else if(X < T->Element)
        return Find(X, T->Left);
    else if(X > T->Element)
        return Find(X, T->Right);
    else
        return T;
}

3. Implementation of FindMax and FindMin (a recursive non-recursive)

Position FindMin(SearchTree T){
    if(T == NULL)
        return NULL;
    else if(T->Left == NULL)
        return T;
    else
        return FindMin(T->Left);
}

Position FindMax(SearchTree T){
    if(T != NULL)
        while(T->Right != NULL)
            T = T->Right;
    return T;
}

4. Implementation of Insert

SearchTree Insert(ElementType X, SearchTree T){
    if(T == NULL){
        T = (SearchTree)malloc(sizeof(struct TreeNode));
        T->Element = X;
        T->Left = T->Right = NULL;
    }
    else if(X < T->Element)
        T->Left = Insert(X, T->Left);
    else if(X > T->Element)
        T->Right = Insert(X, T->Right);
    
    // Else X is in the tree already, we'll do nothing!
    return T;
}

5. Implementation of Delete

SearchTree Delete(ElementType X, SearchTree T){
    Position TmpCell;

    if(T == NULL)
        printf("Element Not Found\n");
    else if(X < T->Element)
        T->Left = Delete(X, T->Left);
    else if(X > T->Element)
        T->Right = Delete(X, T->Right);
    else if(T->Left && T->Right){
        TmpCell = FindMin(T->Right);
        T->Element = TmpCell->Element;
        T->Right = Delete(TmpCell->Element, T->Right);
    }
    else{
        TmpCell = T;
        if(!(T->Left))
            T = T->Right;
        else if(!(T->Right))
            T = T->Left;
        free(TmpCell);
    }
    return T;
}

Tags: C

Posted on Tue, 08 Oct 2019 02:06:19 -0700 by mxl