Insertion and Deletion in Binary Search Trees (using Arrays and Linked Lists)

1.
(Download file toview animation) Dr. S. Lovelyn Rose PSG College of Technology Coimbatore, India

2.
Algorithm Insert_LinkedList_BST(root, element) *root points to the root element of the linked list * ‘element’ is the element to the inserted * ‘data’ holds the data part of a node * lchild stores the address of the left child * rchild stores the address of the right child * GetNode() is a function that creates a node with a data part and 2 address parts and assigns null in the address parts

3.
1.temp=root; 2 if(root ==null) 3. rootdata = element; Insert as first node 4. Return; 5. end if 6. while(1) Element to be inserted is 4 7. if(tempdata > element) 8. if(templchild == null) 2 temp 9.templchild = GetNode() 10.templchild  data = 1 5 element 10.break; 0 3 8 11.end if

4.
12.else 13.temp = templchild 14.endelse 15.end if 16.else 17.if(temprchild == null) Element to be inserted is 4 18.temprchild = GetNode() 2 temp 19.temprchild  data = element 1 5 20.break; 21.end if 0 3 8

5.
12.else 13.temp = temprchild//Move to the right child 23.end else 24.end if 25.end while 26. end Insert_LinkedList_BST Element to be inserted is 4 2 temp 1 5 0 3 8

6.
Algorithm Delete_LinkedList_BST(root) * rootis a pointer to the root node * ‘data’ holds the data part of a node * lchild stores the address of the left child * rchild stores the address of the right child * temp is used to find the address of the element to be deleted * parent stores the address of the parent of the element to be deleted * inorder_N is the inorder successor * parent_inorder_N is the parent of the inorder successor

7.
//Search for theelement 1. temp = root Element to be 2. parent = root searched is 4 3. while((element != tempdata) && (temp != null)) // Loop until the element is found 4.parent = temp 5 5.if(element < tempdata) 6.temp = temp left // Move left 3 7 7.end if 8.else 9.temp = tempright //Move right 2 4 9 10.end else 11.end while

8.
12. If(temp !=null) temp is a leaf node Element found 13.if((templchild == null) and (temprchild == null)) 14.if(parent == temp) Only one node 15.root = null 16.end if 17. else if(temp == parentlchild) 18. parentlchild = null 5 19. end else if else 21.parentrchild = null 4 7 22.end else 3 23.FreeNode(temp) 24.end if 2 4

9.
// Case 2- Delete node with one child else if((templchild == null)or(temprchild == null)) 26.if(parent == temp) 27.if(templchild != null) 28.root = templchild 29.end if root 30.else 4 31.root = temprchild 32.end else 33.end if 2

10.
else if(temp ==parentlchild) 35.if(templchild != null) 36.parentlchild = templchild 37.end if temp is a left child 38.else 39.parentlchild = temprchild 40.end else 5 41.end else if else 43.if(templchild != null) 4 7 44.parentrchild = templchild 45.end if 46.else 2 9 47. parentrchild = temprchild 48.end else temp is a right child 49.end else if 50.FreeNode(temp) 51.end else if

11.
//Case 3 –Delete node with 2 children 52.else 53.parent_inorder_N = temp 54.inorder_N = tempright subtree 2 55.Repeat steps 56,57 Parent_inorder_N while inorder_Nleft ≠ null 1 6 4 56.parent_inorder_N = inorder_N 57.inorder_N = inorder_N  left inorder_N 58.end Repeat 0 3 5 59.tempdata = inorder_Ndata 60. if(inorder_N rchild == null) 6 61. parent_ inorder_Nleft = null 62. end if

12.
63.else // Inordersuccessor has one child 64. parent_ inorder_Nleft = inorder_Nright 65.end else 66. end else 67.end if 68.else 69.Print “Element not Found” 70.end else 71.end Delete_LinkedList_BST

13.
Algorithm Insert_Array_BST(Tree[1:N], element) *Tree is an array of n elements representing the BST * ‘element’ is the element to the inserted * The empty positions in an array are denoted by -1

14.
12.else 1. temp=1; 2. if(Tree[temp]== -1) 13.temp = 2 * temp 14.end else 3.Tree[temp] = element; 15.end if 4. Return; 16. else 5. end if Insert as first node 17. if(Tree[2 * temp+1] == -1) 6. while(1) To find the position 18.Tree[2 * temp+1] == 7. if(Tree[temp] > element) element child 8. if(Tree[2 * temp] == -1) 19.break; 9. Tree[2 * temp] == element 20.end if 10.break; 11. end if Element to be inserted is 6 10 4 15 -1 -1 6 -1 -1 -1 -1

15.
21. else //The right child is occupied 22.temp = 2 * temp + 1 //Move to the right child 23. end else 24. end if 25. end while 26. end Insert_Array_BST

16.
Algorithm Delete_Array_BST(Tree[1:N], element) * Tree is an array of n elements representing the BST * ‘element’ is the element to the inserted * The empty positions in an array are denoted by -1 * temp is used to find the subscript of the element to be deleted * inorder_N is the inorder successor

