RANGKUMAN AVL TREE DAN B-TREE
AVL TREE
Avl tree is a subtype of binary tree, avl tree has the property of self balancing in addition to all the properties exhibited from binary search tree.
Properties:
1. Each tree has a root node (at the top).
2. The root node has zero, one or two child nodes.
3. Each child node has zero, one or two child nodes, and so on.
4. Each node has up to two children.
5. For each node, its left descendants are less than the current node, which is less than the right descendants.
6. The difference between the depth of right and left subtrees cannot be more than one. Avl tree will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee.

AVL TREE INSERTION
When inserting into avl tree we insert using the same as binary search tree then we use left or right rotation to balance the tree.
1. If there is an imbalance in left child of right subtree, then you perform a left-right rotation.
2. If there is an imbalance in left child of left subtree, then you perform a right rotation.
3. If there is an imbalance in right child of right subtree, then you perform a left rotation.
4. If there is an imbalance in right child of left subtree, then you perform a right-left rotation.

AVL TREE ROTATION
in avl tree after performing an operation we need to check the balance, We use rotation operations to make the tree balanced whenever the tree is becoming imbalanced due to any operation.
there are 4 rotation:
1. Single left rotation = every node moves 1 position to the left from the current position.
2. Single Right Rotation =every node moves 1 position to the right from the current position.
3. Left Right Rotation(combination of single left and single right rotation) =every node moves one position to left then one position to right from the current position.
4.  Right Left Rotation(combination of single left and single right rotation) =every node moves one position to right then one position to left from the current position.

AVL TREE DELETION
1. we perform standard deletion same as binary search tree.
2. then rebalance using rotation.

  • If there is an imbalance in left child of right subtree, then you perform a left-right rotation.
  • If there is an imbalance in left child of left subtree, then you perform a right rotation.
  • If there is an imbalance in right child of right subtree, then you perform a left rotation.
  • If there is an imbalance in right child of left subtree, then you perform a right-left rotation.
B-TREE
B-tree is a self balancing binary search tree.
Properties:


1. All leaves are at same level.
2. A B-Tree is defined by the term minimum degree ‘t’. The value of t depends upon disk block size.
3. Every node except root must contain at least t-1 keys. Root may contain minimum 1 key.
4. All nodes (including root) may contain at most 2t – 1 keys.
5. Number of children of a node is equal to the number of keys in it plus 1.
6. All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in the range from k1 and k2.
7. B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward.
8. Like other balanced Binary Search Trees, time complexity to search, insert and delete is O(Logn).

B-TREE INSERTION
A new key is always inserted at the leaf node. B-tree  have a predefined range on the number of keys that a node can contain. So before inserting a key to the node, we make sure that the node has extra space. splitChild() is used to split a child of a node, to make sure that a node has space available for a key before the key is inserted.
1. Initialize x as root.
2. While x is not leaf, do following

  • Find the child of x that is going to be traversed next. Let the child be y.
  • If y is not full, change x to point to y.
  • If y is full, split it and change x to point to one of the two parts of y. If k is smaller than mid key in y, then set x as the first part of y. Else second part of y. When we split y, we move a key from y to its parent x.

3. The loop in step 2 stops when x is leaf. x must have space for 1 extra key as we have been splitting all nodes in advance. So simply insert k to x.

B-TREE DELETION
when we delete a key from an internal node, we will have to rearrange the node’s children.
1. If the key k is in node x and x is a leaf, delete the key k from x.

2. If the key k is in node x and x is an internal node, do the following.


  • If the child y that precedes k in node x has at least t keys, then find the predecessor k0 of k in the sub-tree rooted at y. Recursively delete k0, and replace k by k0 in x. (We can find k0 and delete it in a single downward pass.)
  • If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k0 of k in the subtree rooted at z. Recursively delete k0, and replace k by k0 in x. (We can find k0 and delete it in a single downward pass.)
  • Otherwise, if both y and z have only t-1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t-1 keys. Then free z and recursively delete k from y.

3. If the key k is not present in internal node x, determine the root x.c(i) of the appropriate subtree that must contain k, if k is in the tree at all. If x.c(i) has only t-1 keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least t keys. Then finish by recursing on the appropriate child of x.

  • If x.c(i) has only t-1 keys but has an immediate sibling with at least t keys, give x.c(i) an extra key by moving a key from x down into x.c(i), moving a key from x.c(i) ’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into x.c(i).
  • If x.c(i) and both of x.c(i)’s immediate siblings have t-1 keys, merge x.c(i) with one sibling, which involves moving a key from x down into the new merged node to become the median key for that node.

