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

A tree having ''m'' nodes has (m-1) branches. prove., Q. Prove the hypothes...

Q. Prove the hypothesis that "A tree having 'm' nodes has exactly (m-1) branches".      Ans: A tree having m number of nodes has exactly (m-1) branches Proof: A root

Need help with working out. I dont really get it, Suppose there are exactly...

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

Prefix and Postfix Expressions, Q.   Draw the expression tree of the infix ...

Q.   Draw the expression tree of the infix expression written below and then  convert it intoPrefix and Postfix expressions. ((a + b) + c * (d + e) + f )* (g + h )

Binary search tree (bst), Q. Explain what do we understand by Binary Search...

Q. Explain what do we understand by Binary Search Tree (BST)? Make a BST for the following given sequence of the numbers. 45, 32, 90, 21, 78, 65, 87, 132, 90, 96, 41, 74, 92

Graph terminologies, Graph terminologies : Adjacent vertices: Two vert...

Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

Proof, prove that n/100=omega(n)

prove that n/100=omega(n)

Insertion sort, Data array A has data series from 1,000,000 to 1 with step ...

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Graph, adjacency multilist

adjacency multilist

Binary search, An unsorted array is searched through linear search that sca...

An unsorted array is searched through linear search that scans the array elements one by one until the wanted element is found. The cause for sorting an array is that we search

The search trees are abstract data types, the above title please send give ...

the above title please send give for the pdf file and word file

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