Data Structure

AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis.  Since AVL trees are height balance trees, operations like insertion and deletion have low time complexity. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor . Balance Factor Balance factor of a node in an AVL tree is the differenc e between the height of the l eft subtree  and that of the  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. If the difference in the height of left and

Binary Search Tree Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.  It is called a Binary tree because each tree node has a maximum of 2 children It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time. The properties that separates a binary search tree from a regular binary tree is All nodes of left subtree are less than root node All nodes of right subtree are more than root node Both subtrees of each node are also BSTs meaning they have the above two properties On the picture shown above, the right tree is not a binary search tree because on the right subtree of the root, there's a number with smaller value than the root.  Basic Operations Following are the basic operations of a tree − Search   − Searches an element in a tree. Insert  − Inserts an element in a tree. Pre-order Traversal  − Traverses a tree in a pre-order manner. In-order Traversa

Hashing Table Hash Table is a data structure which stores data in an associative manner.  Data is stored in an array format, where each data value has its own unique index value.  Access of data becomes very fast if we know the index of the desired data. So,   Hash Table is a data structure in which insertion and search operations are very fast where the size of the data doesn't matter.   Hash Function  A hash function job is to store values in an array with a limited size It does it in a way that the array doesn't need to be searched through to find it. This allows us to enter values in any order and we can find them using a calculation instead of searching through the array So how does Hash Table & Hash Function work together? Key values are assigned to elements in a Hash Table using a Hash Function Hash function helps calculate the best index an item should go in Here are a few methods to hash  keys  from string: Mid-square Division Fol

Stack vs Queue Stack  and  Queue  are two important data structures in the programming world and have a variety of usage. T hey are a secondary data structure which can build using an array or linked list. They have their own functions.  Stack can solve recursive problems while Queue can be used for ordered processing. Stack A stack is a container of objects that are inserted and removed in which elements use the  Last-In-First-Out   principle ( LIFO ). The delete operation is known as   POP , in relation to the physical idea of popping something from a stack The   LIFO   structure also means we can only remove the item that was most recently added The   PUSH   operation can be used to add items to a stack. which refers to the physical idea of pushing an item onto the top of a stack The Stack data structure is a natural recursive data structure and suits well for recursive problems e.g. implementing pre-order ,  post-order , and  in-order   traversal of the binary tr

Linked List Definition A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. Pointers are used to link elements.  Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location. Linked List also has some advantages over arrays such as dynamic size and easier insertion or deletion.  Linked list can be visualized as a chain of nodes, where every node points to the next node. These are the basic operations supported by a list. Insertion  − Adds an element at the beginning of the list Deletion  − Deletes an element at the beginning of the list Display  − Displays the complete list Search  − Searches an element using the given key Delete  − Deletes an element using the given key Types of Linked List Simple Linked List   − Item navigation is forward only Doubly Linked List   − Items can be navigated forward and backward Circular Linked Lis