Data Structure Study Notes <5> Binary Search Tree and Balanced Binary Tree

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:
1. If X is less than the key value of the root node, search in the left subtree.
2. If X is greater than the key value of the root node, search in the right subtree.
3. If X is equal to the key value of the root node, 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 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).
Insert image description here

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).
Insert image description here

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).
Insert image description here

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).
Insert image description here

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.

Insert image description here

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