Find the appropriate data structure

 Posted on April 10, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Lets see if you have solutions to the standard problems. Lets define the suitable data structures. Guess the data structues between the 2 data structures provided (in italics). Operations are Insert, DeleteMax, and DeleteMin. balanced tree or sorted doubly-linked list The balanced tree is better since all operations take O(log n) time. The sorted doubly-linked list is O(1) for DeleteMax and DeleteMin, but Insert is O(n); thus, the average time per operation is O(n). [Read More]
kodeknight  balanced trees  array  quiz 

Convert sorted array to Balanced BST

 Posted on February 26, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem  Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height. Examples Input: 1 2 3 4 5 6 7 Output: 4 / \\ 3 6 / \\ / \\ 3 4 6 7 Solutions ** Method 1 - Take the array’s middle element and insert it recursively** Pick up the middle element of the array Set it as the root Recursively build up left and right subtrees with lower and higher halves of the array Here is the code in java: [Read More]
conversion  kodeknight  balanced trees  binary-search-tree  BST  CrackingTheCodingInterview  sorted-array 

Red Black Tree vs AVL Tree vs B-Tree

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

B-tree when you’re managing more than thousands of items and you’re paging them from a disk or some slow storage medium. RB tree when you’re doing fairly frequent inserts, deletes and retrievals on the tree. AVL tree when your inserts and deletes are infrequent relative to your retrievals. think B+ trees are a good general-purpose ordered container data structure, even in main memory. Even when virtual memory isn’t an issue, cache-friendliness often is, and B+ trees are particularly good for sequential access - the same asymptotic performance as a linked list, but with cache-friendliness close to a simple array. [Read More]
kodeknight  red-black-tree  RBT  balanced trees  incomplete  avl 

AVL Tree Index

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

hell-o, im carloe distor, from the most beautiful … Anonymous - Mar 3, 2014hell-o, im carloe distor, from the most beautiful province in benguet, baguio city, i would like to ask if you can do me a favor, because im so tired in doing my homework , IN BINARY TREE (ARRAY REPRESENTATION), INFIXTOPOSTFIX USING STACK AND AVL , THANK YOU, Hi , I don’t think I will be able to help much. [Read More]
tree  kodeknight  balanced trees  avl 

Red Black Tree – Insertion

 Posted on January 7, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Introduction: Please refer the introduction of RBT here. So, we now know the invariants or properties of RBT which make it rbt :) Insertion of element in RBT or red black tree breaks one of the 4 invariants or properties. So we have to fix it in minimal possible way. To assist us with we have 2 solutions : Flipping the color Right and left rotation Insertion: Insertion begins by adding the node much as binary search tree insertion does and by coloring it red. [Read More]
tree  kodeknight  red-black-tree  RBT  balanced trees  incomplete 

Red Black Tree – Deletion

 Posted on January 7, 2012  (Last modified on August 7, 2020)  |  8 minutes  |  Kinshuk Chandra

Deletion of a node from a red black tree is very difficult. During insertion we selected the color of a new node as red to make it easier. We forced a red violation and fixed it. Red violations are easy to fix, and we took full advantage of that to produce a truly elegant recursive algorithm. When you want to delete a node, you don’t have the option of choosing its color. [Read More]
tree  kodeknight  red-black-tree  RBT  balanced trees