Aa-trees, Data Structure & Algorithms

Assignment Help:

Red-Black trees have introduced a new property in the binary search tree that means an extra property of color (red, black). However, as these trees grow, in their operations such as insertion, deletion, it becomes complexes to retain all the properties, especially in case of deletion. Therefore, a new type of binary search tree can be defined which has no property of having a color, however has a new property introduced depend on the color that is the information for the new. This information of the level of any node is stored into a small integer (might be 8 bits). Now, AA-trees are described in terms of level of each node rather than storing a color bit with each node. A red-black tree utilized to have several conditions to be satisfied regarding its color and AA-trees have also been designed in such a way that it msut satisfy certain conditions regarding its new property, i.e., level.

The level of a node will be as:

1. Same as its parent, if the node is red.

2. One if the node is a leaf.

3. Level will be one less than the level of its parent, if the color of node is black.

Any red-black tree can be changed into an AA-tree by translating its color structure to levels such that left child is always one level lower than its parent & right child is always similar or at one level lower than its parent. While the right child is at same level to its parent, then a horizontal link is established among them. Thus, we conclude that it is essential that horizontal links are always at the right side and that there might not be two consecutive links. Taking into concern of all the above properties, we illustrates AA-tree as follows

After having a look at the AA-tree above, now we look at different operations which can be performed at such trees.


Related Discussions:- Aa-trees

Algorithms for push and pop operation, Q. Suggest a method of implementing ...

Q. Suggest a method of implementing two stacks in one array such that as long as space is there in an array, you should be capable to add an element in either stack. Using proposed

Binary tree traversals, We have discussed already about three tree traversa...

We have discussed already about three tree traversal methods in the earlier section on general tree. The similar three different ways to do the traversal -inorder , preorder, and p

Explain open addressing, Open addressing The easiest way to resolve a c...

Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

What are the languages which support assertions, What are the languages whi...

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

Which are the two standard ways of traversing a graph, Which are the two st...

Which are the two standard ways of traversing a graph? i. The depth-first traversal   ii. The breadth-first traversal

Representation of arrays?, A representation of an array structure is a mapp...

A representation of an array structure is a mapping of the (abstract) array with elements of type T onto the store which is an array with elements of type BYTE. The array could be

System defined data types, System defined data types:- These are data t...

System defined data types:- These are data types that have been defined by the compiler of any program. The C language contains 4 basic data types:- Int, float,  char and doubl

Definitions of graph, A graph G might be defined as a finite set V of verti...

A graph G might be defined as a finite set V of vertices & a set E of edges (pair of connected vertices). The notation utilized is as follows: Graph G = (V, E) Consider the g

Give example of assertion and abstract data type, Give example of assertion...

Give example of assertion and abstract data type For illustration, consider Natural ADT whose carrier set is the set of non-negative integers and whose operations are the usual

Threaded binary tree, i need the full concept of it... please can anyone pr...

i need the full concept of it... please can anyone provide

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd