Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt
You are on page 1/ 21
SRM INSTITUTE OF SCIENCE
AND TECHNOLOGY
DATA STRUCTURES AND ALGORITHMS (18CSC162J)
UNIT IV SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
TOPICS TO BE COVERED ⮚ COMPLETE BINARY TREE AND ITS HEIGHT ⮚ BINARY SEARCH TREE INSERTION DELETION AND SEARCHING SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
INTRODUCTION TO BINARY TREE
⮚ WHAT IS BINARY TREE? ⮚ COMPLETE BINARY TREE AND ITS HEIGHT SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
• WHAT IS BINARY TREE?
• A BINARY TREE IS A TYPE OF TREE DATA STRUCTURE IN WHICH EACH NODE CAN HAVE AT MOST TWO CHILD NODES, KNOWN AS THE LEFT CHILD AND THE RIGHT CHILD. SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
• TYPES OF BINARY TREE
• FULL BINARY TREE • COMPLETE BINARY TREE FULL BINARY TREE THE TREE CAN ONLY BE CONSIDERED AS THE FULL BINARY TREE IF EACH NODE MUST CONTAIN EITHER 0 OR 2 CHILDREN BINARY TREE • THE HEIGHT OF A NODE IN A BINARY TREE IS THE LARGEST NUMBER OF EDGES IN A PATH FROM A LEAF NODE TO A TARGET NODE • THE DEPTH OF A NODE IN A BINARY TREE IS THE TOTAL NUMBER OF EDGES FROM THE ROOT NODE TO THE TARGET NODE.
Example PERFECT BINARY TREE VS COMPLETE BINARY TREE:
• A BINARY TREE OF HEIGHT ‘H’ HAVING THE MAXIMUM NUMBER OF NODES IS
A PERFECT BINARY TREE. FOR A GIVEN HEIGHT H, THE MAXIMUM NUMBER OF NODES IS 2H+1-1. • A COMPLETE BINARY TREE OF HEIGHT H IS A PERFECT BINARY TREE UP TO HEIGHT H-1, AND IN THE LAST LEVEL ELEMENT ARE STORED IN LEFT TO RIGHT ORDER. • EXAMPLE 1: EXAMPLE 2:
1 = 7. • COMPLETE BINARY TREE SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
• COMPLETE BINARY TREE
THE COMPLETE BINARY TREE IS A TREE IN WHICH ALL THE NODES ARE COMPLETELY FILLED EXCEPT THE LAST LEVEL. IN THE LAST LEVEL, ALL THE NODES MUST BE AS LEFT AS POSSIBLE. IN A COMPLETE BINARY TREE, THE NODES SHOULD BE ADDED FROM THE LEFT. SRM INSTITUTE OF SCIENCE AND TECHNOLOGY COMPLETE BINARY TREE
• CREATION OF COMPLETE BINARY TREE
ALGORITHM
STEP 1: INITIALIZE THE ROOT WITH A NEW NODE WHEN THE TREE IS EMPTY.
STEP 2: IF THE TREE IS NOT EMPTY THEN GET THE FRONT ELEMENT
IF THE FRONT ELEMENT DOES NOT HAVE A LEFT CHILD THEN SET THE LEFT CHILD TO A NEW NODE
IF THE RIGHT CHILD IS NOT PRESENT SET THE RIGHT CHILD AS A NEW NODE
STEP 3: IF THE NODE HAS BOTH THE CHILDREN THEN POP IT FROM THE QUEUE.
STEP 4: ENQUEUE THE NEW DATA.
SRM INSTITUTE OF SCIENCE AND TECHNOLOGY COMPLETE BINARY TREE
• ILLUSTRATION
• STEP 1 STEP 2 STEP 3
STEP 4 COMPLETE BINARY TREE
• PROPERTIES OF COMPLETE BINARY TREE
• A COMPLETE BINARY TREE IS SAID TO BE A PROPER BINARY TREE WHERE ALL LEAVES HAVE THE SAME DEPTH.
• IN A COMPLETE BINARY TREE NUMBER OF NODES AT DEPTH D IS 2D.
• IN A COMPLETE BINARY TREE WITH N NODES HEIGHT OF THE TREE IS LOG(N+1).
• ALL THE LEVELS EXCEPT THE LAST LEVEL ARE COMPLETELY FULL SRM INSTITUTE OF SCIENCE AND TECHNOLOGY BINARY SEARCH TREE (BST)
• A BINARY SEARCH TREE FOLLOWS SOME ORDER TO ARRANGE THE ELEMENTS. IN A
BINARY SEARCH TREE, THE VALUE OF LEFT NODE MUST BE SMALLER THAN THE PARENT NODE, AND THE VALUE OF RIGHT NODE MUST BE GREATER THAN THE PARENT NODE. • OPERATIONS: INSERT, SEARCH, DELETE SRM INSTITUTE OF SCIENCE AND TECHNOLOGY EXAMPLE OF CREATING A BINARY SEARCH TREE
• SUPPOSE THE DATA ELEMENTS ARE - 45, 15, 79, 90, 10, 55, 12, 20, 50 STEP 1 - INSERT 45 STEP 2 - INSERT 15 STEP 3 - INSERT 79 STEP 4 - INSERT 90 SRM INSTITUTE OF SCIENCE AND TECHNOLOGY EXAMPLE OF CREATING A BINARY SEARCH TREE
• STEP 6 - INSERT 55 STEP 7 - INSERT 12
STEP 8 - INSERT 20 SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
EXAMPLE OF CREATING A BINARY SEARCH TREE
STEP 9 - INSERT 50 SRM INSTITUTE OF SCIENCE AND TECHNOLOGY INSERTION OF A NEW NODE IN TO A BINARY SEARCH TREE
Insert (TREE, ITEM)
Step 1: IF TREE = NULL Allocate memory for TREE SET TREE -> DATA = ITEM SET TREE -> LEFT = TREE -> RIGHT = NULL ELSE IF ITEM < TREE -> DATA Insert(TREE -> LEFT, ITEM) ELSE Insert(TREE -> RIGHT, ITEM) [END OF IF] [END OF IF]
Step 2: END SRM INSTITUTE OF SCIENCE AND TECHNOLOGY SEARCHING OF NODE IN BINARY TREE
Search (ROOT, ITEM)
Step 1: IF ROOT -> DATA = ITEM OR ROOT =
NULL Return ROOT ELSE IF ROOT < ROOT -> DATA Return search(ROOT -> LEFT, ITEM) ELSE Return search(ROOT -> RIGHT,ITEM) [END OF IF] [END OF IF] Step 2: END SRM INSTITUTE OF SCIENCE AND TECHNOLOGY DELETION OF A NEW NODE IN A BINARY TREE
The node to be deleted is a leaf node
Delete (TREE, ITEM) Step 1: IF TREE = NULL Write "item not found in the tree" ELSE IF ITEM < TREE -> DATA Delete(TREE->LEFT, ITEM) ELSE IF ITEM > TREE -> DATA Delete(TREE -> RIGHT, ITEM) ELSE IF TREE -> LEFT AND TREE -> The node to be deleted has only one child RIGHT SET TEMP = findLargestNode(TREE -> LEFT) SET TREE -> DATA = TEMP -> DATA Delete(TREE -> LEFT, TEMP -> DATA) ELSE SET TEMP = TREE IF TREE -> LEFT = NULL AND TREE -> The node to be deleted has two children RIGHT = NULL SET TREE = NULL ELSE IF TREE -> LEFT != NULL SET TREE = TREE -> LEFT ELSE SET TREE = TREE -> RIGHT [END OF IF]
