13.1 What is search?

Search

Definition:

Search is the process of locating a specific element (called the search key) within a collection of data (like an array, list, tree, or database).

Search Key

Definition:

The search key is the specific value or target you're trying to find in a data structure during a search operation.

• It can be a number, string, or any comparable object.
• In complex structures (like databases or key-value pairs), it is the identifier used to look up a record.

13.2 Search in a unsorted array

Sequential search(순차 탐색)

Sequential search is the simplest and most direct search method among search methods. Sequential search is a method of finding a desired item by inspecting items in an unordered array one by one from the beginning to the end.

• Time complexity: O(n) ((n + 1) / 2)

13.3 Search in a sorted array

Binary search

Definition

Binary Search is an efficient algorithm used to find the position of a target value (search key) in a sorted array by repeatedly dividing the search interval in half.

Prerequisite

• The array must be sorted (either ascending or descending).
• Without sorting, binary search won’t work.

How It Works (Step-by-Step)

Given a sorted array:

int[] arr = {2, 4, 7, 10, 15, 18, 21};
int target = 10;

Steps:
1. Set two pointers: low = 0, high = n - 1
2. Calculate mid: mid = (low + high) / 2
3. Compare arr[mid] with the target:

• equal → return mid
• If arr[mid] < target → search in the right half
• If arr[mid] > target → search in the left half
  4.Repeat until found or low > high

Java Code

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // Avoid overflow

            if (arr[mid] == target) {
                return mid; // Target found
            } else if (arr[mid] < target) {
                low = mid + 1; // Search right half
            } else {
                high = mid - 1; // Search left half
            }
        }

        return -1; // Target not found
    }
}

Time Complexity

Case	Time Complexity
Best	O(1) (target at middle)
Average	O(log n)
Worst	O(log n)

• Why O(log n)? Because the array is halved on each step.

Space Complexity

• O(1) for iterative version
• O(log n) for recursive version (due to call stack)

13.5 AVL Tree

Definition

An AVL Tree is a type of self-balancing Binary Search Tree (BST) where the height difference between left and right subtrees (balance factor) of any node is at most 1.

Named after its inventors: Adelson-Velsky and Landis.

Key Property: Balance Factor

For every node:

Balance Factor = Height(left subtree) − Height(right subtree)

• Must be −1, 0, or +1 for the tree to be balanced.
• If this balance is violated after insertion or deletion, rotations are used to fix it.

Rotations to Maintain Balance

There are 4 types of rotations in AVL trees:

Case Type	Situation	Rotation Used
LL (Left-Left)	Insertion in left subtree of left child	Right Rotation
RR (Right-Right)	Insertion in right subtree of right child	Left Rotation
LR (Left-Right)	Insertion in right subtree of left child	Left + Right
RL (Right-Left)	Insertion in left subtree of right child	Right + Left

Java Code

class AVLTree {

    class Node {
        int key, height;
        Node left, right;

        Node(int d) {
            key = d;
            height = 1;
        }
    }

    Node root;

    // Utility: Get height
    int height(Node N) {
        return (N == null) ? 0 : N.height;
    }

    // Utility: Get balance factor
    int getBalance(Node N) {
        return (N == null) ? 0 : height(N.left) - height(N.right);
    }

    // Utility: Right rotate
    Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // Perform rotation
        x.right = y;
        y.left = T2;

        // Update heights
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

    // Utility: Left rotate
    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // Perform rotation
        y.left = x;
        x.right = T2;

        // Update heights
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

    // Insert a node
    Node insert(Node node, int key) {
        // Step 1: Perform normal BST insertion
        if (node == null)
            return new Node(key);

        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else
            return node; // No duplicates

        // Step 2: Update height
        node.height = 1 + Math.max(height(node.left), height(node.right));

        // Step 3: Check balance and rotate
        int balance = getBalance(node);

        // Left Left
        if (balance > 1 && key < node.left.key)
            return rightRotate(node);

        // Right Right
        if (balance < -1 && key > node.right.key)
            return leftRotate(node);

        // Left Right
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node; // return unchanged
    }

    void insert(int key) {
        root = insert(root, key);
    }

    // Inorder traversal
    void inorder(Node node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.key + " ");
            inorder(node.right);
        }
    }

    void printInorder() {
        inorder(root);
        System.out.println();
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30); // RR rotation here
        tree.insert(40);
        tree.insert(50); // Again RR rotation
        tree.insert(25); // RL rotation here

        System.out.println("Inorder traversal of AVL tree:");
        tree.printInorder();
    }
}

Time Complexity

Operation	Time Complexity
Insert	O(log n)
Delete	O(log n)
Search	O(log n)

• AVL Trees are always balanced, ensuring logarithmic operations.

Space Complexity

• O(log n) auxiliary space for recursion stack

Balanced Property

• Height is maintained as O(log n)
• Better than plain BST, which can degrade to O(n) in worst-case

Summary Table

Property	Value
Time Complexity	O(log n) for insert/delete/search
Self-Balancing	✅ Yes
Space Complexity	O(log n) recursion stack
Rotations Used	Left, Right, LR, RL
Use Case	Where guaranteed log-time ops needed

13.6 2-3 Tree

Definition

A 2-3 Tree is a balanced search tree where each internal node can have either 2 children (2-node) or 3 children (3-node), and all leaf nodes are at the same depth.

It maintains balance automatically during insertions and deletions — so operations are guaranteed to run in O(log n) time.

