Advanced data structures - splay trees, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Advanced data structures - splay trees

Make adjacency matrix for un-directed graph, Q. Describe the adjacency matr...

Q. Describe the adjacency matrix and make the same for the given undirected graph.    Ans: The representation of Adjacency Matrix: This representation consists of

Functions and modelling the data flows, Read the scenario (Pickerings Prope...

Read the scenario (Pickerings Properties). (a) List the functions of the system, as perceived by an external user. (b) List the external entities. Note that because we are mo

Determine in brief the painter algorithm, Determine in brief the Painter A...

Determine in brief the Painter Algorithm a) The farthest polygon, namely the rectangle PQRS, is stored first. (b) The next farthest, the quadrilateral ABCD, is superpo

Worst case and average case, Worst Case: For running time, Worst case runn...

Worst Case: For running time, Worst case running time is an upper bound with any input. This guarantees that, irrespective of the type of input, the algorithm will not take any lo

Define rule-based expert system, 1. Define the following terms in a rule-ba...

1. Define the following terms in a rule-based expert system? a) Knowledge base b) Inference engine 2. What is a fuzzy rule? Explain the difference between classical and fuzzy

Depth First Search Through Un-weighted Connected Graph , Q. Write down the ...

Q. Write down the algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neith

Calculate address of an element in an array., Q. Explain the technique to c...

Q. Explain the technique to calculate the address of an element in an array. A  25 × 4  matrix array DATA is stored in memory in 'row-major order'. If base  address is 200 and

Abstract data types, Abstract Data Types :- A useful tool for specifying th...

Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem

Insertion into a red-black tree, The insertion procedure in a red-black tre...

The insertion procedure in a red-black tree is similar to a binary search tree i.e., the insertion proceeds in a similar manner but after insertion of nodes x into the tree T, we c

Explain about hubs, Hubs - In reality a multiport repeater - Connect...

Hubs - In reality a multiport repeater - Connects stations in a physical star topology - As well may create multiple levels of hierarchy to remove length limitation of 10

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