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

Illustrate the operations of the symbol abstract data type, The operations ...

The operations of the Symbol ADT The operations of the Symbol ADT are the following. a==b-returns true if and only if symbols a and bare identical. a symbol bin Unico

Queues, what is the difference between data type and abstract data type

what is the difference between data type and abstract data type

Algorithm, Write an algorithm for compound interest.

Write an algorithm for compound interest.

Complexity of an algorithm, An algorithm is a sequence of steps to solve a ...

An algorithm is a sequence of steps to solve a problem; there may be more than one algorithm to solve a problem. The choice of a particular algorithm depends upon following cons

Lists, In the earlier unit, we have discussed about the arrays. Arrays are ...

In the earlier unit, we have discussed about the arrays. Arrays are data structures of fixed size. Insertion & deletion involves reshuffling of array elements. Thus, arraymanipulat

Which sorting methods sorting a list which is almost sorted, Which sorting ...

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

Explain the memory function method, Explain the Memory Function method ...

Explain the Memory Function method The Memory Function method seeks to combine strengths of the top  down and bottom-up approaches  to  solving  problems  with  overlapping  su

Efficiency of linear search, Efficiency of Linear Search How much numbe...

Efficiency of Linear Search How much number of comparisons is there in this search in searching for a particular element? The number of comparisons based upon where the reco

How can the third dimension be displayed on the screen, How can the third d...

How can the third dimension be displayed on the screen The main problem in visualization is the display of three-dimensional objects and scenes on two-dimensional screens. How

How to write binary search algorithm?, Q. Write down the binary search algo...

Q. Write down the binary search algorithm and trace to search element 91 in following given list: 13          30          62           73         81         88             91

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