Data Strucrure:Hash Table

This is also called as Direct address table.If we have a collection of n elements,whose Keys are Unique integers in the range 1 to m. Where m>=n,then we can store the items in a DAT,T where Ti is either empty or contains one of the elements of our collection.

The range of the key determines ,the size of hash table. Actually in addition to the Key,may also contain other information.Whenever an element is placed in the DAT,that key is used to determine its position.Whenever a search for a given element is performed.

To,search for a key,say K in a hash table.We can access it directly as the Kth element (tk). If hash table contains this element ,it returns it,otherwise it return NULL Value.

Clearly,it can be viewed that searching a direct address table is an 0(1) operation.The two requirements of a Direct address table are;
(a) The Keys must be Unique and,
(b) The range of key must be severely bounded.

Direct addressing can be generalized to a situation where a function H(k) maps to K to a value in the range 10 to m. That is , H(K)==>[1,m] we place the elements in T[H[k]] rather than T[K] and we can search in 0(1) time as before .This indicates that keys need not in the range 1 to m.

Hashing Techniques

Hashing in Data Strucrures:

Hashing is another important search technique that available for searching which is virtually independent of the size of the space being searched.frequently,an application will need to search a key item for a collection of items(or records).
Mainly This hashing techniques transforms the search key item into an address of that item in a table called LOOK_UP_TABLE or HASHTABLE or DIRECTADDRESSTABLE.The transformation is generally carried out by Hashfunction.The maintainance of hashfunction is called HASHTABLE.

Traversing A Binary Tree

Traversing a tree means that processing is so that each node is visited exactly once. A binary tree can be traversed n number ways. They differ primarily In the order In which they visit the nodes. The most common three traversals are
1.Pre-order
2.In-order
3.Post-order

Binary trees , like self-referential structures, are inherently recursive n nature. That is , any given node of a tree can itself be viewed as the root of another tree. That makes the use of recursive calls relatively straightforward for working with trees.

PRE-ORDER:
Pre-order is traversing a tree n the order: root left right
The following is the procedure for pre-order:
1.Visit the root.
2.Traverse the left sub-tree In pre-order.
3.Traverse the right sub-tree n pre-order.

IN-ORDER:
In-order is traversing a tree In the order: left root right
The following is the procedure for In-order:
1.Traverse the left sub-tree In In-order.
2.Visit the root.
3.Traverse the right sub-tree In In-order.

POST-ORDER:
Post-order is traversing a tree in the order: left right root
The following is the procedure for Post-order:
1.Traverse the left sub-tree in Post-order.
2.Visit the root.
3.Traverse the right sub-tree in Post-order.