Hashing Table, Tree, and Binary 101

                           On the previous post, we have already discussed about the concept of Stack and Queue, how they are different from one another, and how they work according to their own operations. Now we are going to continue with our next discussion topic regarding the concept of Hasing Table, Tree and Binary. These are basically are important data structures that came in a different kind of approach. In order to cover the basics, let us jump into the discussion.

Hashing
                            Hashing is used due to it's fast capability of finding item using a more simpler term called the "key", instead of finding it by searching the original value of the item. This technique distributes keys in an array called a hash table (the place to store the original string), while utilizing function called hash function. See the picture below for an example of hash table:

•         The Concept           

                            A technique of transforming a string of characters into a shorter length value (or also called as "key") that potrays the original string, so that the "key" can be stored and retrieved quickly.

•         The Hash Function           

                            Here are some of important methods of hash function:

• Mid-square: squaring the string/identifier, then extract the middle r bits from the previous result of squaring.
• Division: dividing the string/identifier with modulus operator.
• Folding: splitting the string/identifier into several parts, then joins the individual parts together to get the hash key.
• Digit Extraction: collecting several digits from predefined as the hash address.
• Rotating Hash: using other hash method (division or mid-square), then do rotation to the obtained hash address by switching the position of the digits to form a new hash address.

•         Collision           

                            A problem which occurs because there exists more than one data that are stored into same keys. There are two ways to handle collisions, such as:

• Linear Probing: search the next empty slot and put the string there (but it has bad search complexity if there are great number of collisions happens). See the picture below for reference:
  

• Chaining: store the string into a slot as a chained list. See the picture below for reference:
  

Tree

                            A non-linear data structure showing hierarchical relationship among data, which relations can be observed in directory structures or organizational hierarchies. It is not necessary to store the node contiguously, since it can be stored anywhere and linked by pointers.

•         The Concept           

• Root: Node at the top.
• Edge: A line connecting the parent to the child.
• Leaf: Nodes that do not have children.
• Sibling: Nodes that have the same parent.
• Degree of node: The total sub tree of the node.
• Height/Depth: The maximum degree of nodes in a tree.
• If   P--------Q , therefore: 
• P = ancestor of Q. 
• Q = descendant of P.

•         Binary Tree           
•         The Concept           

                            A rooted tree data structure which each node has at most two children, who usually distinguished themselves as left children and right children. Node with no child is called Leaf.

•         Types of Binary Tree          
• Perfect Binary Tree: Binary tree same depth of  every level.

• Complete Binary Tree: Just like Perfect Binary Tree, except the last is completely filled and all nodes are as far left as possible.

• Skewed Binary Tree: Binary tree with each node has one child at most.

• Balanced Binary Tree: Binary tree with no leaf farther away from the root than any other leaf.

That is all the basics about Hashing Table, Tree and Binary, all related problems, steps on how to encounter them, along with their examples.

- END -

References:

S. Sridhar. 2015. Design and Analysis of Algorithms. Oxford University Press. New Delhi. ISBN: 9780198093695. Chapter 5 & 10

Reema Thareja. 2014. Data structures using C. Oxford University Press. New Delhi. ISBN:9780198099307. Chapter 9 & 15

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein. (2009). Introduction to Algorithms. 03. The MIT Press. London. ISBN: 9780262033848. Chapter 11

https://visualgo.net/en/hashtable?slide=1 

http://cslibrary.stanford.edu/110/BinaryTrees.html

https://www.geeksforgeeks.org/hashing-data-structure/