AVL and B3
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree
so in short there it is a sorted BST to make searching, inserting, etc, faster. since it has a habt of rebalancing it self.
4 possible case:-
left left case
left right case
right right case
right left case
for each of the following cases, there are actions took to rebalance the tree and sort the tree by rotating it.
B-tree
B-Tree is a self-balancing search tree. In most of the other self-balancing search trees, it is assumed that everything is in main memory. The main idea of using B-Trees is to reduce the number of disk accesses. Most of the tree operations (search, insert, delete, max, min, ..etc ) require O(h) disk accesses where h is the height of the tree. B-tree is a fat tree.
The goal of a B-tree is to keep the leaves as minimum as possible, there are a few types of B - tree that we can implement, there are 2 - n degree of B - tree.
properties:-
- All leaves are at same level.
- A B-Tree is defined by the term minimum degree ‘t’. The value of t depends upon disk block size.
- Every node except root must contain at least t-1 keys. Root may contain minimum 1 key.
- All nodes (including root) may contain at most 2t – 1 keys.
- Number of children of a node is equal to the number of keys in it plus 1.
- 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.
- B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward
so in short there it is a sorted BST to make searching, inserting, etc, faster. since it has a habt of rebalancing it self.
4 possible case:-
left left case
left right case
right right case
right left case
for each of the following cases, there are actions took to rebalance the tree and sort the tree by rotating it.
B-tree
B-Tree is a self-balancing search tree. In most of the other self-balancing search trees, it is assumed that everything is in main memory. The main idea of using B-Trees is to reduce the number of disk accesses. Most of the tree operations (search, insert, delete, max, min, ..etc ) require O(h) disk accesses where h is the height of the tree. B-tree is a fat tree.
The goal of a B-tree is to keep the leaves as minimum as possible, there are a few types of B - tree that we can implement, there are 2 - n degree of B - tree.
properties:-
- All leaves are at same level.
- A B-Tree is defined by the term minimum degree ‘t’. The value of t depends upon disk block size.
- Every node except root must contain at least t-1 keys. Root may contain minimum 1 key.
- All nodes (including root) may contain at most 2t – 1 keys.
- Number of children of a node is equal to the number of keys in it plus 1.
- 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.
- B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward
Komentar
Posting Komentar