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
Ruby implements Range of T Abstract data type Ruby implements Range of T ADT in its Range class. Elements of carrier set are represented in Range instances by recording interna

Draw a flowchart of a Booth''s multiplication algorithm and explain it.

Assertions and Abstract Data Types Even though we have defined assertions in terms of programs, notion can be extended to abstract data types (which are mathematical entities).

Question 1 Explain the use of algorithms in computing Question 2 Explain time complexity and space complexity of an algorithm Question 3 Explain how you can analyz

Efficiency of Linear Search How much number of comparisons is there in this search in searching for a particular element? The number of comparisons based upon where the reco

Explain about the Structured types - Built-In Types Values of the carrier set are not atomic, consisting rather than several atomic values arranged in some way. Common illu

Explain the term - Branching There are two common ways of branching: case of ..... otherwise ...... endcase  if ..... then ..... else ..... endif   case of

In file access: what is the difference between serial, sequential and indexed sequential searching

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

Question 1 . Give the structure of PL/SQL Blocks and explain Question 2 . Differentiate between PL/SQL functions and procedures Question 3 . Explain the following Par