Skip to main content

AVL dan B-Tree

AVL TREE

In Computer Science term an AVL tree is a type of self-balancing binary tree. The word AVL come from it's inventor Adelson-Velsky and Landis. It's the first of such Data Structure. The term self-balancing mean that an AVL tree will maintain both of it's subtree height so that their height diffenrence will be 1, -1, or 0. This is called the balance facotr of an AVL tree. Basically an AVL tree is like an Binary Search Tree but with an self-balancing function built into it. 

Why Use an AVL Tree

The reasoning to why we must balance the tree if it's not balanced is so that the time complexity for the operation (Search, Insert, Delete) will always be at O(log n) instead of the usual O(h) (where h is the height of the tree ) for the worst case scenario. 

 Example of a skewed tree
Image result for skewed bst

For the tree above say that we want to search for the node 74 that we have to traverse the entire tree to find said note but if it's an AVL tree then











We only need to traverse 2 times compare to the original 5 times. This is why we use an AVL tree.

Balance Factor

Now the balance factor of an AVL tree is the difference pf the right sub tree and the left subtree. This balance factor is the one who decide when is the tree is imbalanced. So this factor is very important for AVL tree to kept it's balance. If the balance factor is 1 or -1 or 0 then the tree is balanced but if the balance factor is larger than 1 or less than -1 then the tree is not balance and will need to be balanced. 

Balancing an AVL Tree

So how do we balance an AVL tree > Well first we need to learn the type of unbalance. There are 4 type of unbalance
Case 1 : (L-L) the deepest node is located at the left sub tree of the left child of T.
Case 2 : (R-R) the deepest node is located at the right sub tree of the right child of T.
Case 3 : (R-L) the deepest node is located at the right sub tree of the left child of T.
Case 4 : (L-R) the deepest node is located at the left sub tree of the right child of T.

Now to solve this imbalance we need to rotate the tree to solve this problem. Now there are 2 type of rotation simple rotation or double rotation. 
1. Simple Rotation: This rotation is need for case 1 and 2 
Right rotation (Case 1): 
See the source image

Left Rotation (Case 2):
See the source image
2. Double Rotation: This is needed to resolve case 3 and 4
Left-Right Rotation (Case 3) :
See the source image
Right-Left Rotation (Case 4):

B-Tree

In Computer Science B-Tree is a self-balancing Data Structure that maintain sorted data to allow operation such as search, sequential access, insertion, and deletion in O(log n) time. B-Tree generalize Binary Search Tree in that it allow a nodes that have more than 2 child. Unlike other self-balancing tree, B-Tree in suited for storage system that write and read large amount of data  such as disk, it's commonly used in database and file system.

Property of B-Tree

A B-Tree of m order has these property :
  1. Every node has at most m children
  2. Every non leaf node (except the root node) has at least m/2 child
  3. The root has at least 2 children if it's not leaf node
  4. a non-leaf node that has k child will have at least k-1 keys
  5. All data are kept in sorted order
  6. All leaf node will be at the same height (bottom)
Example of a B-Tree with an order of 5, note that in most B-Tree the order will be more than 5 :

Exercise :
Create an AVL tree and a B-Tree with the following instruction for both :
  • Insert : 5,6,7,0,4,3,8
  • Delete : 3,4,8
1. AVL Tree

2. B-Tree

Comments

Post a Comment

Popular posts from this blog

Linked List Linked List a sequence of data structure connected together via links. In C a list is usually composed of multiple type of data so we usually use struct so that we can insert multiple amount of data into a single list, also our list also contain a reference(pointer in C) to the next list. So because of this reference our list linked to one another and that is also why this is called linked list. Also in linked list there is another reference that is Head and Tail . Head point to the first list in our linked list and Tail point to the last of our list in the linked list. Now Linked List usually have 2 type that is : 1. Single Linked List 2. Double/Doubly Linked List Single Linked List A single linked list have only one reference that is a reference to the next list. So we could think that a single linked list is like an array.  As seen a single linked list only contain one reference that point to the next list. Also in our tail the next poin...
Post a Comment
Read more
Stack & Queue Stack Stack is type of data structure that store it's data in an orderly manner. Data in stack can only be removed and added from one end of the data. This is called LIFO (Last in First Out) Meaning that the last data that enter will be the first one to be removed. Stack can be implemented with array or linked list. Stack is usually used in backtracking algorithm and also used when making a recursive function (Depth First Search). Queue Queue is also a type of data structure but it's main difference from stack is that in queue data can only be added from behind and data can only be removed from the front of the queue just like a real life queue. This is called FIFO (First In First Out) meaning that the first data that is inserted will be the one that is removed first. Also like stack queue can be implemented with array or linked list. Now queue is used in an algorithm called Breath First Search. Queue also have another type called Circular Que...
Post a Comment
Read more