Menu
How is an AVL tree different from a B-tree?
367
AVL tree is also a BST but it can rebalance itself. This behavior makes it faster in worst cases. It keeps rebalancing itself so in worst case it will consume O(log n ) time when the plain BST will take O(n). So, the answer to your question: It is always better to implement AVL tree than just plain BST.
Advantages of AVL TreesThe height of the AVL tree is always balanced. The height never grows beyond log N, where N is the total number of nodes in the tree. It gives better search time complexity when compared to simple Binary Search trees. AVL trees have self-balancing capabilities.
B-Tree : B-Tree is known as a self-balancing tree as its nodes are sorted in the inorder traversal. Unlike the binary trees, in B-tree, a node can have more than two children. B-tree has a height of logM N (Where 'M' is the order of tree and N is the number of nodes).
The AVL tree is faster than the BST. When we know that we have to do more searching than insertions, we should without any doubt use AVL trees. The insertions into AVL trees make take more time than in BST when random elements are inserted, but that is quite a minute difference.
AVL trees are intended for in-memory use, where random access is relatively cheap. B-trees are better suited for disk-backed storage, because they group a larger number of keys into each node to minimize the number of seeks required by a read or write operation. (This is why B-trees are often used in file systems and databases, such as SQLite.)
124
Both the AVL tree and the B-tree are similar in that they are data structures that, through their requirements, cause the height of their respective trees to be minimized. This "shortness" allows searching to be performed in O(log n) time, because the largest possible number of reads corresponds to the height of the tree.
5 / \ 3 7 / / \ 1 6 9 This is an AVL tree, and is a binary search tree at its core. However, it is self-balancing, which means that as you add elements to the tree, it will restructure itself to maintain as uniform of a height as it can. Basically, it will not allow long branches.
A B-tree also does this, but through a different re-balancing scheme. It's a little too complicated to write out, but if you Google search "B-tree animation" there are some really good applets out there that explain a B-tree pretty well.
They are different in that an AVL tree is implemented with memory-based solutions in mind, while a B-tree is implemented with disk-based solutions in mind. AVL trees are not designed to hold massive collections of data, as they use dynamic memory allocation and pointers to the next block of memory. Obviously, we could replicate the AVL tree's functionality with disk locations and disk pointers, but it would be much slower because we would still have a significant number of reads to read a tree of a very large size.
When the data collection is so large that it doesn't fit in memory, the solution is a B-tree (interesting factoid: there is no consensus on what the "B" actually stands for). A B-tree holds many children at one node and many pointers to children node. This way, during a disk read (which can take around 10 ms to read a single disk block), the maximum amount of relevant node data is returned, as well as pointers to "leaf node" disk blocks. This allows retrieval time of data to be amortized to log(n) time, making the B-tree especially useful for database and large dataset retrieval implementations.
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
