BINARY SEARCH TREE

BINARY SEARCH TREE




SEARCHING

Always starts from the root, compare the data stored with the key we are searching for. If the data is less than the key value, search in the left subtree otherwise search in the right subtree.a binary search tree can reduce the search time to O(n).

Algorithm

 
If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

INSERTION

Start from the root and go down searching for a proper location. If the data is less than the key search for empty location in the left subtree, otherwise searh for empty location in the right subtree. Insert the data if the data that want to be insert is not in the tree (NULL), won't insert duplicates.

Algorithm

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
 
end If

DELETION

Deleted node is replaced by bottom most and rightmost node. There is no order among elements, so replace it with last element. If the node has only one child the way to delete is the same with linked list.
A node to be deleted :
  • is not in a tree
  • is a leaf
  • has only one child
  • has two children

Algorithm
  1. Starting from the root, find the deepest node in binary tree and the node that we want to delete.
  2. Replace the deepest node with node to be deleted.
  3. Then delete the deepest node.





Comments

Post a Comment

Popular posts from this blog

Hash Table and Binary Tree

HASH TABLE Hash Table is a data structure that stores data. It is  consist of 2 parts:  An array format (generally array of Linked List) where we keep the data with special index value.   A hash function that help us to decide wherein the inputted data could be saved. Access of data will be very fast if we know the index of the wanted data.  The efficiency of mapping itself relies upon on how fast the hash function is. Hashing is implemented in 2 steps:  An element is converted into an integer by the usage of a hash function. This element may be used as an index to keep the original, which falls into the hash table. The element is stored in the hash table where it may be fast retrieved by the use of hashed key. Cryptographic Hash Functions A cryptographic hash function is a unique class of hash functions that has numerous properties making it ideal for cryptography. There are certain properties that a cryptographic hash func...
Read more

RANGKUMAN

RANGKUMAN Link ed List Linked List adalah struktur data linear, pada Linked List terdapat nodes / sekumpulan data yang bersambungan dimana setiap node menunjuk node yang lain dengan pointer. Single Linked List Single Linked List adalah Linked List yang hanya menggunakan satu pointer untuk menghubungkan satu node dengan node lainnya sehingga pada Single Linked List pointer hanya bisa bergerak satu arah saja. Single Linked List diawali dengan head untuk menyimpan alamat awal dan diakhiri dengan node yang pointernya mengarah ke NULL. Double Linked List Double Linked List adalah Linked List yang memiliki dua pointer yaitu head dan tail. Pointer head adalah pointer yang menunjuk ke node pertama dan pointer tail adalah pointer yang menunjuk ke node paling terakhir. Pada Double Linked List juga terdapat next untuk menunjuk ke node selanjutnya dan prev untuk menunjuk ke node sebelumnya sehingga  pointer pada Double Linked List bisa bergerak dua arah. Hash Table Ha...
Read more