AA - tree implementation in java
Posted on March 31, 2011
(Last modified on August 7, 2020)
| 7 minutes
| Kinshuk Chandra
An AA tree in computer science is a red-black tree with one additional rule. Unlike red-black trees, RED nodes on an AA tree can only be added as a right subchild. In other words, no RED node can be a left subchild. This results in the simulation of a 2-3 tree instead of a 2-3-4 tree, which greatly simplifies the maintenance operations.
The following code shows how to implement a AA tree in Java:
[Read More]Anagram Trees : Part 2
Posted on February 17, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
One nice thing about working at Google is that you are surrounded by very smart people. I told one of my coworkers about the anagram tree idea, and he immediately pointed out that reordering the alphabet so that the least frequently used letters come first would reduce the branching factor early in the tree, which has the effect of reducing the overall size of the tree substantially. While this seems obvious in retrospect, it’s kind of unintuitive - usually we try to _increase_ the branching factor of n-ary trees to make them shallower and require fewer operations, rather than trying to reduce it.
[Read More]DFS and BFS on trees, with and without recurssion
Posted on April 26, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Some cardinals
Posted on March 4, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A binary tree with n nodes has exactly n+1 null nodes
If there are n nodes, there exist 2^n-n different trees.
No. of nodes in a full binary tree is of the form 2^k - 1
Bucket size is 1, when the overlapping and collision occur at same time
Because If there is only one entry possible in the bucket, when the collision occurs,
[Read More]Tree
Posted on January 29, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Tree are of various types:
- BST
BST - Index
Posted on January 29, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Common Operations on BST Understanding functions of BST – insert, size and traversal Deleting a node from BST Implementing a BST in C Traversals are covered seperately below.
Traversal in BST: Inorder, pre order and post order traversal(recursive approach)
Inorder, pre order and post order traversal(iterative approach)
Level order traversal
Threaded binary tree
DFS and BFS on tree
Given the expression tree, calculate the expression
Construct a tree, given its inorder and pre-order
[Read More]Threaded binary tree
Posted on January 25, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Since traversing the three is the most frequent operation, a method must be devised to improve the speed. In case of iterative traversal, speed is less than recursive one. So we cans use Threaded tree. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. This tree is called right in-threaded binary tree. An extra field called the rthread is used.
[Read More]Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order traversal strings.
Posted on January 25, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
For Inorder And Preorder traversals
inorder = g d h b e i a f j c preorder = a b d g h e i c f j
Scan the preorder left to right using the inorder sequence to separate left and right subtrees. For example, “a” is the root of the tree; “gdhbei” are in the left subtree; “fjc” are in the right subtree. “b” is the next root; “gdh” are in the left subtree; “ei” are in the right subtree.
[Read More]Given an expression tree, evaluate the expression and obtain a paranthesized form of the expression.
Posted on January 25, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The code below prints the paranthesized form of a tree.
**print_infix_exp(node * root)** { if(root) { printf("("); infix_exp(root->left); printf(root->data); infix_exp(root->right); printf(")"); } }
Creating a binary tree for a postfix expression
`
*node create_tree(char postfix[])
{
node *temp, *st[100];
int i,k;
char symbol;
for(i=k=0; (symbol = postfix[i])!=’\0’; i++)
{
temp = (node *) malloc(sizeof(struct node));//temp = getnode();
temp->value = symbol;
temp->left = temp->right = NULL;
if(isalnum(symbol))
st[k++] = temp;
[Read More]First / Lowest common ancestor (LCA) of 2 node in binary tree
Posted on January 25, 2010
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Problem
Case 1 - Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
Case 2- What will you do if it is Binary search tree
Example
So for example look into below figure:
So for node 4 and 14, LCA is 8.
[Read More]