Self Balancing Binary Tree

  1. AVL Tree Implementation. Code. GFG – Insert, Delete  Youtube
    Time Complexity: The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Updating the height and getting the balance factor also take constant time. So the time complexity of AVL insert remains same as BST insert which is O(h) where h is height of the tree. Since AVL tree is balanced, the height is O(Logn). So time complexity of AVL insert is O(Logn). To create an AVL tree you have to insert n elements in it. To insert the element in a balanced tree you need log(n). Therefore you end up with O(n*log(n)).  SO
    Comparison with Red Black Tree

    The AVL tree and other self balancing search trees like Red Black are useful to get all basic operations done in O(Log n) time. The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is more frequent operation, then AVL tree should be preferred over Red Black Tree.
  2. *** Determine if a binary tree is height-balanced 

  3. Count smaller elements on right side. GFG
    1. O(n^2) solution
    2.   A Self Balancing Binary Search Tree (AVL, Red Black,.. etc) can be used to get the solution in O(nLogn) time complexity. We can augment these trees so that every node N contains size the subtree rooted with N. We have used AVL tree in the following implementation.We traverse the array from right to left and insert all elements one by one in an AVL tree. While inserting a new key in an AVL tree, we first compare the key with root. If key is greater than root, then it is greater than all the nodes in left subtree of root. So we add the size of left subtree to the count of smaller element for the key being inserted. We recursively follow the same approach for all nodes down the root.  Auxiliary Space: O(n)


  4. Merge Two Balanced Binary Search Trees. GFG – Same as merging BST
    1. Insert one tree into another – Take all elements of first BST one by one, and insert them into the second BST. Inserting an element to a self balancing BST takes Logn time (See this) where n is size of the BST. So time complexity of this method is Log(n) + Log(n+1) … Log(m+n-1). The value of this expression will be between mLogn and mLog(m+n-1)
    2. Do inorder traversal and get two array. Merge these sorted array.  Time – O(m) + O(n). Construct a balanced tree from the merged array using the technique discussed in this post. This step takes O(m+n) time.
    3.  In-Place Merge using DLLWe can use a Doubly Linked List to merge trees in place. Following are the steps.
    1) Convert the given two Binary Search Trees into doubly linked list in place (Refer this post for this step).
    2) Merge the two sorted Linked Lists (Refer this post for this step).
    3) Build a Balanced Binary Search Tree from the merged list created in step 2.
    Time complexity of this method is also O(m+n) and this method does conversion in place.


  5. How to sort a big array with many repetitions? GFG
    1. A Basic Sorting algorithm like MergeSortHeapSort would take O(nLogn) time where n is number of elements, can we do better?
    2. A Better Solution is to use Self-Balancing Binary Search Tree like AVL or Red-Black to sort in O(n Log m) time where m is number of distinct elements. The idea is to extend tree node to have count of keys also.
    Complexity = O(n Log m) where m is number of distinct elements.


  6. Find N’th item in a set formed by sum of two arrays. GFG
    1- Run two loops – one for first array and second for second array.
    2- Just consider each pair and store their sum in a self-balancing-BST (which is implemented by set and map in C++). We use set in C++ here as we need to only see if elements are present or absent, we don’t need key, value pairs.
    3- Traverse the set and return the Nth element in the set.
    Time Complexity: O(mn log (mn)) where m is the size of the first array and n is the size of the second arr.


  7. Sort an array according to absolute difference with given value. GFG
    Algo:
    1. Java sort method was custom comparator.
    2.The idea is to use a self balancing binary search tree. We traverse input array and for every element, we find its difference with x and store the difference as key and element as value in self balancing binary search tree. Finally we traverse the tree and print its inorder traversal which is required output.


  8. Given an array of distinct positive integers, the task is to find the maximum product of increasing subsequence of size 3, i.e., we need to find arr[i]*arr[j]*arr[k] such that arr[i] < arr[j] < arr[k] and i < j < k <
    Algo: We need to find the product of increasing sequence. So we pick an index i, and find the largest element on it’s left and largest element on it’s right(check the constraint above).
    The idea is to take each index i = 0, and keep adding it to Self Balancing Tree and find the smallest element till that index. This insert and find operation will take n(logn) time.
    Then we need to find the largest element on right using the logic in question below. This take O(n). While finding the maximum keep checking for maximum count. We don’t need to store the entire max array.
    Based On: Replace every element with the greatest element on right side. GFG This task takes only O(n) time.


  9. Count inversions in an array  (Using Self-Balancing BST). GFG
    Algo: We can modify the default avl tree. We will add a new index size to each node structure(along with height). Whenever we add an element to the left we get the size of elements smaller then that (and this happens recursively).


  10. Given an array find the median using AVL tree.  SO
    If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time O(logn) using the fact that the tree is balanced. To accomplish this, you write a more general procedure Select which accepts a node v and a number k, and finds the kth smallest node at the subtree rooted at v.Suppose that the left subtree (if any) has LL nodes. If kk≤L then we recurse to the left subtree. If k=L+1 then we return v. Otherwise we recurse to the right subtree, reducing k by L+1.
    The running time of this algorithm is linear in the height of the tree, which is O(log⁡n).


  11. Given input as an integer array and an integer ‘k’, find and print element with maximum value from each sub-array of size ‘k’. Article
    Algo:
    1. Start traversing the array from i=0 to n-k-1. Create a window of size k and find the maximum. You will have to keep updating the window – adding new and removing old elements. Finding maximum element from sub-array of size ‘k’ takes O(k) time and there are total ‘n-k+1’ such sub-arrays. Therefore, overall time complexity of this approach is O(k(n-k+1)) which is equivalent to O(nk).
    2.  Use an AVL tree. Insert first k elements into the tree and find the max. Then start from i=0 to i=n-k-1. Delete the first window element and add the last one and keep finding the maximum element in the window.
    creating BST takes O(logk) time. Search and delete operation, insert operation and finding maximum valued node operation, each of these operations takes O(logk) time and we need to perform each of these operations ‘n-k’ times. Therefore, overall time complexity of this algorithm is O(nlogk). Extra space taken in the form of BST is O(k).
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s