• USA : +1 973 910 5725
  • INDIA: +91 905 291 3388
  • info@tekslate.com
  • Login

Binary search tree in Data Structures

Binary search tree

 

A binary search tree is a binary tree that may be empty A no-empty binary search tree in data structures satisfy the following properties :

  • Every element has a key(or value), and no two elements have the same key; Therefore, all keys are distinct.
  • The keys(if any) is the left subtree of the root are smaller than the key in the root.
  • The keys(if any) in the right sub tree of the root are larger than the key in the root.
  • The left and right sub trees at the root are also binary search trees.

58

 

 

Searching BST :

  • If we are searching for 15, Then we are done
  • If we are searching a key<15, Then we should search in the left sub tree
  • If we are searching for a key > 15, then we should search in the right sub tree

 

59

 

 

 

Search for 9:

  1. compare 9: 15(The root), goto left sub tree;
  2. Compare 9: 6,go to right sub tree.
  3. compare 9: 7, go to right sub tee
  4. compare 9: 9, found it

 

Insertion operation

Algorithm:

  1. perform search for value x
  2. search will end at node y(if x not in tree)
  3. if x<y, insert new leaf x as new left sub tree for y
  4. if x>y, insert new leaf x as new right sub tree for y.

 

observations :

  • 0(long(n)) operation for balanced tree
  • Insertion may unbalance tree.

 

47

 

10<20. right

30>20, left

25>20, left

insert 20 on left

Example :

instruct a binary search tree with the following elements.

12,5,18,2,9,15,19,13,17

And traverse the binary search tree in zn order, preorder, post order

 

60

 

 

 

Preorder : 12      529   1815131719

In order: 259       12     1315171819

Post order:295             131715191812

 

Deletion operation :

For element removal we consider the three possibilities for the node P that contains the element to be removed.

 

  • P is a leaf
  • P has exactly one nonempty sub tree
  • P has exactly two non empty sub tree

Case 1:

         First cape is handled by discarding the  root, The root is set to null.

61

Case 2:

Next consider the case when the element to be removed is in ia node P that has only one non empty sub tree. IF P has no parent (i.e it is root), The root of its single sub tree becomes the new search tree root. IF p has a parent pp, then we change the pointer from PP so that it points to p’s only child.

ex : Delete 5

62

 

Case 3:

Finally, to remove an element in a node that has two no empty sub trees, we replace this element with either the largest element in its left sub tree or the smallest element in its right sub tree.

Following this replacement, the replacing element is removed from its original node

Ex : Deleting 50

 

63

 

 

 

 

“At TekSlate, we are trying to create high quality tutorials and articles, if you think any information is incorrect or want to add anything to the article, please feel free to get in touch with us at info@tekslate.com, we will update the article in 24 hours.”

0 Responses on Binary search tree in Data Structures"

Leave a Message

Your email address will not be published. Required fields are marked *

Site Disclaimer, Copyright © 2016 - All Rights Reserved.