*Binary Search Tree:*

*Binary Search Tree:*

A binary search tree is also called an ordered or sorted binary tree because the in-order traversal of binary search tree is always in sorted order.

*A binary search tree is a binary tree with only two branches in which each node of the left subtree is less than or equal and each node in the right subtree is greater. A binary Search Tree is a node-based binary tree data structure. We can perform preorder, in-order, and post-order traversal using the Binary Search tree.*

*AVL Tree: *

*AVL Tree:*

AVL tree is a self-balancing Binary Search Tree where the difference between heights of left and right subtrees cannot be more than 1 for all nodes. This difference is called the Balance Factor i.e. 0, 1, and -1.

*In order to perform this balancing, we perform the following rotations on the unbalanced/imbalanced Binary Search Tree to make it an AVL tree.*

*Left Rotation**Right Rotation**Left Right Rotation**Right Left Rotation*

*Following are the Difference between Binary Search Tree and AVL Tree*

*Following are the Difference between Binary Search Tree and AVL Tree*S.No | Binary Search Tree | AVL Tree |
---|---|---|

1. | In Binary Search Tree, In AVL Tree, every node does not follow the balance factor. | In AVL Tree, every node follows the balance factor i.e. 0, 1, -1. |

2. | Every Binary Search tree is not an AVL tree. | Every AVL tree is a Binary Search tree. |

3. | Simple to implement. | Complex to implement. |

4. | The height or depth of the tree is O(n). | The height or depth of the tree is O(logn) |

5. | Searching is not efficient when there are a large number of nodes in the Binary Search tree. | Searching is efficient because searching for the desired node is faster due to the balancing of height. |

6. | The Binary Search tree structure consists of 3 fields left subtree, data, and right subtree. | AVL tree structure consists of 4 fields left subtree, data, right subtree, and balancing factor. |

7. | It is not a balanced tree. | It is a balanced tree. |

8. | In Binary Search tree. Insertion and deletion are easy because no rotations are required. | In an AVL tree, Insertion and deletion are complex as it requires multiple rotations to balance the tree. |