This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

I. Binary Search Tree

1. What is a Binary Search Tree

A Binary Search Tree (BST, Binary Search Tree), also known as a binary sort tree or binary lookup tree, is a binary tree that can be empty. When not empty, it satisfies the following properties:

All key values in the non-empty left subtree are less than the root node's key value
All key values in the non-empty right subtree are greater than the root node's key value
Both left and right subtrees are binary search trees

2. Operations on Binary Search Trees

(1) Find Operation on BST

The value to find is X

Start searching from the root node. If the tree is empty, return NULL
If the search tree is not empty, compare X with the root node's key value and process as follows:
1. If X is less than the root node's key value, search in the left subtree
2. If X is greater than the root node's key value, search in the right subtree
3. If X equals the root node's key value, the search is complete; return a pointer to that node

Tail Recursion Implementation

Position Find(ElementType X, BinTree BST) {
 if( !BST ) return NULL;//Search failed
 if( X > BST->Data )
  return Find(X, BST->Right);//Operation 1
 else if (X < BST->Data)
  return Find(X, BST->Left); //Operation 2
 else
  return BST; //Operation 3: Search successful
}

Iterative Implementation

Position Find(ElementType X, BinTree BST) {
 while(BST) {
  if (X > BST->Data)
   BST = BST->Right;//Operation 1
  else if (X < BST->Data)
   BST = BST->Left;//Operation 2
  else
   return BST;//Operation 3: Search successful
 }
 return NULL;//Search failed
}

(2) Finding Maximum and Minimum Elements

The maximum element must be at the rightmost branch's terminal node of the tree
The minimum element must be at the leftmost branch's terminal node of the tree

Finding the Maximum Element

Recursive function

Position FindMin(BinTree BST) {
 if (!BST ) return NULL;//Empty tree, return NULL
 else if ( !BST->Left )
  return BST; //Found the leftmost leaf node
 else
  return FindMin(BST->Left);//Continue searching along the left branch
}

Iterative function

Position FindMin(BinTree BST) {
 if (BST) {
  while (BST->Left) BST = BST->Left;
 }
 return BST;
}

Finding the Minimum Element

Recursive function

Position FindMax(BinTree BST) {
 if (!BST ) return NULL;//Empty tree, return NULL
 else if ( !BST->Right )
  return BST; //Found the leftmost leaf node
 else
  return FindMin(BST->Right);//Continue searching along the right branch
}

Iterative function

Position FindMax(BinTree BST) {
 if (BST) {
  while (BST->Right) BST = BST->Right;
 }
 return BST;
}

(3) Insertion in a Binary Search Tree

The key is to find the correct position for the element to be inserted, ensuring the tree remains a valid BST after insertion.

BinTree Insert(ElementType X, BinTree BST) {
 if(!BST) { //Original tree is empty, create and return a single-node BST
  BST = malloc(sizeof(struct TreeNode));
  BST->Data = X;
  BST->Left = BST->Right = NULL;
 } else { //Start looking for the position to insert the element
  if (X < BST->Data)
   BST->Left = Insert(X, BST->Left);
  else if (X > BST->Data)
   BST->Right = Insert(X, BST->Right);
  else printf("Value already exists");
 }
 return BST;
}

(4) Deletion in a Binary Search Tree

Consider three cases:

The node to delete is a leaf node: Delete it directly and update the parent node's pointer
The node to delete has only one child node: Point the parent node's pointer to the child node of the node being deleted
The node to delete has both left and right subtrees: Replace the deleted node with another node (either the minimum element of the right subtree or the maximum element of the left subtree)

BinTree Delete(ElementType X, BinTree BST) {
 Position Tmp;
 if(!BST) printf("Element to delete not found");
 else if (X < BST->Data)
  BST->Left = Delete(X,BST->Left);
 else if (X > BST->Data)
  BST->Right = Delete(X,BST->Right);
 else { //Found the node to delete
  if (BST->Left && BST->Right) { //Node to delete has both children
   Tmp = FindMin(BST->Right); //Find the minimum element in the right subtree to fill the deleted node
   BST->Data = Tmp->Data;
   BST->Right = Delete(BST->Data,BST->Right);//After filling, delete that minimum element from the right subtree
  }
  else { //Node to delete has 1 or no children
   Tmp = BST;
   if (!BST->Left) //Has right child or no children
    BST = BST->Right;
   else if (!BST->Right)
    BST = BST->Left;
   free(Tmp);
  }
 }
 return BST;
}

II. AVL Tree (Balanced Binary Tree)

1. What is an AVL Tree

An AVL Tree (Balanced Binary Tree) can be empty. When not empty, it satisfies the following properties:

