Page 121 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms Mandeep Kaur, Lovely Professional University

Notes Unit 6: Binary Search Tree and AVL Trees

CONTENTS
Objectives

Introduction
6.1 Binary Search Tree
6.2 Counting the Number of Nodes in a Binary Search Tree
6.3 Searching for a Target Key in a Binary Search Tree
6.4 Deletion of a Node from a Binary Search Tree
6.4.1 Deletion of a Node with Two Children
6.4.2 Deletion of a Node with one Child
6.4.3 Deletion of a Node with no Child
6.5 Application of a Binary Search Tree
6.6 AVL Tree
6.7 Summary
6.8 Keywords
6.9 Self Assessment
6.10 Review Questions
6.11 Further Readings

Objectives

After studying this unit, you will be able to:
z Describe binary search tree
z Explain deletion of node with two child and with single child

z Describe applications of BST

Introduction

Consider the problem of searching a linked list for some target key. There is no way to move
through the list other than one node at a time, and hence searching through the list must always
reduce to a sequential search. As you know, sequential search is usually very slow in comparison
with binary search. Hence, assuming we can keep the keys in order, searching becomes much
faster if we use a contiguous list and binary search. Suppose we also frequently need to make
changes in the list, inserting new entries or deleting old entries.

6.1 Binary Search Tree

A binary search tree is a binary tree which may be empty, and every node contains an identifi er
and

1. Identifier of any node in the left sub-tree is less than the identifier of the root

2. Identifier of any node in the right sub-tree is greater than the identifier of the root and the
left sub-tree as well as right sub-tree both are binary search trees.

116 LOVELY PROFESSIONAL UNIVERSITY