AVL Tree dan B-Tree

AVL Tree

AVL Tree is one type of BST that is formed in a balanced way.
The difference between the height of the right and left branches may not be more than one.
The height of the AVL Tree is always O (Log n), where n is the number of nodes in the tree.
In the Insertion in AVL Tree, we do BSTT Insertion as usual then each node is balanced by right or left rotation.
The purpose of AVL Tree is to shorten and simplify the search time of data.

Some cases:

• Left Left case
• Left Right case
• Right Right case
• Right Left case

Here is the example of AVL Tree:

Case:

Insert: 5,6,7,0,4,3,8

Delete: 3,4,8

B-tree

B-Tree is part of a binary tree, which is a form of simplification and balancing at the same time as a binary tree.

Rules on the B-Tree: m = order

• Each node (except leaves) has the most number of child
• Each node (except root) has children of at least m / 2 child
• Root has at least 2 child, as long as the root is not a leaf
• If the non-leaf node has k child, then the amount of data stored in node k-1
• Data stored on the node must be sorted in-order
• All leaves are at the same level

Operations on B-Tree are Insertion, Deletion, and Searching.

Data Structure's Summary

Linked list is more dynamic than Array list. It can store/delete unlimited data.
Actually, there are 3 types of linked list in data structures;

1.    Singly Linked List

2.    Doubly Linked List

3.    Circular Doubly Linked List

§  Singly Linked List

§  Simply, here is the example of a singly linked list.

§  Doubly Linked List

§  Doubly linked list is like singly linked list, but it have two direction for each list, so they could go to the head or tail direction.

§  Here is the example of doubly linked list.

Stack Concept

§  Basically, the data are stored like stacked objects. We insert the object to the last, and the last will be taken first. This is also known as LIFO (Last in First Out).

§  Stack Operations:

• push(x) : add an item x to the top of the stack.
• pop() : remove an item from the top of the stack.
• top() : reveal/return the top item from the stack.

Queue Concept

§  Queue concept is just like the stack concept but this time the first one will be taken first. This is also known as  FIFO (First In First Out).

§  Infix, Postfix, Prefix Notations.

§  Based on how operator is written, there are 3 methods in inserting data:

• Infix
• Operator is written between operands.
• Postfix
• Operator is written after operands.
• Prefix
• Operator is written before operands.

Hashing 

§  Hashing is a technique to store retrieve key in a faster way. 

§  It's transforming a string into a shorter length value/key. (hashed key)

Hash Table

§  Hash table is an array that stores the original value of a string.

§  The hash table size is lower than the total number of possible string (some string can have the same key).

Hash Function

§  There are several methods to hash a string into a key:

• Mid-square
• Square the string, then obtain the key from number of bits taken from the middle of the square.
• Division
• This is the most common and simplest method.
• We can obtain the key by dividing the string with modulus operator.
• Folding
• We can obtain the hash key by dividing the key value into parts. Every parts has the same number of digits(except for the last one). Then add every parts except the last one.
• ex: x= 1264 ; then the parts is 12 & 64 ; then the sum is 76(hash value).
• Digit Extraction
• Considering some digits as a hash address from the given number.
• ex: x=15.769 ; If we extract the first, third and fifth digit, we will obtain the hash code which is 179
• Rotating Hash
• Use any hash method to find the hash code. Then rotate the value from front to back.
• ex: hash address=19920 ; then the rotation result is 02991.
• Collision
• There are two ways to handle collision:
• Linear Probing
• Searching for next empty slot and store the string there.
• Chaining
• Inserting string to a slot as chained list.

Tree

§  Tree is a form of non-linear data structure that describes the relationship that is hierarchical between the elements.

§  Tree can be defined as a collection of nodes with a special element called root and other nodes are divided into sets that are not related to each other (called as sub-tree).

Binary Trees

§  A binary tree is made of nodes where each node contains a left pointer and right pointer. The root pointer points to top of tree. 

§  Left and right pointers point to sub-tree smaller than both sides with recursive.

Hashing & Binary Tree

• Hashing 
• Hashing is a technique to store retrieve key in a faster way. 
• It's transforming a string into a shorter length value/key. (hashed key)

• Hash Table
• Hash table is an array that stores the original value of a string.
• The hash table size is lower than the total number of possible string (some string can have the same key).

• Hash Function
• There are several methods to hash a string into a key:
• Mid-square
• Square the string, then obtain the key from number of bits taken from the middle of the square.
• Division
• This is the most common and simplest method.
• We can obtain the key by dividing the string with modulus operator.
• Folding
• We can obtain the hash key by dividing the key value into parts. Every parts has the same number of digits(except for the last one). Then add every parts except the last one.
• ex: x= 1264 ; then the parts is 12 & 64 ; then the sum is 76(hash value).
• Digit Extraction
• Considering some digits as a hash address from the given number.
• ex: x=15.769 ; If we extract the first, third and fifth digit, we will obtain the hash code which is 179
• Rotating Hash
• Use any hash method to find the hash code. Then rotate the value from front to back.
• ex: hash address=19920 ; then the rotation result is 02991.
• Collision
• There are two ways to handle collision:
• Linear Probing
• Searching for next empty slot and store the string there.
• Chaining
• Inserting string to a slot as chained list.

• Tree
• Tree is a form of non-linear data structure that describes the relationship that is hierarchical between the elements.
• Tree can be defined as a collection of nodes with a special element called root and other nodes are divided into sets that are not related to each other (called as sub-tree).

• Binary Trees
• A binary tree is made of nodes where each node contains a left pointer and right pointer. The root pointer points to top of tree. 
• Left and right pointers point to sub-tree smaller than both sides with recursive.

• Hashing Implementation in Blockchain
• When we are talking about hashing in blockchain, we are talking about the process of having an input item of whatever length reflecting an output item of a fixed length. 
• If we take the example of blockchain use in cryptocurrencies, transactions of varying lengths are run through a given hashing algorithm, and all give an output that is of a fixed length.

Stack & Queue

Operator is written between operandsIn this material we will learn about how data are stored(stack & queue) and notations(Infix, Postfix, Prefix).

• Stack Concept
• Basically, the data are stored like stacked objects. We insert the object to the last, and the last will be taken first. This is also known as LIFO (Last in First Out).
• Stack Operations:
• push(x) : add an item x to the top of the stack.
• pop() : remove an item from the top of the stack.
• top() : reveal/return the top item from the stack.
• Queue Concept
• Queue concept is just like the stack concept but this time the first one will be taken first. This is also known as  FIFO (First In First Out).
• Infix, Postfix, Prefix Notations.
• Based on how operator is written, there are 3 methods in inserting data:
• Infix
• Operator is written between operands.
• Postfix
• Operator is written after operands.
• Prefix
• Operator is written before operands.

Linked List

Linked list is more dynamic than Array list. It can store/delete unlimited data.
Actually, there are 3 types of linked list in data structures;

1. Singly Linked List
2. Doubly Linked List
3. Circular Doubly Linked List

• Singly Linked List

• Simply, here is the example of a singly linked list.

• Doubly Linked List

• Doubly linked list is like singly linked list, but it have two direction for each list, so they could go to the head or tail direction.
• Here is the example of doubly linked list.

• Circular Doubly Linked List
• I may say that circular doubly linked list is a kind of combination of singly and doubly linked list.