Linked List In Data Structures

Flat Chain or Linked List is one form of data structure, containing a collection of data (nodes) arranged in connection
connect, dynamic and limited.
Linked List are connected with the help of a pointer variable
Each data in Linked List called the node (node)
which occupies a dynamic memory allocation and usually in the form
struct that consists of several fields.
Linked List or Flat-chain can be illustrated as
one unit train.
The train consists of several cars, each of the car is called the formation of the data type (struct).
In order for these cars can be linked to each other is needed
at least a hook that is called as a pointer.
After declaring data types and pointers on the list, then we will try to make a list (linked list) is not a single spin or a car. There are some operations that we can make on the list, including: add, delete and edit of these cars.
The essence of Linked list is a process (add, edit, delete) from car / node and how to connect between the carriage / node is .....

moore....

Tree In Heap sort

In Heap Sort Tree
2.1 Definition of Heap
Is a data structure that meets the tree-shaped nature of the heap that is, if B is a child of A, then the value stored at node A is greater than or equal to the value stored at node B. This causes the element with the largest value is always located at the root position, and the heap is called a max heap. (If the comparison is diterbalikkan smallest element always at the root node, the heap is called the min heap). Therefore, the heap used to implement queue prioriti. Operations that are used for the heap are:
• Delete-delete-max or min: remove the root node of a max or min heap.
• Increase or decrease-key-key: change the value stored in a node.
• Insert: add a value into the heap.
• Merge: merge two heap to form a new heap which contains all the elements forming the heap.

Graf In Data Structures

Graf is used to represent discrete objects
and the relationship between these objects.

Graf Types
Based on the presence or absence of a bracelet or double side on a graph,
then the graph is classified into two types:

1. Simple graph (simple graph).
Graph does not contain a bracelet and double-side is called
simple graph.

2. Graf-no simple (unsimple-graph).
Graph which contains the so-called dual or bracelet graph
not-simple (unsimple graph).

• Based on the number of nodes in a graph, then the general graph
can be classified into two types:

1. Graf finite (limited graph)
is a graph of the number of the knot, n, finite.

2. Graf an infinite (unlimited graph)
Graph of the number of the knot, n, no finite number of
called an infinite graph.

• Based on the orientation direction, the general graph in
distinguish the 2 types:

1. Non-directional graph (undirected graph)
Graph which side do not have direction orientation is called graph
non-directional.

2. Directed graph (directed graph or digraph)
Graph that each side is given the orientation direction is called a
as a directional graph.

Example
Graf in its application:
Electrical circuits, chemical compounds of carbon Isomers etc..

moore....

Tree In Data Structure

In Data Structures, Tree is one of the data structure
shaped like a tree, which consists of attack
series node (node) of each node is berhubungan.Node-in
vektor.Setiap connect by a node can have 0 or
more child nodes (child). A node that has a child node in -
call the parent node (parent). A child node has only one
parent node. By convention computer science, Tree growing
down, not like in the real world tree that grows up.
Thus the child node will be described under the node
induknya.Node in the base of the tree is called the root node (the root),
while the node is located at the tip of tree pyramid is called
leaf node (leaf).

Binary Tree (Binary Tree)
In the course of data structures, will be specifically studied
finger on the binary tree. Binary tree is a tree that
each knot can only have a maximum of 2 (two)
No child node lebih.Pada binary tree, generally two
child node is called the position, the left and right.
Some terms in the binary tree:
- Size (size): the total number of existing nodes in binary tree.
- Depth (depth): the long path that connects a
node to node until the very end of her child (leaf).
Depth is often called height.Full Binary Tree (Full Binary Tree)
is a binary tree each nodenya has 0 or 2 child nodes.

Perfect Binary Tree
(Binary Tree Perfect) is a binary tree of all nodes leafnya
is at a depth of samadari root node. Also called
as a Complete Binary Tree (Complete Binary Tree)

Almost Complete Binary Tree
(Almost Complete Binary Tree) is a binary tree of each
0 node nodenyadapat have children, or have left, or if
has a right to have kiri.Tidak should have the right course.
Implementation of programming, in this subject will be in
discussed for binary trees only. Initial assumption is that the data
to be inserted in the node, an integer data type.

Stack the Data Structure

Stack or stack is a data structure that seems to look like the data that is composed of 'stacking', where there is data that is located above the other data.
Stack stack or arrangement is LIFO (Last In First Out), means the last incoming data will be out first.
for example in daily life, among others:
Piles of books, piles of coins, etc..

There are two basic operations in use at the Stack:
Push function to add data on STACK on top of the pile
Pop works taking data on STACK at the top
http://www.ziddu.com/download/8190571/Stack.rar.html

Heap Sort

