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

Find the complexity of an algorithm, Q.1 What is an algorithm? What are the...

Q.1 What is an algorithm? What are the characteristics of a good algorithm? Q.2 How do you find the complexity of an algorithm? What is the relation between the time and space c

String pattern matching, Document processing is quickly becoming one of the...

Document processing is quickly becoming one of the dominant functions of computers. Computers are utilized to edit, search & transport documents over the Internet, and to display d

Define the term ''complexity of an algorithm, Define the term 'complexity o...

Define the term 'complexity of an algorithm; Complexity of an algorithm is the calculate of analysis of algorithm. Analyzing an algorithm means predicting the resources that th

Asymptotic notation, Asymptotic notation Let us describe a few function...

Asymptotic notation Let us describe a few functions in terms of above asymptotic notation. Example: f(n) = 3n 3 + 2n 2 + 4n + 3 = 3n 3 + 2n 2 + O (n), as 4n + 3 is of

Frequency count, what is frequency count with examble? examble?

what is frequency count with examble? examble?

COBOL, write a COBOL program to find the biggest of two numbers

write a COBOL program to find the biggest of two numbers

All pairs shortest paths algorithm, In the last section, we discussed regar...

In the last section, we discussed regarding shortest path algorithm that starts with a single source and determines shortest path to all vertices in the graph. In this section, we

Sorted list using binary search technique, Write an algorithm for searching...

Write an algorithm for searching a key from a sorted list using binary search technique 1.   if (low > high) 2.     return (-1) 3.    mid = (low +high)/2; 4    .if ( X

Deletion of an element from the linear array, Program will demonstrate dele...

Program will demonstrate deletion of an element from the linear array /* declaration of delete_list function */ voiddelete_list(list *, int); /* definition of delete_list

#, if two relations R and S are joined, then the non matching tuples of bot...

if two relations R and S are joined, then the non matching tuples of both R and S are ignored in

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