Code And Fun

Rotations When the tree structure changes, we need to modify the tree to restore the AVL tree property. This can be done using single or double rotations. Types of Violations Let us assume the node that must be rebalanced in X. Violations might occur in four cases: Insertion into the left subtree of the left child of X. Insertion into the right subtree of the right child of X.  Insertion into the right subtree of the left child of X. Insertion into the left subtree of the right child of X. Single Rotation Left Left Rotation (LL Rotation) [Case 1]: Rotation does not have to be done at the root of a tree. In general, we start at the node inserted and travel up the tree, updating the balance information at every node on the path. public AVLTree rotateLeft (AVLTree x) {        AVLTree  y = x.right;        // Perform rotation            y.left = x;    ...

What is AVL Tress? A binary tree is said to be an AVL Tree if: It is a binary search tree. For any node, the height of left subtree of node and height of right subtree of node differ by at most 1. Minimum/Maximum number of Nodes in AVL Tree Let the height of an AVL Tree is h and N(h) indicate the number of nodes in AVL Tree. Minimum number of nodes with height h is: N(h) = N(h-1) + N(h-2) + 1 N(h-1) indicates the minimum number of nodes with height h-1 . N(h-2) indicates the minimum number of nodes with height h-2 .   AVL Tree Declaration The declaration of AVL is similar to that of BST (Binary Search Tree). We include the height sldo as a part of a declaration. public class AVLTree {          int key, height;           AVLTree  left, right;           AVLTree  (int data) {                 key = d;...

If a collection refuses to add a particular element for any reason other than that it already contains the element, it  must throw  an exception (rather than returning false). This preserves the invariant that a collection always contains the specified element after this call returns. offer  method - tries to add an element to a queue, and returns  false  if the element can't be added (like in case when a queue is full), or  true  if the element was added, and doesn't throw any specific exception. add  method - tries to add an element to a queue, returns  true  if the element was added, or throws an IllegalStateException if no space is currently available. There is no difference for the implementation of  PriorityQueue.add : public boolean add ( E e ) { return offer ( e ); } For  AbstractQueue  there actually is a difference: public boolean add ( E e ) { if ( offer ( e )) ret...

What is Tree? A tree is a data structure, each node points to a number of nodes. A tree is an example of non-linear data structures. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. The root of a tree is the node with no parents. A node with no children is called a leaf node . Children of the same parent are called siblings . A node "p" is an ancestor of node "q" if there exists a path from "root" to "q" and "p" appears on the path. The node "q" is called descendant of p. Set of all node at a given depth is called the level of the tree. The root node is at level zero. The height of the tree is the maximum height among all the nodes in the tree and depth of the tree is the maximum depth among all the nodes in the tree. Binary Tree A tree is called a binary tree if each node has zero child, one child or two children. Types of binary tree Stric...

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves and then merges the two sorted halves. Algorithm: MergeSort(a[], l, r) If r > l Find the middle point to divide the array into two halves: middle m = (l+r)/2 . Call mergeSort for the first half: Call mergeSort(a, l, m) . Call mergeSort for the second half: Call mergeSort(a, m+1, r) . Merge the two halves sorted in step 2 and 3: Call merge(a, l, m, r) . The following diagram: Source code in Java: class MergeSort {      // Merge two subarray of a[].      // First subarray is a[l...m].     //  Second subarray is a[m+1....r].       void merge(int a[], int l, int m, int r)    {         int n1 = m-l+1;         int n2 = r-m;         // Create temp array.         int L[] = new int[n1];   ...

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of non-overlapping subsets. Union-Find Algorithm is an algorithm which performs two operations: Find: Determine which subset a particular element is in. Union: Join two subsets into a single subset.   Source code in java import java.util.*; import java.lang.*; import java.io.*; class Graph { int V, E; // V-> no. of vertices & E->no.of edges Edge edge[]; // /collection of all edges class Edge { int src, dest; }; // Creates a graph with V vertices and E edges Graph(int v,int e) { V = v; E = e; edge = new Edge[E]; for (int i=0; i<e; ++i) edge[i] = new Edge(); } // A utility function to find the subset of an element i int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // A uti...

Spanning tree of a graph is a subgraph that contains all the vertices and is also a tree.  A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connected all the vertices of G with minimum total cost (weights). A minimum spanning tree exists only if the graph is connected. In this post, O(ELogV) algorithm for adjacency list representation is discussed. Prim's Algorithm:  STEP 1: Create an array parent[] of size V and initialize with -1. STEP 2: Create a min heap (or Priority queue) of size V . Let the min heap be h . STEP 3: Insert all vertices into h such that the key value of starting vertex is 0 and the key value of other vertices is infinite. STEP 4: While h is not empty.      a) u = extractMin() from h .      b) for every adjacent v of u .            if v is in h .               i) update key value of v...