17.
//Search for the‘element’ in the BST 1. temp = 1 2. while((Tree[temp]!=element) && (Tree[temp] != -1)) // Loop until the element is found 3.if(element < Tree[temp]) 4.temp = 2 * temp // Move left 5.end if 6. else 7.temp = 2 * temp + 1 //Move right Element to be searched is 4 8. end else 9. end while 10 4 15 -1 -1 -1 -1 temp

18.
10. if(Tree[temp] !=-1) // If the element is found // Case 1 - Delete leaf node 11.if((Tree[2*temp] == -1) and (Tree[2*temp+1] == -1)) 12.Tree[temp] = -1 13.end if 10 -1 4 15 -1 -1 -1 -1 temp

19.
// Case 2- Delete node with one child 14.else if((Tree[2*temp] == -1) or (Tree[2*temp+1] == -1)) 15.if(Tree[2*temp] != -1) // Is the child in the left of temp 16.Call Preorder(Tree[1:N], 2*temp) //Update the whole subtree 17.end if 18.else 19.Call Preorder(Tree[1:N], 2*temp+1) 20.end else 21.end else if 10 4 15 -1 7 -1 -1 -1 -1 temp

20.
//Case 3 –Delete node with 2 children 22.else 23.inorder_N = 2*temp+1 // Inorder successor is surely in the right subtree 24.Repeat steps 48,49 while Tree[2*inorder_N] ≠ -1 25.inorder_N = 2*inorder_N 26.end Repeat 27.Tree[temp] = Tree[inorder_N] // Replace with inorder successor 28.if(Tree[2*inorder_N + 1] == -1) // Inorder successor has no child 29.Tree[inorder_N] = -1 30.end if

21.
31.else // Inordersuccessor has one child 32.Call Preorder(Tree[1:N], 2*inorder_N+1) 33.end else 34.end else 35.end if 36.else 37.Print “Element not Found” 38.end else 39.end Delete_Array_BST

22.
Algorithm Insert_LinkedList_BST(root, element) *root points to the root element of the linked list * ‘element’ is the element to the inserted * ‘data’ holds the data part of a node * lchild stores the address of the left child * rchild stores the address of the right child * GetNode() is a function that creates a node with a data part and 2 address parts and assigns null in the address parts

23.
1.temp=root; 2 if(root ==null) 3. rootdata = element; Insert as first node 4. Return; 5. end if 6. while(1) Element to be inserted is 4 7. if(tempdata > element) 8. if(templchild == null) 2 temp 9.templchild = GetNode() 10.templchild  data = 1 5 element 10.break; 0 3 8 11.end if

24.
12.else 13.temp = templchild 14.endelse 15.end if 16.else 17.if(temprchild == null) Element to be inserted is 4 18.temprchild = GetNode() 2 temp 19.temprchild  data = element 1 5 20.break; 21.end if 0 3 8

25.
12.else 13.temp = temprchild//Move to the right child 23.end else 24.end if 25.end while 26. end Insert_LinkedList_BST Element to be inserted is 4 2 temp 1 5 0 3 8

26.
Algorithm Delete_LinkedList_BST(root) * rootis a pointer to the root node * ‘data’ holds the data part of a node * lchild stores the address of the left child * rchild stores the address of the right child * temp is used to find the address of the element to be deleted * parent stores the address of the parent of the element to be deleted * inorder_N is the inorder successor * parent_inorder_N is the parent of the inorder successor

27.
//Search for theelement 1. temp = root Element to be 2. parent = root searched is 4 3. while((element != tempdata) && (temp != null)) // Loop until the element is found 4.parent = temp 5 5.if(element < tempdata) 6.temp = temp left // Move left 3 7 7.end if 8.else 9.temp = tempright //Move right 2 4 9 10.end else 11.end while

28.
12. If(temp !=null) temp is a leaf node Element found 13.if((templchild == null) and (temprchild == null)) 14.if(parent == temp) Only one node 15.root = null 16.end if 17. else if(temp == parentlchild) 18. parentlchild = null 5 19. end else if else 21.parentrchild = null 4 7 22.end else 3 23.FreeNode(temp) 24.end if 2 4

29.
// Case 2- Delete node with one child else if((templchild == null)or(temprchild == null)) 26.if(parent == temp) 27.if(templchild != null) 28.root = templchild 29.end if root 30.else 4 31.root = temprchild 32.end else 33.end if 2

30.
else if(temp ==parentlchild) 35.if(templchild != null) 36.parentlchild = templchild 37.end if temp is a left child 38.else 39.parentlchild = temprchild 40.end else 5 41.end else if else 43.if(templchild != null) 4 7 44.parentrchild = templchild 45.end if 46.else 2 9 47. parentrchild = temprchild 48.end else temp is a right child 49.end else if 50.FreeNode(temp) 51.end else if

