Advanced data structures - splay trees, Data Structure & Algorithms

This is a unit of which targeted on the emerging data structures. Red- Black trees, Splay trees, AA-trees & Treaps are introduced. The learner must explore the possibilities of applying these concepts in real life.

Splay trees are binary search trees that are self adjusting. Basically, self adjusts means that whenever a splay tree is accessed for insertion or deletion of a node, then that node pushes all the remaining nodes to become root. Thus, we can conclude that any node that is accessed frequently will be at the top levels of the Splay tree.

A Red-Black tree is a type of binary search tree in which each node is either red or black. In spite of that, the root is always black. If a node is red, then its children must be black. For every node, all the paths from a node to its leaves contain the identical number of black nodes.

AA-trees are described in terms of level of each node rather than storing a color bit with each node. AA-trees have also been designed in such a way that it must satisfy certain conditions regarding its new property that means level.

The priorities of nodes of a Treap must satisfy the heap order. Therefore, the priority of any node should be as large as it's parent's. Treap is the simplest of all the trees.

Posted Date: 4/11/2013 6:06:14 AM | Location : United States







Related Discussions:- Advanced data structures - splay trees, Assignment Help, Ask Question on Advanced data structures - splay trees, Get Answer, Expert's Help, Advanced data structures - splay trees Discussions

Write discussion on Advanced data structures - splay trees
Your posts are moderated
Related Questions
1. develop an algorithm which reads two decimal numbers x and y and determines and prints out wether x>y or y>x. the input values, x and y, are whole number > or equal to 0, which

What are the conditions under which sequential search of a list is preferred over binary search? Sequential Search is a preferred over binary search when the list is unordered

The information in the table below is available for a large fund-raising project. a. Determine the critical path and the expected completion time of the project. b. Plot the total


We would like to implement a 2-4Tree containing distinct integer keys. This 2-4Tree is defined by the ArrayList Nodes of all the 2-4Nodes in the tree and the special 2-4Node Root w

Draw a B-tree of order 3 for the following sequence of keys: 2,4,9,8,7,6,3,1,5,10.and delete 8 and 10

D elete a specific Node from Double Linked List as follows DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FORW [ BACK [LOC]]:= FORW[LOC]& BACK [FORW[

what is queues? how it work? and why it used? i want an assignment on queue .....

Define File organization''s and it''s types

As part of an experiment, a school measured heights (in metres) of all its 500 students. Write an algorithm, using a flowchart that inputs the heights of all 500 students and ou