Blog

AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains an extra information called as balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis. Balance Factor Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of right subtree of that node. Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1. AVL Rotations Left Rotation If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation Right Rotation AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree then needs a right

Linked List LinkedList  − A Linked List contains the connection link to the first link called First and to the last link called Last. Singly Linked List   A singly linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The ‘data’ field stores actual piece of information and ‘link’ field is used to point to next node. Doubly Linked List A doubly linked list  contains an extra pointer, typically called  previous pointer , together with next pointer and data which are there in singly linked list. Difference between Singly linked list and Doubly linked list In SingleLinkList, the traversal can be done using the next node link only. In DoublyLinkList, the traversal can be done using the previous node link or the next node link. The SingleLinkList occupies less memory than DoublyLinkList as it has only 2 fields. The DoublyLinkList occupies more memory than SingleLinkList as it has 3 fields. Less efficient access to elements. More efficient