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;
}