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.
0 comments:
Post a Comment