Week 7 - Binary Search

Introduction

• Course: SET08122: Algorithms & Data Structures

• Instructor: Md Zia Ullah

• Contact: m.ullah@napier.ac.uk

• University: Edinburgh Napier University, School of Computing

Objectives

• Understand Hierarchical Data Structures: Trees, Binary Trees, and Binary Search Trees (BST)

• Design and implement a BST

• Basic operations on a BST: Traverse, Search, Insert, Delete

• Analyze BST's time complexity

• Extra study: Huffman coding for data compression using a BST

Trees: Hierarchical Data Structures

• A tree consists of nodes, with the topmost node called the root.

• Each node can have multiple children; the maximum number defines the tree's branching factor.

• Nodes without children are referred to as leaf nodes.

• Ancestors and descendants: a node's ancestors include itself up to the root; descendants are all nodes below.

Binary Trees (BT)

• Definition: A binary tree is either empty or consists of a root and two subtrees (left and right).

• Structure:

  • Root contains an element.

  • Left and right subtrees are distinct binary trees.

Binary Search Trees (BST)

• Characteristics:

  • Data is structured for efficient searching, insertion, and deletion.

  • Node rules:

    • Left of root: smaller values.

    • Right of root: larger values.

• Recursion applies to support tree structure.

Basic Operations on Binary Trees

• Traversal Options: Preorder, Inorder, Postorder

• Searching: Traverse to find an element using BST properties.

• Insertion:

  • If empty, create the root.

  • Insert left if less than or equal to parent; otherwise, insert right.

Traversal Techniques

• Preorder:

  • Visit root, then left subtree, then right subtree.

  • Implementation example presented.

• Inorder:

  • Visit left subtree, then root, then right subtree.

  • Implementation example presented and shows result in sorted order for BSTs.

• Postorder:

  • Visit left subtree, then right subtree, then root.

  • Implementation example presented.

Height of a Tree

• Definition: the number of edges on the longest simple downward path from the root node to the leaf node

  • Null tree (zero node) = -1

  • Zero level (1 node) = 0

  • one level (3 nodes) = 1

  • two levels (7 nodes) = 2

  • Three levels (15 nodes) = 3

  • Four levels (31 nodes) = 4

• Recursive algorithm:

  int height(Node root) { 
  	if(root == null)
  		return -1;
  	int hl = height(root.left); 
  	int hr = height(root.right); 
  	return 1 + Math.max(hl, hr);
  }

Basic Operations on Binary Tree

• Searcg, minimum, maximum, successor, predecessor

• Insertion

• Deletion

Searching in a BST

TREE-SEARCH (Node root, int target) {
	if root == null or target == root.data
		return root
	if target < root.data
		return TREE-SEARCH (root.left, target)
	else
	return TREE-SEARCH (root.right, target)

Minimum in a BST

TREE-MINIMUM (Node x){
	while x.left≠null
		x = x.left
	return x
}

Successor in a BST

TREE-SUCCESSOR (Node x){
	if x.right ≠ null
		return TREE-MINIMUM(x.right)
	else
		y = x.parent
		while y ≠ null and x==y.right
			x = y
			y = y.parent
		return y
}

Checking if a BST contains an Item

boolean contains(Node root, int target){
	if(root == null){
		return false;
	}
	else{
		if(target == root.data)
			return true;
		else{
			if(target < root.data)
				return contains(root.left, target);

		    }
	     }
}

Inserting an Element to a BST

• Step 1

  • If a BST is empty - Create a root node with the new element

  • else - locate the parent node for the new element node

• Step 2

  • if the new element is less than or equal to the parent element, the node for the new element becomes the left child of the parent

• Step 3

  • If the new element is greater than the parent element - the node for the new element becomes the right child of the parent

private Node insert(Node root, int data) {
	if (root==null) {
		root = new Node(data);
	}
	else {
		if (data <= root.data) {
			root.left = insert(root.left, data); 
			root.height = max(height(), 1 + height(left));
}

	else {
	root.right = insert(root.right, data);
	root.height = max(height(), 1 + height(right));
	}

	}

	return(root);

}

Deleting Element in a BST

• To delete an element from a binary tree, first locate the node containing the element and its parent node.

  • Let current point to the node with the element in the BST and parent to its parent.

  • Determine whether the current node is a left or right child of the parent.

    Consider the two cases that arise from the position of the current node.

1. Case 1

   • The current node does not have a left child

   • Simply connect the parent node with the right child of the current node

   • Example:

     • to delete node 10 connect the parent of node 10 with the right child of node 10

2. Case 2:

   • The current node has a left child

   • let the rightMost point to the node that contains the largest element in the left subtree of the current node and parentOfRightMost point to the parent node of the rightMost node of the current node

   • Note that the rightMost node cannot have a right child but may have a left child

   • Replace the element value in the current node with the one in the rightMost node, connect the parentOfRightMost node with the left child (if any) of the rightMost node, the delete the rightMost node

Time Complexity Analysis

• Traversal (Inorder, Preorder, Postorder): O(n)

• Searching, Insertion, Deletion: dependent on tree height

  • Worst-case height: O(n) (unbalanced tree)

  • Best-case height: O(log2n) (balanced tree) - efficiency

Huffman Coding

• Purpose: Data Compression

• Uses a binary tree (Huffman tree) to encode frequent characters with fewer bits.

• Process involves creating trees based on character frequency using a greedy algorithm.

• Example: 'Mississippi' character to code frequency.

Conclusion

• Efficient data structures and algorithms are essential for effective data management and processing. Understanding and implementing BSTs and their operations, along with concepts such as Huffman coding, enables better performance in software development.