The tree diagram in Heap SortUnderstanding Heap is a data structure that meets the tree-shaped nature of the heap that is, if B is a child of A, then the value stored at node A is greater than or equal to the value stored at node B. This causes the element with the largest value is always located at the root position, and the heap is called a max heap. (If the comparison is diterbalikkan smallest element always at the root node, the heap is called the min heap). Therefore, the heap used to implement the priority queue. Operations that are used for the heap are:
• Delete-delete-max or min: remove the root node of a max or min heap.• Increase or decrease-key-key: change the value stored in a node.• Insert: add a value into the heap.• Merge: merge two heap to form a new heap which contains all the elements forming the heap.
.2 Heap Types
.2.1 Binary heapis the heap created by using binary trees.
.2.2 Binomial heapis the heap created by using the binomial tree.
Binomial tree is defined recursively if is:• A binomial tree with height 0 is a single node• A binomial tree with height k has a root node whose children are the roots of the binomial trees.
.2.3 Fibonacci HeapFibonacci heap is a collection of trees that form the minimum heap.Trees in this data structure does not have a specific shape and in extreme cases this heap contains all the elements in a different tree or a single tree with a height advantage ofFibonacci heap is a heap enough when combined with the combining of two lists of trees.
Heap SORTHeap Sort is a sorting algorithm based on comparative data, and selection are among the sort. Although slower than quick sort in most machines, but the heap sort has the advantages of the complexity of the algorithm in the worst case is n log n.Heap sorting algorithm of this sort to sort the contents of an array of inputs by looking at the array input as a Complete Binary Tree (CBT). After the Complete Binary Tree (CBT) can be converted into a heap tree. After the Complete Binary Tree (CBT) is changed into a priority queue.Heap sorting algorithm starts from building a heap of data collection to be ordered, and then delete the data that has the highest value and placing it in the end of the array which has been ordered. After moving the data with the largest value, the next process is to rebuild the heap and move the greatest value on the heap and put it in last place in the sorted array of other data not specified. This process is repeated until no more data left in the heap and the sorted array is full. In our implementations require two arrays - one to store the heap and one for storing data that is sorted. But for memory optimization, we can use only one array only. That is the way to exchange the contents of the root with the last element in the heap tree. If the memory is not a problem it can be fixed using two rows of input array and the array results.Heap Sort enter input data into a heap data structure. Greatest value (the max-heap) or the smallest value (in min-heap) is taken one by one until the end, the value is taken in the ordered sequence.The algorithm for heap sort:heapSort function (a, count) isInput: an array is not sorted a long length with(first place in a max-heap) heapify (a, count)end: = count -1 0 do" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">while end> 0 doremove ()reheapify ()end: = end - 1
Algorithm HeapifyHeapify algorithm is to build a heap from the bottom up, successively changing down to build the heap. The first problem we must consider the operation of the heapify is where we must begin. When we try to roots heapify operations will occur runut-up operations like bubble sort algorithm that would cause the complexity of the existing time will double.A different version is to build a heap in a top-down and turns up to be conceptually simpler to handle. This version begins with an empty heap and successively enter the data. Another version is to form a tree-lined heap heap-subtree starting from the bottom subtree. If the subtree-subtree of a node is formed from the heap then the tree node is easily made with a flow heap tree down.Once tested, the most efficient idea is the final version, the complexity of the algorithm in the worst case is O (n), while the forming heap-heap tree tree from top to bottom its complexity O (n log n) Thus, the main algorithm heapify is doing an internal iteration starting from the bottom right node (the representation of the array, the elements in the largest index) to the root, then towards the left and climbed into the top level, and so on until reaching the root (as an array [0 .. N -1]). Therefore, the iteration is started from j = N / 2 and less one-one until it reaches j = 0. At the internal node, the examination is only done on the direct child node (not on the other levels below it). At the time iteration in a higher level, is always already formed subtreesubtree heap. Thus, the case will flow towards the bottom node. Thus, this version heapify do as much as N / 2 times iteration, and in the worst case would do as much iteration log (N) times.
Algorithm RemoveThis algorithm remove the root switch (which contains the maximum value) of the heap with the last element. Logically, the nodes that are most kanabawah transferred to the roots to replace the root node to be taken.
Algorithm ReheapifyReheapify algorithm is doing a remake the heap from top to bottom as well as the last iteration of the algorithm heapify methods. The difference between the methods heapify method on iteration reheapify by both the algorithm. The algorithm method was only doing reheapify last iteration of the algorithm heapify. This is because both the left subtree and right subtree is a heap, so no need for such a complete iteration algorithm heapify. And after reheapify the node that will be reduced next diiterasikan one.
DYNAMIC ALLOCATION REPRESENTATIONS heap sorting algorithm SORTCharacteristics of the heap sorting algorithm is that the sort heap sort implementation using heap tree can be solved in order to heap sort. Therefore, to implement the sort heap sorting algorithm in an application program requires a dynamic allocation using a tree data structure (tree). The basic principles of tree data structure used to realize the heap tree is as follows:a. Nodes are interconnected by using a pointer.In this tree data structure is used at least two pointers in each node, each branch to point to the left and right branches of the tree. For example in C language, tree data structure is declared as follows:Class BinaryTreeSimpul (keyType key;infoType info;BinaryTreeSimpul Left,Right; / / methods)
b. Left and Right value NULL if no more branches in the corresponding direction.
c. The structure of the binary tree, including the relationships between nodes, are explicitly represented by the Left and Right. If required search up (backtrack), then it can be done with a scan of the root, the use of algorithms that are recursive, or use of the stack.
d. Another alternative is to add a pointer to the parent.However, this will result in increasing the number of stages in the processes of addition / removal of nodes
COMPARISON WITH OTHER sorting algorithmHeapsort almost equivalent to a quick sort, other data sorting algorithm based on a highly efficient comparison. Quick sort a bit faster, because the cache and other factors, but in the worst casecomplexity O (n), which is very slow for data that are very large. Then because the heap sort has (N log N) is a system that requires strict security usually wear a heap sort algorithm pengurutannya. Heap sort is often compared with merge sort, which mempunyaikompleksitas the same algorithm, but its space complexity (n) larger than the heap sort. Heap sort is also faster on the machine data dengancache small or slow.
CONCLUSIONTaking advantage of the tree data structure, we can get the data sorting algorithm mangkus which can be used to build a good application programs. Sort heap sorting algorithm can be incorporated into the divide and conquer algorithm that caused the division performed by first applying the algorithm as an initialization heapify method to transform a tree into the heap tree, and at every stage of the algorithm is applied reheapify method to reorder the heap tree

