Several operations on a aa-tree, Data Structure & Algorithms

Assignment Help:

The following are several operations on a AA-tree:

1. Searching: Searching is done using an algorithm which is similar to the search algorithm of a binary search tree.

2. Insertion: The insertion procedure always starts from the bottom level. However, whereas performing this function, either of the two troubles can occur:

    (a) Two consecutive horizontal links (right side)

    (b) Left horizontal link.

Whereas studying the properties of AA-tree, we said that conditions (a) and (b) must not be satisfied. Therefore, in order to eliminate conditions (a) and (b), we employ two new functions namely skew ( ) & split( ) depend on the rotations of the node, so that all the properties of AA-trees are retained.

The condition that (a) two consecutive horizontal links in an AA-tree can be eliminated by a left rotation by split( ) while the condition (b) can be eliminated by right rotations through function show( ). Either of these functions can eliminate this condition, but can also arise the other condition. Let us show it with an example. Imagine, in the AA-tree of Figure, we have to insert node 50.

According to the condition, the node 50 will be added at the bottom level in such a way that it satisfies Binary Search tree property also

Now, we have to be aware as to how this left rotation is performed. Keep in mind, that rotation is introduced in Red-black tree and these rotations (left and right) are the similar as we performed in a Red-Black tree. Now, again split ( ) has removed its condition although has created skew conditions. Thus, skew ( ) function will now be called again and again till a complete AA-tree with a no false condition is obtained.

A skew problem arises since node 90 is two-level lower than its parent 75 and thus in order to avoid this, we call skew / split function again.

Therefore, introducing horizontal left links, to avoid left horizontal links and making them right horizontal links, we make three calls to skew and then two calls to split to remove consecutive horizontal links

A Treap is another kind of Binary Search tree and has one property distinct from other types of trees. Each of the nodes in the tree stores an item, a left & right pointer and a priority that is randomly assigned while the node is created. Whereas assigning the priority, it is essential that the heap order priority has to be maintained: node's priority must be at least as large as its parent's. A treap is both binary search tree with respect to node elements and a heap with respect to node priorities.


Related Discussions:- Several operations on a aa-tree

B-tree of minimum degree t can maximum pointers in a node, A B-tree of mini...

A B-tree of minimum degree t can maximum pointers in a node T pointers in a node.

frequenty count of function, Ask question find frequency count of function...

Ask question find frequency count of function- {for(i=1;i {for(j=1;j {for(k=1;k } } }

Enumerate the types in ruby, Enumerate the Types in Ruby Ruby is a pure...

Enumerate the Types in Ruby Ruby is a pure object-oriented language, meaning that all types in Ruby are classes, and each value in a Ruby program is an instance of a class. Thi

#title.state charts., explain two strategies to implement state charts with...

explain two strategies to implement state charts with the help of an example of each.

Array implementation of a multiqueue, Program gives the program segment by ...

Program gives the program segment by using arrays for the insertion of an element to a queue into the multiqueue. Program: Program segment for the insertion of any element to t

Randomized algorithm, need an expert to help me with the assignment

need an expert to help me with the assignment

The complexity ladder, The complexity Ladder: T(n) = O(1). It is ca...

The complexity Ladder: T(n) = O(1). It is called constant growth. T(n) does not raise at all as a function of n, it is a constant. For illustration, array access has this c

Bubble sort, Q. The reason bubble sort algorithm is inefficient is that it ...

Q. The reason bubble sort algorithm is inefficient is that it continues execution even after an array is sorted by performing unnecessary comparisons. Therefore, the number of comp

Various passes of bubble sort, Q. Show the various passes of bubble sort on...

Q. Show the various passes of bubble sort on the unsorted given list 11, 15, 2, 13, 6           Ans: The given data is as follows:- Pass 1:-     11   15   2     13

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