Page 242 - DCAP407_DATA_STRUCTURE

Yadwinder Singh, Lovely Professional University Unit 13: Binary Search Trees

Unit 13: Binary Search Trees

CONTENTS
Objectives

Introduction
13.1 Binary Search Tree Operations
13.1.1 Searching in Binary Search Trees
13.1.2 Inserting in Binary Search Trees
13.1.3 Deleting in Binary Search Trees
13.1.4 Other Operations

13.2 Summary
13.3 Keywords
13.4 Self Assessment
13.5 Review Questions
13.6 Further Readings
Objectives

After studying this unit, you will be able to:
• Explain insertion operation in a binary search tree

• Describe searching operation in a binary search tree
• Explain deletion operation in a binary search tree
• Find the height of a binary search tree
• Determine the minimum and maximum value in a binary search tree
• Write a C function to count the leaves and nodes of a binary search tree
Introduction

You have already learnt about binary trees. The disadvantage of binary trees is that data is stored in
these trees in any order and hence, the time taken to search these trees is longer. Search trees are data
structures that support many dynamic-set operations such as searching, finding the minimum or
maximum values, insertion, and deletion. Binary search trees, AVL trees and B+ trees are examples of
search trees.
A binary search tree (BST) has binary nodes. In a binary search tree, for a given node with value n, each
node to the left has a value lesser than n and each node to the right has a value greater than n. This
applies recursively down the left and right sub-trees.

LOVELY PROFESSIONAL UNIVERSITY 235