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

Enumerate about the data structure, Enumerate about the Data structure ...

Enumerate about the Data structure An arrangement of data in memory locations to signify values of the carrier set of an abstract data type. Realizing computational mechanis

ERM, Hi, can you give me a quote for an E-R diagram

Hi, can you give me a quote for an E-R diagram

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

Data searching, In file access: what is the difference between serial, seq...

In file access: what is the difference between serial, sequential and indexed sequential searching

Explain in brief the asymptotic notations, Question 1 Write the different ...

Question 1 Write the different characteristics of an algorithm Question 2 Explain in brief the asymptotic notations Question 3 Write an algorithm of insertion sort and e

Breadth first search, While BFS is applied, the vertices of the graph are d...

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part

Drawback of sequential file, Following are some of the drawback of sequenti...

Following are some of the drawback of sequential file organisation: Updates are not simply accommodated. By definition, random access is impossible. All records should be

Program insertion of a node into any circular linked list, Program Insertio...

Program Insertion of a node into any Circular Linked List Figure depicts a Circular linked list from which an element was deleted. ALGORITHM (Deletion of an element from a

C, padovan string

padovan string

Program for linear search, Program for Linear Search. Program: Linear S...

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

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