w3college.com

  A tree is a hierarchical data structure where data is stored in nodes interconnected via some edges. A  General Tree   can have any number of nodes. A  Binary Tree   is a type of tree where each node has at max two child nodes. A  Binary Search Tree  or  BST  is a binary tree where the left child is less than the right child. If the difference between the height of the left subtree and the right subtree of a BST is not more than one then, that tree is called  Balanced BST.  An AVL tree is a binary search tree that is height-balanced for each node. The following Venn diagram is a visual aid for better understanding.   Learning everything about AVL trees at once is a tedious task. So to ease the pace of learning the whole blog is divided into 3 different blog series. The content of the three blogs are:  Introduction to AVL Trees Insertion in AVL Trees Deletion in AVL Trees   In this article, we’ll learn about insertio...

  AVL Trees Recall that balanced BSTs maintain  h = O(\log n) h = O ( lo g n ) , so all operations run in  O(\log n) O ( lo g n )  time. Self-balancing  BSTs are data types that automatically keep track of their height to maintain the balanced property. One of the most important operations on most self-balancing binary trees is the  rotation . Left and right rotations are animated below. [ 1 ] Some of the popular data structures that implement self-balancing BSTs include: 2-3 trees AVL trees Red-black trees In this section, we’ll discuss AVL trees. AVL: Adel’son-Vel’skii & Landis AVL trees  are the first example (invented in 1962) of a  self-balancing  binary search tree. AVL trees satisfy the  height-balance property : for any node  n n , the heights of  n n ’s left and right subtrees can differ by at most 1. To make math easier, we can define each null node to have height of -1. This will make balancing easier. As part of...