The absolute difference in height between the left and right subtrees of any node does not exceed 1
Given n nodes, the maximum height of an AVL tree is O(log₂n)!

Balance Factor (BF, Balance Factor): BF(T) = h_L - h_R, where h_L and h_R are the heights of the left and right subtrees of T, respectively.

2. Adjustments in AVL Trees

RR Insertion -- RR Rotation [Right Single Rotation]

The violating node (trouble node) is located in the right subtree of the right subtree of the violated node (discoverer)

LL Insertion -- LL Rotation [Left Single Rotation]

The violating node (trouble node) is located in the left subtree of the left subtree of the violated node (discoverer)

LR Insertion -- LR Rotation

The violating node (trouble node) is located in the right subtree of the left subtree of the violated node (discoverer)

RL Insertion -- RL Rotation

The violating node (trouble node) is located in the left subtree of the right subtree of the violated node (discoverer)

PS: Sometimes, even when inserting an element does not require structural adjustment, some balance factors may still need to be recalculated

3. AVL Tree Implementation

Definition

typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
 ElementType Data;
 AVLTree Left, Right;
 int Height;
};
int Max(int a, int b) {
 return a>b?a:b;
}

Left Single Rotation

PS: A must have a left child node B. Perform a left single rotation on A and B, update the heights of A and B, and return the new root node B.

AVLTree SingleLeftRotation(AVLTree A) {
 AVLTree B = A->Left;
 A->Left = B->Right;
 B->Right = A;
 A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
 B->Height = Max( GetHeight(B->Left),A->Height ) + 1;
 return B;
}

Right Single Rotation

PS: A must have a right child node B. Perform a right single rotation on A and B, update the heights of A and B, and return the new root node B.

AVLTree SingleRightRotation(AVLTree A) {
 AVLTree B = A->Right;
 A->Right = B->Left;
 B->Left = A;
 A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
 B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
 return B;
}

LR Rotation

PS: A must have a left child node B, and B must have a right child node C. First perform a right single rotation on B and C, returning C. Then perform a left single rotation on A and C, returning C.

AVLTree DoubleLeftRightRotation(AVLTree A) {
 A->Left = SingleRightRotation(A->Left);
 return SingleLeftRotation(A);
}

RL Rotation

PS: A must have a right child node B, and B must have a left child node C. First perform a left single rotation on B and C, returning C. Then perform a right single rotation on A and C, returning C.

AVLTree DoubleRightLeftRotation(AVLTree A) {
 A->Right = SingleLeftRotation(A->Right);
 return SingleRightRotation(A);
}

Insertion

Insert X into AVL tree T and return the adjusted AVL tree.

AVLTree Insert(AVLTree T,ElementType X) {
 if (!T) { //If the tree to insert into is empty, create a new tree with node X
  T = (AVLTree) malloc(sizeof(struct AVLNode));
  T->Data = X;
  T->Height = 0;
  T->Left = T->Right = NULL;
 } else if( X < T->Data) {
  T->Left = Insert(T->Left, X);
  if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {//Need left rotation
   if (X < T->Left->Data)
    T = SingleLeftRotation(T); //Need left single rotation
   else
    T = DoubleLeftRightRotation(T);//Left-right double rotation
  }
 } else if (X > T->Data) {
  T->Right = Insert(T->Right, X);
  if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {//Need right rotation
   if (X > T->Right->Data)
    T = SingleRightRotation(T); //Need right single rotation
   else
    T = DoubleRightLeftRotation(T);//Right-left double rotation
  }
 }
 //Update tree height
 T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
 return T;
}

