Hashing
-Hashing is a technique used for storing and retrieving keys in a rapid manner.
-In
hashing, a string of characters are transformed into a usually shorter 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
item using shorter hashed key than to find it using the original value.
-Hashing
can also be defined as a concept of distributing keys in an array called a hash
table using a predetermined function
called hash
function.
Hash Table
-Hash
table is a table (array) where we store the original string. Index of the table
is the hashed key while the value is the original string.
-The
size of hash table is usually several orders of magnitude lower than the total
number of possible string, so several string might have a same hashed-key.
Hash Function
There
are many ways to hash a string into a key. The following are some of the
important methods for constructing hash functions.
-Mid-square
-Division (most common)
-Folding
-Digit Extraction
-Rotating Hash
Trees & Binary Tree
Tree Introduction
-A
tree is a non-linear data structure that represents the hierarchical
relationships among the data objects
-Some
of the tree relations can be observed in directory structures or organizational
hierarchies.
-The
node in the tree need no to be stored contiguously and can be stored anywhere
and linked by pointers
Tree
Concept
Tree
is a
collection of one or more nodes.
-Node
at the top is called as root.
-A
line connecting the parent to the child is edge.
-Nodes
that do not have children are called leaf.
-Nodes
that have the same parent are called sibling.
-Degree of
node is the total sub tree of the node.
-Height/Depth
is
the maximum degree of nodes in a tree.
-If
there is a line that connects p to q, then p is called the ancestor of
q, and q is a descendant of
p.
Tree Example
DEGREE of TREE = 3
DEGREE of C = 2
HEIGHT = 3
PARENT of C = A
CHILDREN of A = B, C, D
SIBLING of F = G
ANCESTOR of F = A, C
DESCENDANT of C = F, G
Binary
Tree Concept
-Binary
tree is a rooted tree data structure in which each node has at most two children.
-Those
two children usually distinguished as left child and right child.
-Node
which doesn’t have any child is called leaf.
Type
of Binary Tree
-PERFECT
binary tree is a
binary tree in which every level are at the same depth.
-COMPLETE
binary tree is a
binary tree in which every level, except possibly the last, is completely
filled, and all nodes are as far left as possible. A perfect binary tree is a
complete binary tree.
-SKEWED
binary tree is a
binary tree in which each node has at most one child.
-BALANCED
binary tree is a
binary tree in which no leaf is much farther away from the root than any other
leaf (different balancing scheme allows different definitions of “much
farther”).
Advantages
-It
enables linear traversal of elements in the tree
-Linear
traversal eliminates the use of stacks which in turn consume a lot of memory
space and computer time
-It
enables to find the parent of a given element without explicit use of parent
pointers
-Since
nodes contain pointers to in-order predecessor and successor, the threaded tree
enables forward and backward traversal of the nodes as given by in-order
fashion
source:
-ppt