Contoh soal AVL-tree:
insert: 5,6,7,0,4,3,8
delete: 3,4,8

struct node{
int val;
int height;
struct node *left, *right;
};

int max(int a, int b)
{
if(a>=b)return a;
else return b;
}

int getHeight(struct node *node)
{
if(node==NULL)return 0;
else return node->height;
}

int getBFactor(struct node *node)
{
if(node==NULL)return 0;
else return getHeight(node->left)-getHeight(node->right);
}

struct node *rightRotate(struct node *a)
{
struct node *b=a->left;
struct node *c=b->right;
b->right=a;
a->left=c;
a->height=max(getHeight(a->left), getHeight(a->right))+1;
b->height=max(getHeight(b->left), getHeight(b->right))+1;
return b;
}
struct node *leftRotate(struct node *a)
{
struct node *b=a->right;
struct node *c=b->left;
b->left=a;
a->right=c;
a->height=max(getHeight(a->left), getHeight(a->right))+1;
b->height=max(getHeight(b->left), getHeight(b->right))+1;
return b;
}
struct node *insert(struct node *root, int val)
{
if(root==NULL)
{
struct node *newNode=(struct node*)malloc(sizeof(struct node));
newNode->val=val;
newNode->height=1;
newNode->right=newNode->left=NULL;
return newNode;
}
else if(val<root->val)
root->left=insert(root->left, val);
else if(val>root->val)
root->right=insert(root->right, val);
root->height=max(getHeight(root->left), getHeight(root->right))+1;
int bFactor=getBFactor(root);
if(bFactor > 1 && getBFactor(root->left)>=0)
return rightRotate(root);
else if(bFactor < -1 && getBFactor(root->right) <=0)
return leftRotate(root);
else if(bFactor > 1 && getBFactor(root->left) < 0)
{
root->left=leftRotate(root->left);
return rightRotate(root);
}
else if(bFactor < -1 && getBFactor(root->right)>0)
{
root->right=rightRotate(root->right);
return leftRotate(root);
}
return root;
}
struct node *getMaxNode(struct node *node)
{
if(node->right!=NULL)
{
node=node->right;
}
return node;
}
struct node *del(struct node *node, int val)
{
if(node==NULL)
{
printf("Data not found\n");
return NULL;
}
else if(val<node->val)
node->left=del(node->left, val);
else if(val>node->val)
node->right=del(node->right, val);
else
{
if(node->left==NULL && node->right==NULL)
{
free(node);
node=NULL;
return node;
}
else if(node->right==NULL)
{
struct node *temp=node;
node=node->left;
free(temp);
}
else if(node->left==NULL)
{
struct node *temp=node;
node=node->right;
free(temp);
}
else
{
struct node *temp=getMaxNode(node->left);
node->val=temp->val;
node->left=del(node->left, temp->val);
}
}
if(node==NULL)return node;
node->height=max(getHeight(node->left), getHeight(node->right))+1;
int bFactor=getBFactor(node);
if(bFactor > 1 && getBFactor(node->left)>=0)
return rightRotate(node);
else if(bFactor < -1 && getBFactor(node->right) <=0)
return leftRotate(node);
        else if(bFactor > 1 && getBFactor(node->left) < 0)
{
node->left=leftRotate(node->left);
return rightRotate(node);
}
else if(bFactor < -1 && getBFactor(node->right)>0)
{
node->right=rightRotate(node->right);
return leftRotate(node);
}
return node;
}
int main(){
struct node *root=NULL;
int val;
printf("Input the number: "); 
scanf("%d", &val); getchar();
root=insert(root, val);
printf("Input the number: "); 
scanf("%d", &val); getchar();
root=del(root, val);
}

Comments

Post a Comment

Popular posts from this blog

Binary search tree adalah binary tree yang menggunakan node dan memiliki beberapa properti yaitu: Node anak kiri berisikan angka lebih kecil dari node induk Node anak kanan berisikan angka lebih besar dari node induk Node kanan dan kiri juga harus merupakan binary search tree tidak boleh ada node yang duplicate /sama Operasi pada binary search tree: find(); mencari sebuah angka/data pada binary search tree insert(): memasukkan angka/data baru pada binary search tree remove():menghapus angka/data baru pada binary search tree Searching: untuk melakukan searching pertama kita mengcompare nodenya , apabila angka/data yang dicari ada pada node maka kita akan return node, apabila angka yang ingin dicari lebih besar makan kita akan mengcompare node anak kanan sedangkan apabila lebih kecil kita akan mengcompare anak node kiri. struct node* search(struct node* root, int key) {     if (root == NULL || root->key == key)        return root; ...
Read more