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

Darw a flowchart to inputs top speeds of 5000 cars, Write an algorithm in t...

Write an algorithm in the form of a flowchart that: inputs top speeds (in km/hr.) of 5000 cars Outputs fastest speed and the slowest speed Outputs average (mean) s

File organisation, File organisation might be described as a method of stor...

File organisation might be described as a method of storing records in file. Also, the subsequent implications approaching these records can be accessed. Given are the factors invo

Array implementation of a circular queue, A circular queue can be implement...

A circular queue can be implemented through arrays or linked lists. Program 6 gives the array implementation of any circular queue. Program 6: Array implementation of any Circu

Structure of an avl tree, Given is the structure of an AVL tree: struct ...

Given is the structure of an AVL tree: struct avl { struct node *left; int info; int bf; struct node *right; }; 2) A multiway tree of n order is an ord

Explain merge sort, Merge sort: Merge sort is a sorting algorithm that ...

Merge sort: Merge sort is a sorting algorithm that uses the idea of split and conquers. This algorithm splits the array into two halves, sorts them separately and then merges t

Using array to execute the queue structure, Q. Using array to execute the q...

Q. Using array to execute the queue structure, write down an algorithm/program to (i) Insert an element in the queue. (ii) Delete an element from the queue.

Optimization Methods, Optimal solution to the problem given below. Obtain t...

Optimal solution to the problem given below. Obtain the initial solution by VAM Ware houses Stores Availibility I II III IV A 5 1 3 3 34 B 3 3 5 4 15 C 6 4 4 3 12 D 4 –1 4 2 19 Re

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.

Which data structure is used for implementing recursion, Which data structu...

Which data structure is used for implementing recursion Stack.

Demonstrate that dijkstra''s algorithm, Demonstrate that Dijkstra's algorit...

Demonstrate that Dijkstra's algorithm does not necessarily work if some of the costs are negative by finding a digraph with negative costs (but no negative cost dicircuits) for whi

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