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

What is a linear array, What is a linear array? An array is a way to re...

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

Stack, Explain in detail the algorithmic implementation of multiple stacks....

Explain in detail the algorithmic implementation of multiple stacks.

State warnock algorithm, Warnock's Algorithm An interesting approach to...

Warnock's Algorithm An interesting approach to the hidden-surface problem was presented by Warnock. His method does not try to decide exactly what is happening in the scene but

Define an array, Define an array. Array is made up of same data structu...

Define an array. Array is made up of same data structure that exists in any language. Array is set of same data types. Array is the collection of same elements. These same elem

Prime''z algorithem, Ask question #explain it beriflyMinimum 100 words acce...

Ask question #explain it beriflyMinimum 100 words accepted#

A bst is traversed in which order recursively, A  BST is traversed in the ...

A  BST is traversed in the following order recursively: Right, root, left e output sequence will be in In Descending order

Define graph, A graph is a mathematical structure giving of a set of vertex...

A graph is a mathematical structure giving of a set of vertexes (v1, v2, v3) and a group of edges (e1, e2, e3). An edge is a set of vertexes. The two vertexes are named the edge en

Non Recursive Algorithm to Traverse a Binary Tree, Q. Write down a non recu...

Q. Write down a non recursive algorithm to traverse a binary tree in order.                    Ans: N on - recursive algorithm to traverse a binary tree in inorder is as

Number of operations possible on ordered lists and arrays, Q. Enumerate num...

Q. Enumerate number of operations possible on ordered lists and arrays.  Write procedures to insert and delete an element in to array.

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