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

Methods of collision resolution, Methods of Collision Resolution 1)  Co...

Methods of Collision Resolution 1)  Collision Resolution by separate chaining  2)  Collision Resolution by open addressing

Generate a single sorted list of all n elements, Q. Assume that we have sep...

Q. Assume that we have separated n elements in to m sorted lists. Explain how to generate a single sorted list of all n elements in time O (n log m )?

Data mining assignment, The assignment aims at consolidating your knowledge...

The assignment aims at consolidating your knowledge on data mining techniques and developing practical skills through solving a problem of transcription factor binding sites recogn

Illustrate the visual realism applications, Illustrate the Visual realism a...

Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

Algorithms & flowchart, write an algorithm to find the average number of oc...

write an algorithm to find the average number of occurances of MECHANIL in an english passage

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

Implementation of stack, In this unit, we have learned how the stacks are i...

In this unit, we have learned how the stacks are implemented using arrays and using liked list. Also, the advantages and disadvantages of using these two schemes were discussed. Fo

Perform inorder, QUESTION (a) Construct a binary tree for the following...

QUESTION (a) Construct a binary tree for the following numbers assuming that a number greater than the node (starting from the root) goes to the left else it goes to the right.

B-TREE and AVL tree diffrance, Explain process of B-TREE and what differen...

Explain process of B-TREE and what difference between AVL Tree Using Algorithms

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