Binary Search Tree

Binary Search Tree is a #202112102110 that is dedicated for searching.

Characteristics

  • All values in left subtree is less than in root
  • All values in right subtree is larger than in root

Analysis

  • The average depth of Binary Search Tree is \(O(\log N)\)
  • All operations, except MakeEmpty, will result in \(O(\log N)\)
  • If during Insertion there are duplicated items, add in extra field or use an auxiliary struct such as 202110191729 or another Binary Search Tree
  • Deletion in Binary Search Tree favours making the left subtrees deeper than the right subtrees, which will make the Tree right-heavy
  • Lazy Deletion by merely mark the node as deleted could avoid reinsertion overhead

Implementation

#ifndef _Tree_H

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

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

#endif    // _Tree_H
struct TreeNode {
  ElementType Element;
  SearchTree  Left;
  SearchTree  Right;
};

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

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

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)
    return NULL;
  else if (T->Right == NULL)
    return T;
  else
    return FindMax(T->Right)
}

SearchTree Insert(ElementType X, SearchTree T) {
  if (T == NULL) {
    // Create and return a one-node tree
    T = malloc(sizeof(struct TreeNode));
    if (T == NULL)
      FatalError("Out of space!!!");
    else {
      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;
}

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

  if (T == NULL)
    Error("Element not found");
  else if (X < T->Element)    // Go left
    T->Left = Delete(X, T->Left);
  else if (X > T->Element)    // Go right
    T->Right = Delete(X, T->Left);
  else if (T->Left && T->Right) {   // Two children
    // Replace with smallest in right subtree
    TmpCell = FindMin(T->Right);
    T->Element = TmpCell->Element;
    T->Right = Delete(T->Element, T->Right);
  } else {    // One or zero children
    TmpCell = T;
    if (T->Left == NULL)    // Also handles 0 children
      T = T->Right;
    else if (T->Right == NULL)
      T = T->Left;
    free(TmpCell);
  }

  return T;
}
Links to this page
#data-structure #tree