http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx
Andersson Trees
Posted on January 5, 2012 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra
Andersson Trees
Search trees
AVL Trees : Inserting a new Item
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]
Convert Binary tree to double linked list in inorder traversal
Problem Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.
Example Input
[Read More]
print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order in Binary Tree
/\*
Two passes with constant space
\*/
int printSum(Tree t, int toPrint)
{
if(t == NULL)
return 0;
int lsum = printSum(t->left, toPrint);
int rsum = printSum(t->right, 0);
int sum = lsum + t->data + rsum;
if(toPrint)
printf("%d ", sum);
printSum(t->right, toPrint);
return sum;
}
/\*
One pass with n space
\*/
int printSum2(Tree t, int a\[\], int \*pos)
{
if(t == NULL)
return 0;
int lsum = printSum2(t->left, a, pos);
(\*pos)++;
int p = \*pos;
int rsum = printSum2(t->right,a, pos);
return a\[p\] = lsum + t->data + rsum;
}
What does flattening list of items into tree means
If I had a list of lists, “flatten” would be the operation that returns a list of all the leaf elements in order, i.e., something that changes:
[[a, b, c], [d, e, f], [g, h i]]
Into
[a, b, c, d, e, f, g, h, i]
For trees, flatting is generating a list of all leaves in natural traversal order (NB: since only leaves are in the result, it doesn’t matter whether you think of this as pre-, in- or post-order traversal.
[Read More]
B + tree
B-tree
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
Red Black tree
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]