Posts

AVL Tree and Binary Tree

Image
1. AVL TREE What is AVL tree?  AVL tree is a binary search tree in which the difference of heights of left and right subtrees of any node is less than or equal to one.  The goal is to keep the height of a BST to be O(log n). Operations like insertion or deletion will have lower time complexity. Here we see that the first tree is balanced and the next two trees are not balanced In the second tree, the left subtree of  C  has height 2 and the right subtree has height 0, so the difference is 2. In the third tree, the right subtree of  A  has height 2 and the left is missing, so it is 0, and the difference is 2 again. AVL tree permits difference (balance factor) to be only 1. If the difference in the height of left and right sub-trees is more than 1, the tree is balanced using some rotation techniques. AVL ROTATION There are 4 types of rotation: - Left rotation - Right rotation - Left-Right rotation - Right-Left rotation We will ...
Post a Comment
Read more

DATA STRUCTURE SUMMARY

Image
Linked List Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers. 1. SINGLE LINKED LIST To CREATE a linked list, we first need to define a node structure for the list. struct tnode {   int value;   struct tnode *next; }; struct tnode *head = 0; To INSERT a new value, first we should dynamically allocate a new node and assign the value to it and then connect it with the existing linked list. struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode)); node->value = x; node->next  = head; head = node; To DELETE  a value, first we should find the location of node which store the value we want to delete, remove it, and connect the remaining linked list. There are 2 conditions, when the deleted value is on the head and not on the head. struct tnode *curr = head; // if x is in head n...
Post a Comment
Read more