Skip to main content
Engineering LibreTexts

8: Searching, Binary Search Trees and Heaps

  • Page ID
    47925
  • Unit Introduction

    Searching is one of the most fundamental problems in Computer Science. It is the process of finding a particular item in a collection of items. Typically, a search answers whether the item is present in the collection or not. This unit discusses two important search methods: sequential search and binary search. A Sequential (linear) search is the simplest method to solve the searching problem. It finds an item in a collection by looking for it in a collection one at a time from the beginning till the end. Binary Search on the other hand is use a divide and conquer strategy. In divide and conquer, a larger problem is reduced into smaller sub-problems recursively until the problem is small enough that the solution is trivial. A condition for binary search is that the array should be a sorted array.

    The unit also discusses two important data structures; a binary search tree (BST) and a heap. A BST is a binary tree based data structure that is viewed to support efficiently the dynamic set operations, including search and insert operations amongst others. A heap on the other hand is a specific tree based data structure in which all the nodes of tree are in a specific order. The maximum number of children of a node in the heap depends on the type of heap. However, a binary heap is the most commonly used heap type, where there are at most 2 children of a node.

    Unit Objectives

    Upon completion of this unit you should be able to:

    • Demonstrate knowledge of searching algorithms
    • Implement a searching algorithm based on efficiency requirements
    • Demonstrate knowledge of advanced data structures including binary search trees and binary heap
    • Implement a data structure based on efficiency requirements

    Key Terms

    Searching: A process of finding a particular item in a collection of items

    Linear search: A search that sequentially looks for an item in a collection from beginning to the end

    Binary Search: A search based on divide and conquer strategy

    Binary tree: A tree made of nodes, where each node contains a “left” pointer, a “right” pointer, and a data element.

    Binary search tree (BST): A type of binary tree where the nodes are arranged in order, that is, for each node all keys in its left sub-tree are less-or-equal to its key and all the keys in its right sub-tree are greater than its key.

    In-order Traversal (Walk): A BST walk that recursively prints the BST keys in monotonically increasing order

    Red-black trees: A variant of BST that ensure that the tree is balanced, that is, its height is O(lg n), where n is the number of nodes.

    Heap: A specific tree based data structure in which all the nodes of tree are in a specific order.

    Learning Activities

    • Was this article helpful?