Data Structures

Data Structures Binary Search Tree

Binary Search Trees Introduction  Searching and Insertion  Deletion 

Introduction Definition : The value at a node is greater than every value in the left subtree of the node and is less than every value in the right subtree of the node.

Node

Left

Value at node > Value of left subtree

Right

Value at node < Value of right subtree

Example of a Binary Tree : 38

59

16

9

25

18

45

83

75

Searching and Insertion Value to be searched = 20 38

14

56

8

23 45

82

18 70 20

Algorithm for searching an element FIND(INFO, LEFT, RIGHT, ROOT, ITEM, LOC, PAR) 2. [Tree empty ?] If ROOT=NULL, then: set LOC=NULL and PAR=NULL, and Return 2. [ITEM at ROOT] If ITEM=INFO[ROOT], then set LOC=ROOT and PAR=NULL and Return 8. [Initialize pointers PTR and SAVE.] If ITEM
Contd…

Algorithm for searching an element 6.

If ITEM
Algorithm for insertion of an element INSBST(INFO,LEFT,RIGHT,ROOT,ITEM,LOC,PAR) 2. Call FIND(INFO,LEFT,RIGHT,ROOT,ITEM,LOC,PAR) 3. If LOC╪NULL, then EXIT 4. [COPY ITEM into new node in AVAIL list.] (A) AVAIL=NULL then Write OVERFLOW, and EXIT. (B) Set NEW=AVAIL, AVAIL=LEFT[AVAIL] and INFO[NEW]=ITEM (C) Set LOC=NEW, LEFT[NEW]=NULL and RIGHT[NEW]=NULL. 8. [Add ITEM to Tree] If PAR = NULL, THEN: set ROOT=NEW. Else If ITEM
Deletion of element  



Root node N has no child nodes N has exactly one child node either in left or in the right N has child nodes on both the sides