Posts

AVL Tree

Image
   Today let's talk about what an AVL tree is.  An AVL tree is a subtype of the binary search tree. Named after it's inventors Adelson, Velskii, and Landis, and that's how they made the name AVL, taken by their initials. AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees. Here are the operations of an AVL tree: Insertion Deletion Insertion    Inserting a new node can cause the balance factor of some node to become 2 or -2. In that case, we fix the balance factors by use of rotations. Also, only the heights of the nodes on the path from the insertion point to the root can be changed. So, after inserting, we go back up to the root and update heights of the nodes and if we find any node with a balance factor of 2 or -2, we fix it by rotation. There are two rotations, which are the left rotation and the right rotation.    Here are steps to follow for insertion:    ...
Post a Comment
Read more

Hash Table

   Today, I am going to explain about hash tables. If you are still confused about hashing, you can go and check my "Hashing and Binary Tree" post/blog. Well then, let's get started.    Hash table is a data structure that stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.  Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash table uses an array as a storage medium and uses the hash technique to generate an index where an element is to be inserted or is to be located.    The hashing technique may be used to create an already used index of the array. In such a case, we can search the next empty location in the array by looking into the next cell until we find an empty cell. This technique is called linear pr...
Post a Comment
Read more

Hashing and Binary Tree

Hashing    What is hashing? Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find the item using the shorter hashed key than o find it using the original value. It is also used in many encryption algorithms.    The hashing algorithm is called the hash function. The hash function is used to index the original value or key and then used later each time the data associated with the value or key is to be retrieved. A good hash function also should not produce the same hash value from two different inputs. If it does, this is known as a collision and must be handled using some collision handling technique. Following are the ways to handle collisions: Chaining : The idea is to make each cell of hash table point to a linked list of records that have the same hash function value. Chaining is si...
Post a Comment
Read more