Review Data Structure 10 Maret 2020 (Hashing & Binary Tree)

Hashing and Hash Tables
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