Comparison of BST and AVL


Binary Search Tree (BST) is a tree that left item is less than root, right item is greater than root and each sub-tree is it itself a binary search tree. For BST, the first piece of data is the root of the tree. Balancing is not important in BST. On the other hand, AVL tree is alike BST but it is a highly balanced tree, which mean the number of sub-trees on the left almost equal on the right. From the result of program two, we can see the difference between two trees and which is more effective than the other.


Looking at the search result, there are 37 times, which is more than half the total number of search, that the Binary Tree takes larger amount of steps than the AVL tree. If the data is found, AVL tree far beats BST. While on unfound data, the two trees are almost equal. This mean if the data does exist AVL can find it faster than BST most of the time and almost equal other if not. In steps count, the largest BSTís count is 15 while AVLís count is only 10. This mean the BSTís height is larger than AVLís height. From this result, we can see why AVL beats BST most of the time when searching for data near the bottom of the tree. However, BST takes the lead when search for data near the root, which is very minimal.


For my opinion, AVL tree is very effective and a lot faster when implement to store larger number of data. Although, itís algorithm is complex, difficult to understand and hard to debug, but it will save a lot time when the user frequently search for data in a larger database. In contrast, BST is better for small data storage where running time is not significantly high. Its algorithm is simple, easy to understand and maintains