Complete Code Demonstration

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
 ElementType Data;
 AVLTree Left, Right;
 int Height;
};
int Max(int a, int b) {
 return a>b?a:b;
}
int GetHeight(AVLTree A) {
    if (A)
        return A->Height;
    else
        return 0;
}
AVLTree SingleLeftRotation(AVLTree A) {//Left single rotation
 AVLTree B = A->Left;
 A->Left = B->Right;
 B->Right = A;
 A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
 B->Height = Max( GetHeight(B->Left),A->Height )+ 1;
 return B;
}
AVLTree SingleRightRotation(AVLTree A) {//Right single rotation
 AVLTree B = A->Right;
 A->Right = B->Left;
 B->Left = A;
 A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
 B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
 return B;
}
AVLTree DoubleLeftRightRotation(AVLTree A) {//Left-right double rotation
 A->Left = SingleRightRotation(A->Left);
 return SingleLeftRotation(A);
}
AVLTree DoubleRightLeftRotation(AVLTree A) {//Right-left double rotation
 A->Right = SingleLeftRotation(A->Right);
 return SingleRightRotation(A);
}
AVLTree Insert(AVLTree T,ElementType X) {//Insert X into AVL tree T

 if (!T) { //If the tree to insert into is empty, create a new tree with node X
  T = (AVLTree) malloc(sizeof(struct AVLNode));
  T->Data = X;
  T->Height = 0;
  T->Left = T->Right = NULL;

 } else if( X < T->Data) {
  T->Left = Insert(T->Left, X);
  if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {//Need left rotation
   if (X < T->Left->Data)
    T = SingleLeftRotation(T); //Need left single rotation
   else
    T = DoubleLeftRightRotation(T);//Left-right double rotation
  }
 } else if (X > T->Data) {
  T->Right = Insert(T->Right, X);
  if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {//Need right rotation
   if (X > T->Right->Data)
    T = SingleRightRotation(T); //Need right single rotation
   else
    T = DoubleRightLeftRotation(T);//Right-left double rotation
  }
 }
 //Update tree height
 T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
    return T;
}
void PreOrderTraversal(AVLTree T) {
 if(T) {
  printf("%d", T->Data);
  PreOrderTraversal( T->Left);
  PreOrderTraversal( T->Right);
 }
}
void InOrderTraversal(AVLTree T) {
 if(T) {
  InOrderTraversal( T->Left);
  printf("%d", T->Data);
  InOrderTraversal( T->Right);
 }
}
int main() {
    AVLTree T = NULL;
    int i;
    for (i = 1; i < 10; i++) {
        T = Insert(T,i);
    }
    PreOrderTraversal(T);//Pre-order traversal
    printf("\n");
    InOrderTraversal(T);//In-order traversal
    return 0;
}

Output:

421365879 123456789

From the pre-order and in-order traversal results, we can easily reconstruct the following AVL tree:

III. Determining if Two BSTs are the Same

Problem: Given an insertion sequence that determines a unique BST, for various input insertion sequences, determine whether they produce the same BST.

How to determine if two sequences correspond to the same search tree? Build one tree, then check whether other sequences are consistent with it! For example, given the insertion sequence 3 1 4 2 to build a BST, determine whether 3 4 1 2 and 3 2 4 1 correspond to the same tree.

1. Search Tree Representation

typedef struct TreeNode *Tree;
struct TreeNode {
 int v;
 Tree Left,Right;
 int flag; //Used to mark whether this node has been searched; 1 means searched
};

2. Building Search Tree T

Tree MakeTree(int N) {
 Tree T;
 int i, V;
 scanf("%d", &V);
 T = NewNode(V);
 for(i = 1; i < N; i++) {
  scanf("%d",&V);
  T = Insert(T,V);//Insert remaining nodes into the BST
 }
 return T;
}

Tree NewNode(int V) {
 Tree T = (Tree)malloc(sizeof(struct TreeNode));
 T->v = V;
 T->Left = T->Right = NULL;
 T->flag = 0;
 return T;
}

Tree Insert(Tree T, int V) {
 if(!T) T = NewNode(V);
 else {
  if (V > T->v)
   T->Right = Insert(T->Right, V);
  else
   T->Left = Insert(T->Left,V);
 }
 return T;
}

3. Checking Whether a Sequence is Consistent with Search Tree T

Method: Search for each number in the sequence 3 2 4 1 in tree T in order.

If every search passes through only previously searched nodes, the trees are consistent
Otherwise (a search encounters a previously unseen node), they are not consistent

int check(Tree T,int V) {
 if(T->flag) {//This node has been searched; determine whether to search in the left or right subtree
  if(V < T->v) return check(T->Left,V);
  else if(V > T->v) return check(T->Right,V);
  else return 0;
 }
 else { //The node to find is exactly this node; mark it
  if(V == T->v) {
   T->flag = 1;
   return 1;
  }
  else return 0; //Encountered a previously unseen node
 }
}

Determine whether an insertion sequence of length N produces a tree consistent with the search tree.

int Judge(Tree T,int N) {
 int i, V, flag = 0;//flag=0 means currently consistent; 1 means already inconsistent
 scanf("%d",&V);
 if (V != T->v) flag = 1;
 else T->flag = 1;
 for(i = 1; i < N; i++) {
  scanf("%d", &V);
  if( (!flag) && (!check(T,V)) ) flag = 1;
 }
 if(flag) return 0;
 else return 1;
}

Clear the flag marks of all nodes in T, setting them to 0.

void ResetT(Tree T) {
 if(T->Left) ResetT(T->Left);
 if(T->Right) ResetT(T->Right);
 T->flag = 0;
}

Free the memory of T.

void FreeTree(Tree T) {
 if(T->Left) FreeTree(T->Left);
 if(T->Right) FreeTree(T->Right);
 free(T);
}

Data Structure Study Notes <5> Binary Search Trees and AVL Trees