Node Types

Node Type	Description	Structure
2-Node	Has 1 key and 2 children	[key] → left < key < right
3-Node	Has 2 keys and 3 children	[key1, key2] → left < key1 < middle < key2 < right

Properties of 2-3 Tree

1. Every internal node is either a 2-node or a 3-node.
2. All leaves are at the same depth.
3. The tree is always height-balanced.
4. In-order traversal yields sorted order.
5. Insertions and deletions may cause splitting or merging, but maintain the properties.

Example Structure

        [20, 40]          ← 3-node
       /   |    \
     <20 20–40 >40

• Left subtree: all keys < 20
• Middle subtree: keys between 20 and 40
• Right subtree: keys > 40

Operaions

Insertion

• Insert key into appropriate leaf node.
• If the node becomes a 4-node (too many keys), split it:
  • Middle key moves up to the parent.
  • Node splits into two 2-nodes.
• May propagate splits up to root, possibly increasing height.

Deletion

• Remove the key.
• If a node ends up with too few keys:
  • Borrow from siblings, or
  • Merge with siblings.
• Merging may propagate upward, possibly decreasing tree height.

Time Complexity

Operation	Time Complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)

Why? Because tree height is kept logarithmic due to balancing.

Summary Table

Property	Value
Type	Balanced Search Tree
Node Types	2-node (1 key), 3-node (2 keys)
Children	2 for 2-node, 3 for 3-node
Height-balanced	✅ Yes
All leaves same depth	✅ Yes
Time Complexity	O(log n) for search, insert, delete
Use Case	Foundation for B-Trees and Red-Black Trees

Relation to Other Trees

Tree Type	Notes
2-3 Tree	Base model: balanced, simple, guarantees O(log n)
2-3-4 Tree	Extends 2-3 Tree to 4-nodes (up to 3 keys, 4 children)
Red-Black Tree	Binary tree representation of 2-3-4 Tree (used in Java TreeMap/TreeSet)
B-Tree	Generalization for disk-based structures (used in databases, filesystems)

Every 2-3 Tree can be represented as a Red-Black Tree, which makes Red-Black Trees easier to implement in binary tree form.

Comparison of Search Trees

Comparison

Property / Tree	Binary Search Tree (BST)	AVL Tree	Red-Black Tree	2-3 Tree	B-Tree	Splay Tree	Trie
Balancing	❌ No	✅ Strict	✅ Loose (relaxed)	✅ Strict	✅ Strict	⚠️ Semi (self-adjusting)	❌ No (but height depends on key length)
Worst-case Height	O(n)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)	O(L) (L = key length)
Search Time	O(n)	O(log n)	O(log n)	O(log n)	O(log n)	O(n), amortized O(log n)	O(L)
Insert/Delete Time	O(n)	O(log n)	O(log n)	O(log n)	O(log n)	O(n), amortized O(log n)	O(L)
Space Overhead	Low	Moderate	Moderate	Moderate	High (many children)	Low	High (many pointers)
Self-Balancing	❌ No	✅ Yes	✅ Yes	✅ Yes	✅ Yes	⚠️ Adjusts only on access	❌ No
Stable Tree Height	❌ No	✅ Yes	✅ Yes	✅ Yes	✅ Yes	❌ No	✅ Yes (predictable by key length)
Use in Libraries	Rare	Sometimes	✅ Java TreeMap, C++ std::map	Conceptual	✅ DBs, filesystems	Rare	✅ Dictionary, autocomplete
Best For	Simple cases	Real-time systems	General-purpose balanced trees	Theoretical/educational	Disk-based systems	Frequently-accessed keys	Prefix-based search
In-Order Traversal	✅ Yes	✅ Yes	✅ Yes	✅ Yes	✅ Yes	✅ Yes	❌ No (lexicographic traversal possible)

Key Descriptions

1. Binary Search Tree (BST)
   • Simple structure.
   • Unbalanced → worst case O(n).
   • Good for learning but not for critical applications.
2. AVL Tree
   • Strictly balanced → better worst-case performance than Red-Black.
   • Slower insert/delete than Red-Black (more rotations).
   • Best when read-heavy and real-time constraints matter.
3. Red-Black Tree
   • Loosely balanced → fewer rotations, faster insert/delete.
   • Widely used in libraries (Java, C++).
   • Slightly worse search than AVL but better overall efficiency.
4. 2-3 Tree
   • Every internal node has 2 or 3 children.
   • Strict balancing → ideal for theoretical understanding.
   • Foundation for Red-Black Trees.
5. B-Tree
   • Generalization of 2-3-4 Tree for disk-based storage.
   • Used in databases, file systems, etc.
   • Internal nodes can have many children → fewer disk accesses.
6. Splay Tree
   • Self-adjusting: recently accessed elements move to the root.
   • Amortized O(log n), but poor worst-case.
   • Useful when frequent access to a few elements is expected.
7. Trie (Prefix Tree)
   • Not a comparison-based structure.
   • Used for prefix-based search, autocomplete, dictionary, etc.
   • Time based on length of key (O(L)), not number of elements.

Summary Recommendation

Use Case	Recommended Tree
General-purpose search/insert/delete	Red-Black Tree
Read-heavy, real-time systems	AVL Tree
Frequent access to same keys	Splay Tree
Large-scale databases / disk systems	B-Tree / B+ Tree
Prefix search / autocomplete	Trie
Educational / theory	2-3 Tree / BST