## 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 it is not empty, it satisfies the following properties:

- The
**key values of all non-empty left subtrees**are less than the key value of its root node. - The
**key values of all non-empty right subtrees**are greater than the key value of its root node. **Both left and right subtrees are binary search trees.**

## 2. Operations on Binary Search Trees#

### (1) Find Operation in Binary Search Tree#

The value to be searched 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 key value of the root node**and proceed as follows:- If
**X is less than the key value of the root node**, search in the**left subtree**. - If
**X is greater than the key value of the root node**, search in the**right subtree**. - If X is
**equal**to the key value of the root node, the search is complete,**return**a**pointer**to that node.

- If

#### 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 Function 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**end node of the rightmost branch**of the tree. - The
**minimum element**must be at the**end node of the leftmost branch**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 Binary Search Tree#

To ensure that it remains a binary search tree after insertion, it is crucial to find the position where the element should be inserted.

```
BinTree Insert(ElementType X, BinTree BST) {
if(!BST) { // The original tree is empty, create and return a one-node binary search tree
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("This value already exists");
}
return BST;
}
```

### (4) Deletion in Binary Search Tree#

Consider three cases:

- If the node to be deleted is a
**leaf node**: delete it directly and modify the pointer of its parent node. - If the node to be deleted
**has only one child**: point its parent's pointer to the child node of the node to be deleted. - If the node to be deleted
**has both left and right subtrees**: use another node to replace the deleted node (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("The element to be deleted was 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 be deleted
if (BST->Left && BST->Right) { // The node to be deleted has both left and right children
Tmp = FindMin(BST->Right); // Find the smallest 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 in the right subtree
}
else { // The node to be deleted has 1 or no child nodes
Tmp = BST;
if (!BST->Left) // Has a child or no child
BST = BST->Right;
else if (!BST->Right)
BST = BST->Left;
free(Tmp);
}
}
return BST;
}
```

## II. Balanced Binary Tree#

## 1. What is a Balanced Binary Tree#

A **Balanced Binary Tree** (**AVL Tree**, Balanced Binary Tree), can be empty. When it is 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. - The
**maximum height of an AVL tree with n nodes**is**O(log~2~n)**!

**Balance Factor** (**BF**, Balanced 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 Balanced Binary Trees#

### RR Insertion — RR Rotation [Right Single Rotation]#

The problematic node (the troublesome node) is located in the right subtree of the node that was disturbed (the discoverer).

### LL Insertion — LL Rotation [Left Single Rotation]#

The problematic node (the troublesome node) is located in the left subtree of the node that was disturbed (the discoverer).

### LR Insertion — LR Rotation#

The problematic node (the troublesome node) is located in the right subtree of the left subtree of the node that was disturbed (the discoverer).

### RL Insertion — RL Rotation#

The problematic node (the troublesome node) is located in the left subtree of the right subtree of the node that was disturbed (the discoverer).

#### Note: Sometimes, even if the inserted element does not require structural adjustments, it may be necessary to recalculate some balance factors.#

## 3. Implementation of Balanced Binary Tree#

### Definition Part#

```
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#

Note: A must have a left child B. Perform a left single rotation between A and B, and update the heights of A and B, returning 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#

Note: A must have a right child B. Perform a right single rotation between A and B, and update the heights of A and B, returning 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#

Note: A must have a left child B, and B must have a right child C. First, perform a right single rotation between B and C, returning C. Then, perform a left single rotation between A and C, returning C.

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

### RL Rotation#

Note: A must have a right child B, and B must have a left child C. First, perform a left single rotation between B and C, returning C. Then, perform a right single rotation between 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 be inserted is empty, create a tree containing 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) { // Needs left rotation
if (X < T->Left->Data)
T = SingleLeftRotation(T); // Needs 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) { // Needs right rotation
if (X > T->Right->Data)
T = SingleRightRotation(T); // Needs 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 be inserted is empty, create a tree containing 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) { // Needs left rotation
if (X < T->Left->Data)
T = SingleLeftRotation(T); // Needs 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) { // Needs right rotation
if (X > T->Right->Data)
T = SingleRightRotation(T); // Needs 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

Based on the pre-order and in-order traversals, it can be restored to form such a balanced binary tree.

## III. Determine if it is the Same Binary Search Tree#

Problem: Given an insertion sequence that determines a unique binary search tree, determine whether various input insertion sequences can generate the same binary search tree.

How to determine if two sequences correspond to the same search tree?

**Build a tree, then check if other sequences are consistent with that tree!**

For example, input 3 1 4 2 to determine a binary search tree, check if 3 4 1 2 and 3 2 4 1 correspond to the same tree.

## 1. Representation of Search Tree#

```
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. Build 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 the remaining nodes into the binary tree
}
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. Determine if a Sequence is Consistent with Search Tree T#

Method: Sequentially search each number in the sequence 3 2 4 1 in tree T.

**If every node passed during the search has been searched before, then they are consistent.****Otherwise (if an unvisited node is encountered during a search), they are inconsistent.**

```
int check(Tree T,int V) {
if(T->flag) { // This point has been searched, check 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 point to be searched is exactly this point, mark it
if(V == T->v) {
T->flag = 1;
return 1;
}
else return 0; // Encountered a point that has not been seen before
}
}
```

Determine whether the tree generated by an insertion sequence of length N is consistent with the search tree.

```
int Judge(Tree T,int N) {
int i, V, flag = 0; // flag=0 means currently consistent, 1 means 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 each node in T to reset them to 0.

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

Free the space of T.

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