Red-black trees are spiffy because find key, insert, and delete are all done in
log(n) time. Thus, they can be freely used instead of hash-tables, with the
benifit of having the elements in sorted order at all times, and with the
guarantee of operations being in log(n) time.
A balanced binary search tree where the height of the two subtrees (children) of
a node differs by at most one. Look-up, insertion, and deletion are O(log n),
where n is the number of nodes in the tree. An AVL tree is at least as balanced
than a red-black tree.
A stack is a type of data structure - a means of storing information in a
computer. When a new object is entered in a stack, it is placed on top of all
the previously entered objects. In other words, the stack data structure is
just like a stack of cards, papers, credit card mailings, or any other
real-world objects you can think of. When removing an object from a stack, the
one on top gets removed first. This method is referred to as LIFO (last in,
first out).
List data structure is a collection of items accessible one after another
beginning at the head and ending at the tail.
Abstract data type to efficiently support finding the item with the highest
priority across a series of operations. The basic operations are: insert,
find-minimum (or maximum), delete-minimum (or maximum), delete an arbitrary
item, and increase the priority of a item (decrease-key).
Dijkstra's algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra,
is an algorithm that solves the single-source shortest path problem for a directed graph
with nonnegative edge weights.
For example, if the vertices of the graph represent cities and edge weights represent
driving distances between pairs of cities connected by a direct road,
Dijkstra's algorithm can be used to find the shortest route between two cities.
Operation time is O(N*logN), where N is number of nodes.
|