1.
Binary Search Tree (BST)
A Binary Search Tree (BST) is one of the most widely used data structures in computer science,
primarily known for its efficient search, insertion, and deletion operations
operations.
It is a type of binary tree where each node has at most two children,, referred to as the left child
and the right child.
A Binary Search Tree (BST) is a binary tree in which:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree contains only nodes with keys greater than the node’s key.
Both left and right subtrees are also BSTs.
Operations on BST
Search
Let's say we want to search for the number key, We start at the root. Then:
1. We compare the value to be searched with the value of the root.
If it's equal we are done with the search.
If key == root → found
2. If it's smaller we know that we need to go to the left subtree.
If key < root → search le subtree
3. If it's greater we search in the right subtree.
If key > root → search right subtree
4. Repeat the above step till no more traversal is possible
5. If at any iteration, key is found, return True. If the node is null, return False.
Algorithm
Search(root, key)
1. If root == null
return "Not Found"
2. If [Link] == key
return "Found"
3. If key < [Link]
return Search([Link], key)
4. Else
return Search([Link], key)
Program:
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
class BinarySearchTree {
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// Function to search a key in BST
boolean search(Node root, int key) {
if (root == null)
return false; // Element not found
if ([Link] == key)
return true; // Element found
// If key is smaller, search in left subtree
if (key < [Link])
return search([Link], key);
// If key is greater, search in right subtree
return search([Link], key);
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// Creating a simple BST manually
[Link] = new Node(50);
[Link] = new Node(30);
[Link] = new Node(70);
[Link] = new Node(20);
[Link] = new Node(40);
[Link] = new Node(60);
[Link] = new Node(80);
int key = 40;
if ([Link]([Link], key))
[Link](key + " found in BST");
else
[Link](key + " not found in BST");
} }
Red-Black Trees
Binary search trees are a fundamental data structure, but their performance can suffer if the
tree becomes unbalanced.
Red Black Trees are a type of balanced binary search tree that use a set of rules to maintain
balance, ensuring logarithmic time complexity for operations like insertion, deletion, and
searching, regardless of the initial shape of the tree.
Red Black Trees are self-balancing, using a simple color-coding scheme to adjust the tree after
each modification.
A Red-Black Tree is a self-balancing
balancing binary search tree where each node has an additional
attribute: a color, which can be either red or black.
The primary objective of these trees is to maintain balance during insertions and deletions,
ensuring efficient data retrieval and manipulation
Properties (Rules)
1. Node Color:: Each node is either red or black.
2. Root Property: The root of the tree is always black.
3. Red Property:: Red nodes cannot have red children (no two consecutive red nodes on
any path).
4. Black Property:: Every path from a node to its descendant null nodes (leaves) has the
same number of black nodes.
5. Leaf Property:: All leaves (NIL nodes) are black.
These properties ensure the tree is always approximately balanced,, keeping operations fast.
Red Black Tree Searching
Searching for a node in a Red-Black Tree is similar to searching in a standard Binary Search Tree
(BST). The search operation follows a straightforward path from the root to a leaf, comparing
the target value with the current node's value and moving left or right accordingly.
Search Steps
1. Start at the Root: Begin the search at the root node.
2. Traverse the Tree:
If the target value is equal to the current node's value, the node is found.
If the target value is less than the current node's value, move to the left child.
If the target value is greater than the current node's value, move to the right
child.
3. Repeat: Continue this process until the target value is found or a NIL node is reached
(indicating the value is not present in the tree).
Algorithm:
Algorithm RB_Search(root, key)
key → value to search
current ← root
while current ≠ NULL and key ≠ [Link] do
if key < [Link] then
current ← [Link]
else
current ← [Link]
end while
return current
Program:
class Node {
int data;
Node left, right, parent;
boolean color; // true = Red, false = Black
Node(int data) {
[Link] = data;
left = right = parent = null;
color = true; // New nodes are usually red by default
}
}
// Red-Black Tree class
class RedBlackTree {
Node root;
// Constructor
public RedBlackTree() {
root = null;
}
// Function to search for a key in Red-Black Tree
public boolean search(Node root, int key) {
if (root == null)
return false;
if (key == [Link])
return true;
// If key is smaller, go to left subtree
if (key < [Link])
return search([Link], key);
else // If key is greater, go to right subtree
return search([Link], key);
}
// function to call search
public void searchKey(int key) {
if (search(root, key))
[Link](key + " found in Red-Black Tree");
else
[Link](key + " not found in Red-Black Tree");
}
// Manually creating a small Red-Black Tree
public void createSampleTree() {
root = new Node(20);
[Link] = false; // root is black
[Link] = new Node(10);
[Link] = true;
[Link] = new Node(30);
[Link] = true;
[Link] = new Node(5);
[Link] = false;
[Link] = new Node(15);
[Link] = false;
}
public static void main(String[] args) {
RedBlackTree tree = new RedBlackTree();
[Link](); // Create tree manually
[Link](15); // Example search
[Link](25); // Another search
}
}