AVL Tree : Rotations
Posted on January 6, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
A tree rotation can be an imtimidating concept at first. You end up in a situation where you’re juggling nodes, and these nodes have trees attached to them, and it can all become confusing very fast. I find it helps to block out what’s going on with any of the subtrees which are attached to the nodes you’re fumbling with, but that can be hard.
Left Rotation (LL) or Single Left rotation
[Read More]Andersson Trees
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Search trees
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
AVL Trees : Inserting a new Item
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Initially, a new item is inserted just as in a binary search tree. Note that the item always goes into a new leaf. The tree is then readjusted as needed in order to maintain it as an AVL tree. There are three main cases to consider when inserting a new node.
Case 1: New Node added to (BF = 0) Node A node with balance factor 0 changes to +1 or -1 when a new node is inserted below it.
[Read More]B + tree
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 0 minutes
| Kinshuk Chandra
B-tree
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Introduction
B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red Black Trees), it is assumed that everything is in main memory.
To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. When the number of keys is high, the data is read from disk in the form of blocks. Disk access time is very high compared to main memory access time.
[Read More]BTree in java
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 0 minutes
| Kinshuk Chandra
Red Black tree
Posted on January 4, 2012
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them “symmetric binary B-trees”, but acquired its modern name in a paper in 1978 by Leo J. Guibas and Robert Sedgewick, due to printing press technology of that time. Unfortunately, they were not able to print the paper in red black ink as was supposed, but the name stayed.
[Read More]Check if Tree is a Balanced Tree
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one
Solution Method 1 - Difference of height at each node should not be greater than 1
Here is the code :
public boolean isBalanced(Node root){ if(root==null){ return true; //tree is empty } else{ int lh = root.
[Read More]Balanced Search tree
Posted on September 10, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Definition
A balanced search tree is a tree which can provide operations like insert, delete and search in O(lg n) where n is the height of tree and lg n is height.
Motivation behind Balanced Search tree
Properties of sorted array
Consider the sorted array. If we have a sorted array, what kinds of operations can we perform on it?
Binary search in O(logn) time. (We use binary search) Select element given ith order statistic in O(1) Computing min/max of array - O(1) Predecessor/Successor - O(1), just find that element and return one before/after it Rank - how many keys stored are less than or equal to the key - O(logn) Output in sorted order - O(n) Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time.
[Read More]