31.
//Case 3 –Delete node with 2 children 52.else 53.parent_inorder_N = temp 54.inorder_N = tempright subtree 2 55.Repeat steps 56,57 Parent_inorder_N while inorder_Nleft ≠ null 1 6 4 56.parent_inorder_N = inorder_N 57.inorder_N = inorder_N  left inorder_N 58.end Repeat 0 3 5 59.tempdata = inorder_Ndata 60. if(inorder_N rchild == null) 6 61. parent_ inorder_Nleft = null 62. end if

32.
63.else // Inordersuccessor has one child 64. parent_ inorder_Nleft = inorder_Nright 65.end else 66. end else 67.end if 68.else 69.Print “Element not Found” 70.end else 71.end Delete_LinkedList_BST

33.
Algorithm Insert_Array_BST(Tree[1:N], element) *Tree is an array of n elements representing the BST * ‘element’ is the element to the inserted * The empty positions in an array are denoted by -1

34.
12.else 1. temp=1; 2. if(Tree[temp]== -1) 13.temp = 2 * temp 14.end else 3.Tree[temp] = element; 15.end if 4. Return; 16. else 5. end if Insert as first node 17. if(Tree[2 * temp+1] == -1) 6. while(1) To find the position 18.Tree[2 * temp+1] == 7. if(Tree[temp] > element) element child 8. if(Tree[2 * temp] == -1) 19.break; 9. Tree[2 * temp] == element 20.end if 10.break; 11. end if Element to be inserted is 6 10 4 15 -1 -1 6 -1 -1 -1 -1

35.
21. else //The right child is occupied 22.temp = 2 * temp + 1 //Move to the right child 23. end else 24. end if 25. end while 26. end Insert_Array_BST

36.
Algorithm Delete_Array_BST(Tree[1:N], element) * Tree is an array of n elements representing the BST * ‘element’ is the element to the inserted * The empty positions in an array are denoted by -1 * temp is used to find the subscript of the element to be deleted * inorder_N is the inorder successor

37.
//Search for the‘element’ in the BST 1. temp = 1 2. while((Tree[temp]!=element) && (Tree[temp] != -1)) // Loop until the element is found 3.if(element < Tree[temp]) 4.temp = 2 * temp // Move left 5.end if 6. else 7.temp = 2 * temp + 1 //Move right Element to be searched is 4 8. end else 9. end while 10 4 15 -1 -1 -1 -1 temp

38.
10. if(Tree[temp] !=-1) // If the element is found // Case 1 - Delete leaf node 11.if((Tree[2*temp] == -1) and (Tree[2*temp+1] == -1)) 12.Tree[temp] = -1 13.end if 10 -1 4 15 -1 -1 -1 -1 temp

39.
// Case 2- Delete node with one child 14.else if((Tree[2*temp] == -1) or (Tree[2*temp+1] == -1)) 15.if(Tree[2*temp] != -1) // Is the child in the left of temp 16.Call Preorder(Tree[1:N], 2*temp) //Update the whole subtree 17.end if 18.else 19.Call Preorder(Tree[1:N], 2*temp+1) 20.end else 21.end else if 10 4 15 -1 7 -1 -1 -1 -1 temp

40.
//Case 3 –Delete node with 2 children 22.else 23.inorder_N = 2*temp+1 // Inorder successor is surely in the right subtree 24.Repeat steps 48,49 while Tree[2*inorder_N] ≠ -1 25.inorder_N = 2*inorder_N 26.end Repeat 27.Tree[temp] = Tree[inorder_N] // Replace with inorder successor 28.if(Tree[2*inorder_N + 1] == -1) // Inorder successor has no child 29.Tree[inorder_N] = -1 30.end if

41.
31.else // Inordersuccessor has one child 32.Call Preorder(Tree[1:N], 2*inorder_N+1) 33.end else 34.end else 35.end if 36.else 37.Print “Element not Found” 38.end else 39.end Delete_Array_BST

42.
Algorithm Preorder(Tree[1:N], root) *Tree is the array holding the tree * root is the subscript of the root node * The empty positions in an array are denoted by -1 1. Tree[ceil(root/2)-1] = Tree[root] 2. Tree[root] = -1 3. if(Tree[2*root] ≠ -1) // A left child exists 4. call Preorder(Tree[], 2 * root) 5. end if 6. if ( Tree[2*root+1] ≠ -1) // Does a right child exist 7. call Preorder(Tree[], 2 * root+1) 8. end if 9. end Preorder

43.
http://datastructuresinterview.blogspot.in/ http://talkcoimbatore.blogspot.in/ http://simpletechnical.blogspot.in/

Insertion and Deletion in Binary Search Trees (using Arrays and Linked Lists)

In this document

More Related Content

What's hot

Viewers also liked

Similar to Insertion and Deletion in Binary Search Trees (using Arrays and Linked Lists)

Recently uploaded

Insertion and Deletion in Binary Search Trees (using Arrays and Linked Lists)