Huffman Coding in a Tree Diagram

Huffman code is basically Initialize_model code prefix (prefix code) which is a set that contains a set of binary code. Prefix code is represented as a labeled binary tree where each side is labeled 0 (left branch) or 1 (right branch). Series of bits that form on each path from the root to leaf is a prefix code for the character that matched.
This code also has a wide variety including:

1. Adaptive Huffman coding
2. Length-Limited Huffman Coding
3. N-Ary Huffman Template Algorithm
4. Huffman With Unequal Letter Costs

1. Variations various Huffman Code

A. Adaptive Huffman Coding
Adaptive methods are used at the time of renewal (update) the new algorithm models both the process of compression and decompression
Basic Concept:
Encoder:
Initialize_model
Repeat for each character
(
Encode character
Update_model
)
Decoder
Initialize_model
Repeat for each character
(
Decode character
Update_model
)
The problem is how to update the model consists of algorithms that increase the number and update the Huffman tree. The trick is to update the tree where it is the compression / nirmampat.
Huffman tree initialized with a single node, known as Not-Yet-Transmitted (NYT) Code that is sent each time a new character is found. The algorithm works with a unique numbering on the nodes with different number of leaves.

Lawyer steps update the model
1. If the code was first discovered NYT, then add the two nodes at node NYT. One node as a node NYT and other node as a leaf. Add the number of leaves. If not the NYT, straight to the leaves.

2. If the block does not have the highest rates, exchange with the highest number of blocks.

3. Add the number of node.

4. Check whether the node is the root node. If not go to the parent node.

B. Length-Limited Huffman Coding

Huffman variation is used to obtain the depth of the smallest distance from a symbol, with the restriction that the length of each of which included no less than a given constant value. This method is usually used with GNU gzip.
The steps in Method Length-Limited Huffman are:

1. Selecting two or more symbols to be compressed

2. Combine these symbols and replace them with pseudo-symbol and its frequency.

3. Perform the above steps are iterative until all the nodes that have a single root node.

4. If these nodes have the same frequency, then choose the node with the shortest depth.

C. Binary Huffman Template Algorima

This algorithm is similar to the ordinary Huffman algorithm. The difference, Huffman tree used in this algorithm has more than two roots (0 and 1). While the Huffman template algorithm, allowing to use non-numerical size (the size and frequency in addition to costs).

D. Huffman With Unequal Letter Costs
In this method there is a problem where a set of code that consists of several letters by frequency of occurrence and cost (cost) is different. This method is intended to find a prefix code (prefix code) and calculate the minimum cost (minimum cost). Prefix code is a set of prefix code-free. Cost (cost) of these is the amount of the cost of each letter in the code.
General steps method of Huffman codes with Unequal Letter Cost:

1. Looking for K-prefix code is optimal.

2. Changing K-prefix code into the optimal prefix code.

3. Having obtained the code and then calculate the cost (cost) of his.

Conclusion
Huffman codes proved to have many variations, among them the Adaptive Huffman Code, Code Length-limited Huffman, n-ary Huffman template algorithm, and Huffman codes with unequal letter costs. Various techniques can be used in applications different, but generally used for data compression. This naturally happens because the essence of all the variations of this technique is similar to Huffman codes, namely solving the optimization problem data.

 
 #Huffman Coding #Tree Diagram