Struktur Data

Binary Tree

Binary Tree is a tree in a hierarchical data structure (one to 

many relationship). A tree can be defined as a collection of vertices with each node having at most two children. Specifically, their children are named left and right. Binary trees do not have more than three levels from Root.
Binary tree is a tree with the condition that each node (node) can only have a maximum of two subtree and the two subtree must be separate. Each node in a binary tree can have at most two children, the child specifically named left and right.
Binary trees can also be stored as implicit data structures in arrays, and if the tree is a complete binary tree, this method does not waste a place. In this tight arrangement, if a node has index i, its child can be found at index 2i + 1 and 2i + 2, even though the father (if any) is found at the index floor ((i-1) / 2) (assume the root has an empty index).

Binary Search Tree

Binary Search Tree is an ordered tree (ordered Binary Tree). Binary Search Tree is also often called a Sorted Binary Tree which functions to store information on names or numbers that are stored in memory. With this data is divided into two by finding the midpoint as a benchmark. A binary tree consists of a main node called the root. Then from the root there are the left and right. Data is stored after the root is stored based on the value of comparison with the root. Ordering can be done if BST is traced (traversed) using the in-order method. Details of this search process will be discussed at the next meeting. Data that has been arranged in the BST data structure can also be searched easily and has an average complexity of O (log n), but requires a time of O (n) in the worst conditions where BST is not balanced and forms a linked list

Binary search tree allows fast searching, addition, also deleting the data contained in it, can also be used as an implementation of a number of dynamic data, or search for data tables by using key information.

In order for the data to actually be arranged in the BST data structure, the two rules that must be met when the data are arranged in the BST are as follows:

All data in the left sub-tree of node t is always smaller than the data in node t itself.

All data in the right sub-tree of node t is always greater or the same as data in node t.

Hash

Hash or Hashing means decapitating and then combining. The hash uses main storage memory in the form of arrays with additional algorithms to speed up data processing. A hash is a method that directly accesses records in a table by performing an arithmetic transformation on the key that is the address in the table.

Hashing is used as a method for storing data in an array so that data storage, data search, data addition and data deletion can be done quickly.

The hash function must be stable (referential transparent), meaning, if it is called twice by exactly the same input (for example, a string containing the same character sequence), then it must give the same result.

Tracking using a hash consists of two main steps, namely:

Calculating Hash Functions

The Hash function is a function that changes keys to addresses in a table. The Hash function maps a key to an address in a table. Ideally, different keys should be mapped to different addresses. In fact, there is no perfect Hash function. Most likely what happens is that two or more different keys are mapped to the same address in the table. This event is called a collision. That's why the next step is needed, namely collision resolution (collision resolution).

Collision Resolution

Collision resolution is the process of handling the occurrence of two or more keys hashed to the same address. The way to do this if a collision occurs is to find the empty locations in the Hash table in order. Another way is to use another hash function to find the empty location.