Data Structures and Algorithms

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of non-random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown.

This framework is a patented software framework introduced by Google to support distributed computing on large sets of data.

Profiling is a form of dynamic program analysis that measures, for example, the space or time complexity of a program, the usage of particular instructions, or frequency and duration of function calls. The most common use of profiling information is to aid program optimization.

In a dynamic data structure, it is mandatory to use a concept of pointer. There is no alternative way to pointers for implementing the dynamic data structure.

The statement p=Num; is the correct way to store the address in a pointer variable p. Here there is no requirement of address operator(&) before the array name.

Compiler implementations usually use hash tables to look up identifiers. A hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

Graphs and trees are linked abstract data structures composed of nodes. Each node contains a value and also one or more pointers to other nodes. Graphs can be used to represent networks, while trees are generally used for sorting and searching, having their nodes arranged in some relative order based on their values.

A union is a value that may have any of several representations or formats, or it is a data structure that consists of a variable which may hold such a value.

A queue is a First In First Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed.

Recursion uses stack data structure.

Quadratic Probing is used for collision resolution in hashing.It is a technique in which the interval between probes is increased by adding the successive outputs of a quadratic polynomial to the starting value given by the original hash computation.

The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node,typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.

By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are Prim's minimal spanning tree algorithm and Dijkstra's shortest path problem.

The Breadth First Search algorithm uses a queue data structure to store intermediate results as it traverses the graph.

A walk in which the children are traversed before their respective parents are traversed is called a post-order walk.