Algorithms and Data Structures Glossary (Starting with "R")
By
www.nist.gov,
Gaithersburg, Maryland, U.S.A.
paul
. black [at] nist . gov
http://www.nist.gov/dads
Become a member of TranslationDirectory.com at just
$8 per month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
R
 RabinKarp: see KarpRabin
 radix sort
 radix tree: see Patricia tree
 ragged matrix
 Raita
 random access machine
 randomization
 randomized algorithm
 randomized binary search tree
 randomized complexity
 randomized polynomial time: see RP
 randomized rounding
 randomized search tree
 RandomizedSelect
 random number generator
 random sampling
 random search
 range
 range sort
 rank
 rapid sort
 Ratcliff/Obershelp pattern recognition
 RBST: see randomized binary search tree
 reachable
 rebalance
 recognizer
 rectangular matrix
 rectilinear
 rectilinear Steiner tree
 recurrence equations: see recurrence relation
 recurrence relation
 recursion
 recursion termination
 recursion tree
 recursive
 recursive data structure
 recursive doubling: see pointer jumping
 recursive language: see decidable language
 recursively enumerable language
 recursively solvable: see decidable problem
 redblack tree
 reduced basis
 reduced digraph
 reduced ordered binary decision diagram
 reduction
 reflexive
 regular decomposition
 rehashing: see double hashing
 relation
 relational structure
 relative performance guarantee
 relaxation
 relaxed balance
 repeated squaring
 rescalable
 reservoir sampling
 restricted universe sort
 result cache
 Reverse Colussi
 Reverse Factor
 Rfile
 Rice's method
 right rotation
 rightthreaded tree
 RNG: see random number generator
 ROBDD: see reduced ordered binary decision diagram
 Robin Hood hashing
 root
 root balance: see balance
 rooted tree
 rotate left: see left rotation
 rotate right: see right rotation
 rotation
 rough graph
 RP
 R^{+}tree
 R^{*}tree
 Rtree
 run time
radix sort
(algorithm)
Definition:
A multiple pass distribution sort algorithm that distributes each item to a bucket according to part of the item's key beginning with the least significant part of the key. After each pass, items are collected from the buckets, keeping the items in order, then redistributed according to the next most significant part of the key.
Generalization (I am a kind of ...)
distribution sort.
Note:
Here is a simple example of the sort. Suppose the input keys are 34, 12, 42, 32, 44, 41, 34, 11, 32, and 23. Four buckets are appropriate, since there are four different digits. The first pass distributes the keys into buckets by the least significant digit. Half way through the first pass, the buckets contain the following, where each line is a bucket. 12 42 32 34 44 When the first pass is done, we have the following. 41 11 12 42 32 32 23 34 44 34 We collect these, keeping their relative order: 41 11 12 42 32 32 23 34 44 34. Now we distribute by the next most significant digit, which is the highest digit, and we get the following. 11 12 23 32 32 34 34 41 42 44 When we collect them, they are in order: 11 12 23 32 32 34 34 41 42 44. [CLR90, page 179] gives an inplace variant of radix sort which uses a stable sort on each digit of the key.
Radix sort can be particularly effective on a linked list. Rather than buckets, put items in linked lists. At the end of a pass collect the items by "sewing" the lists together: make the tail of each list point to the head of the next list. (After Steven Pigeon, QuickSort and Radix Sorts on Lists, Dr. Dobb's Journal, May 2002, pages 8994.)
Author: PEB
ragged matrix
(data structure)
Definition:
A matrix having irregular numbers of items in each row.
Note:
An upper triangular matrix or a lower triangular matrix are usually not thought of as being ragged since the number of items in each row is regular (changing by one from row to row).
For example
Author: PEB
random access machine
(definition)
Definition:
A model of computation whose memory consists of an unbounded sequence of registers, each of which may hold an integer. In this model, arithmetic operations are allowed to compute the address of a memory register.
Note:
From Algorithms and Theory of Computation Handbook, page 524, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
randomized algorithm
(definition)
Definition:
Any algorithm that makes random (or pseudorandom) choices.
Generalization (I am a kind of ...)
algorithm.
Specialization (... is a kind of me.)
Monte Carlo algorithm, Las Vegas algorithm, skip list insert, randomized binary search tree, reservoir sampling.
Note:
From Algorithms and Theory of Computation Handbook, pages 1017 and 1521, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC. Some algorithms make random choices initially to avoid any fixed worst case.
Author: CRCA
randomized binary search tree
(data structure)
Definition:
A binary search tree in which nodes have a randomly assigned priority. Updates keep priorities in heap order instead of keeping balance information and doing rebalance operations.
Also known as cartesian tree, RBST.
Generalization (I am a kind of ...)
treap.
Note:
Also called a treap, but strictly a treap does not define how priorities are assigned. Because of the random priority, the trees are always expected to be nearly balanced, regardless of the number, kind and order of updates made. The expected worst case is O(log n) for any update or search in a RBST of size n.
Author: CM
More information
Conrado Martinez and Salvador Roura, Randomized Binary Search Trees, Journal of the ACM, 45(2):288323, March 1998. Jean Vuillemin, A Unifying Look at Data Structures, CACM, 23(4):229239, April 1980.
randomized complexity
(definition)
Definition:
The expected running time of the best possible randomized algorithm over the worst input.
Note:
From Algorithms and Theory of Computation Handbook, page 2621, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
randomized rounding
(algorithm)
Definition:
A probabilistic method to convert a solution of a relaxed problem into an approximate solution to the original problem.
Note:
From Algorithms and Theory of Computation Handbook, page 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
randomized search tree
(data structure)
Definition:
See randomized binary search tree.
Author: PEB
More information
Raimund G. Seidel and Cecilia R. Aragon, Randomized Search Trees, Algorithmica, 16(4/5):464497 (1996). Also in 30th Annual Symposium on Foundations of Computer Science, pages 540545, Research Triangle Park, North Carolina, 30 October1 November 1989. IEEE.
random number generator
(algorithm)
Definition:
See pseudorandom number generator.
Also known as RNG.
Note: Any computer program is likely to generate
pseudorandom numbers, not actually random numbers.
This is important when, say, simulations are sensitive
to subtle patterns in the "random" numbers or security
depends on the numbers being unpredictable.
Author: PEB
random sampling
(algorithmic technique)
Definition:
Using a randomly selected sample of the data to help solve a problem on the whole data.
Note:
From Algorithms and Theory of Computation Handbook, page 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
random search
(algorithm)
Definition:
Repeatedly check items in an array at random until successful.
Generalization (I am a kind of ...)
search, Las Vegas algorithm.
Note:
If any item with a certain value is needed and there are many items with that value, a random search has lower expected time than linear search. If parallel processing is available, random search is fault tolerant (processors may stop working without causing failure) and reasonably efficient.
Author: PEB
More information
This definition after Kenneth A. Berman and Jerome L. Paul, Fundamentals of Sequential and Parallel Algorithms, Sect. 18.4, pages 639640, PWS Publishing Co., Boston, MA, 1996.
range
(definition)
Definition:
The possible results of a function or relation. For instance, the range of cosine is [1,+1].
Author: PEB
range sort
(algorithm)
Definition:
A bucket sort where the function to determine the bucket is based on the range of possible keys.
Generalization (I am a kind of ...)
bucket sort, distribution sort.
Specialization (... is a kind of me.)
pigeonhole sort.
Author: ASK
rank
(definition)
Definition:
For a given match, this is the number of matches in a longest chain terminating with that match, inclusive.
Note:
From Algorithms and Theory of Computation Handbook, page 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
rapid sort
(algorithm)
Definition:
A 2pass sort algorithm that is efficient when the range of keys is approximately equal to the number of items and only keys are sorted. The first pass counts the occurrences of each key in an auxiliary array. The second pass goes over the auxiliary array writing the counted number of keys to the destination.
Generalization (I am a kind of ...)
pigeonhole sort.
Note:
Rapid sort only sorts keys. In other words, items to be sorted consist solely of the key; there is no additional data in items. More formally, the algorithm is efficient if the range of key is O(number of items), that is, less than or equal to the number of items, with a possible constant multiplier. If the range is much larger than the number of keys, the second pass is inefficient.
Pigeonhole sort moves items, that is, the key and additional data. Since rapid sort sorts keys, it "moves items" by counting or writing occurrences. Counting sort counts the number of occurrences in an auxiliary array then uses the array to compute each item's final destination. In contrast, rapid sort uses the auxiliary array to write the keys in the final destination.
Author: PEB
Ratcliff/Obershelp pattern recognition
(algorithm)
Definition:
Compute the similarity of two strings as the number of matching characters divided by the total number of characters in the two strings. Matching characters are those in the longest common subsequence plus, recursively, matching characters in the unmatched region on either side of the longest common subsequence.
Generalization (I am a kind of ...)
string matching with errors.
Author: PEB
More information
John W. Ratcliff and David Metzener, Pattern Matching: The Gestalt Approach, Dr. Dobb's Journal, page 46, July 1988.
reachable
(definition)
Definition:
A vertex v is reachable from another vertex u if there is a path of any length from u to v.
Note:
Usually applied only to directed graphs, since any vertex in a connected, undirected graph is reachable from any other vertex.
Author: JM
rebalance
(algorithm)
Definition:
Restore balance to a tree.
Author: PEB
recognizer
(definition)
Definition:
A finite state machine with one or more states designated as accepting states. An input string is accepted if there is a path from the start state to an accepting state.
Author: PEB
rectangular matrix
(data structure)
Definition:
An n × m matrix, or, one whose size may not be the same in both dimensions.
Generalization (I am a kind of ...)
uniform matrix.
Author: PEB
rectilinear
(definition)
Definition:
Distance, paths, lines, etc. which are always parallel to axes at right angles. For example, a path along the streets of Salt Lake City or the moves of a rook in chess.
Author: PEB
rectilinear Steiner tree
(definition)
Definition:
A minimumlength rectilinear tree connecting a set of points, called terminals, in the plane. This tree may include points other than the terminals, which are called Steiner points.
Author: JLG
recurrence relation
(definition)
Definition:
The specification of a sequence of values in terms of earlier values in the sequence and base values.
Also known as recurrence equations.
Note:Fibonacci numbers may be described by the recurrence relation F(n) = F(n1) + F(n2), where F(1)=1 and F(2)=1. Execution times are often computed by setting up, then solving, a unary recurrence relation, such as T(n) = 2T(n/4) + 2.
From Algorithms and Theory of Computation Handbook, page 126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
recursion
(algorithmic technique)
Definition:
An algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task.
Specialization (... is a kind of me.)
tail recursion, collective recursion.
Note:
Every recursive solution involves two major parts or cases, the second part having three components.  base case(s), in which the problem is simple enough to be solved directly, and
 recursive case(s). A recursive case has three components:
 divide the problem into one or more simpler or smaller parts of the problem,
 call the function (recursively) on each part, and
 combine the solutions of the parts into a solution for the problem.
Depending on the problem, any of these may be trivial or complex. Here are some exercises to help you learn recursion. Although recursion may not be the best way to write some of these functions, it is good practice.  Write a function to compute the sum of all numbers from 1 to n.
 Write a function to compute 2 to the power of a nonnegative integer.
 Write a function to compute any number to the power of a nonnegative integer.
 Write a function to compute the nth Fibonacci number.
 Write a function to compute the greatest common divisor (GCD) of two positive integers with Euclid's algorithm.
 Write a function to compute GCD based on the following relations
 GCD(2m, 2n) = 2 * GCD(m, n)
 GCD(2m, 2n+1) = GCD(m, 2n+1)
 GCD(2m+1, 2n+1) = GCD(nm, 2m+1) if m < n
 GCD(m, m) = m
(after "ML for the Working Programmer", page 49).  Write a function to compute any number to the power of a nonnegative integer using repeated squaring, that is, x^{2n} = (x^{n})² and x^{2n+1} = x × x^{2n}. (after "ML for the Working Programmer", pages 45 and 46).
 Write a function to compute the integer square root of a nonnegative integer using square_root(4x) = 2*square_root(x). (after "ML for the Working Programmer", pages 48 and 49).
Authors: PEB,PR
More information
See dynamic algorithms for an example of one tradeoff between speed and clarity for a recursive vs. an iterative implementation. See the notes for the towers of Hanoi puzzle for another recursive and iterative solution. Bro. David Carlson's tutorial and code (C++) with examples for factorial, Fibonacci, quicksort, and merge sort.
recursion termination
(definition)
Definition:
The point when conditions are met and a recursive algorithm ceases calling itself and begins to return values.
Author: PR
recursion tree
(definition)
Definition:
A method to analyze the complexity of an algorithm by diagramming the recursive function calls.
Formal Definition: A recursion tree T(p) of degree p is either (i) null or (ii) has p children which are recursion trees.
Note:
Also known as an "Rtree".
Author: PEB
More information
After [GCG92] and [CLR90, page 59]. Suggested by Rama Maiti, 19 August 2001.
recursive
(data structure)
Definition:
(1) A data structure that is partially composed of other instances of the data structure. For instance, a tree is composed of smaller trees (subtrees) and leaf nodes, and a list may have other lists as elements. (2) An algorithm in which functions might call themselves. For instance, quicksort or heapify.
Note:
Infinite data structures may be represented by having a tree include (point back to) itself recursively, a list include itself, etc. Recursive data structures are often best handled with a recursive algorithm, or an algorithm using recursion.
Author: PEB
More information
See the entry at recursion for links, explanations, exercises, cross references, etc.
recursive data structure
(definition)
Definition:
A data structure that is partially composed of smaller or simpler instances of the same data structure. For instance, a tree is composed of smaller trees (subtrees) and leaf nodes, and a list may have other lists as elements.
Authors: PR,PEB
recursively enumerable language
(definition)
Definition:
A language accepted by a Turing machine.
Note:
From Algorithms and Theory of Computation Handbook, pages 2419 and 2620, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
redblack tree
(data structure)
Definition:
A nearlybalanced tree that uses an extra bit per node to maintain balance. No leaf is more than twice as far from the root as any other.
Formal Definition: A redblack tree with n internal nodes has height at most 2log_{2}(n+1).
Also known as symmetric binary Btree.
Generalization (I am a kind of ...)
Btree.
Specialization (... is a kind of me.)
AVL tree.
Aggregate child (... is a part of or used in me.)
left rotation, right rotation.
Note:
The extra bit "colors" the node red or black, hence the name. These were called "symmetric binary Btrees" when first invented. The red/black naming and explanation was given by Guibas and Sedgewick. An AVL tree is at least as balanced as a redblack tree.
Author: PEB
More information
Rudolf Bayer, Symmetric Binary BTrees: Data Structures and Maintenance Algorithms, Acta Informatica, 1:290306, 1972. Leo J. Guibas and Robert Sedgewick, A Dichromatic Framework for Balanced Trees, Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pages 821. IEEE Computer Society, 1978.
reduced basis
(definition)
Definition:
A basis for a lattice that is nearly orthogonal.
Note:
From Algorithms and Theory of Computation Handbook, page 3239, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
reduction
(definition)
Definition:
A computable transformation of one problem into another.
Note:
From Algorithms and Theory of Computation Handbook, page 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
reflexive
(definition)
Definition:
A binary relation R for which a R a for all a.
Note:
The relation "equals" is reflexive since everything is equal to itself. However the relation "less than" is not reflexive. The relation "likes" is not reflexive either since some people do not like themselves.
Author: PEB
regular decomposition
(definition)
Definition:
A space decomposition method that partitions the underlying space by recursively halving it across the various dimensions instead of permitting the partitioning lines to vary.
Note:
From Algorithms and Theory of Computation Handbook, page 1824, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
relation
(definition)
Definition:
A computation which takes some inputs and yields an output. Any particular input may yield different outputs at different times. Formally, a mapping from each element in the domain to one or more elements in the range.
Specialization (... is a kind of me.)
function, binary relation.
Note:
Cosine is a function, since every angle has a specific cosine. Its inverse cos^{1}(x) is a relation, since a cosine value maps to many (for this relation, infinitely many) angles.
Author: PEB
relational structure
(data structure)
Definition:
The counterpart in formal logic of a data structure or class instance in the objectoriented sense. Examples are strings, directed graphs, and undirected graphs. Sets of relational structures generalize the notion of languages as sets of strings.
Note:
From Algorithms and Theory of Computation Handbook, page 2921, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
relative performance guarantee
(definition)
Definition:
The maximum ratio by which the result of a ρapproximation algorithm may depart from the optimal solution.
Also known as performance ratio.
Note:
From Algorithms and Theory of Computation Handbook, page 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
relaxation
(definition)
Definition:
An optimization problem with an enlarged feasible region (and extended objective function) compared with an original optimization problem. Typically, the relaxation is considerably easier to solve than the original.
Note:
From Algorithms and Theory of Computation Handbook, pages 3239 and 3418, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
relaxed balance
(definition)
Definition:
When rebalancing a search tree is independent of updating the tree.
Note:
Normally rebalancing is tightly coupled to updating: as soon as the tree is updated, rebalancing operations are applied until the given balance constraints are again fulfilled. In search trees with relaxed balance, updating and rebalancing are processes which can be controlled separately. Typically, this means that balance constraints must be relaxed such that an update can leave the tree in a welldefined state. Thus, the assumptions under which rebalancing is carried out change. This poses the problem of still carrying out the rebalancing efficiently.
Author: KSL
repeated squaring
(algorithm)
Definition:
Compute the n^{th} power of an expression in Θ(log n) steps by repeatedly squaring an intermediate result and multiplying an accumulating value by the intermediate result when appropriate.
Note:
To find x^{13} one could multiple 13 x's together. This is slow if multiplication is time consuming (e.g., matrix multiplication) or the exponent is very large. Instead, write the exponent in binary notation. 13 = 1101 Start with a "squares" value (s) equal x and an "accumulated" value (a) equal 1. Reading from least significant bit to most significant, when there is a 1 in the binary notation, multiply a by s. Keep squaring s.
s  a   x^{1}  1     Least significant bit of exponent is 1, so multiply a = a * s  x^{1}  x^{1}     Square s  x²  x^{1}     Next bit is 0, so don't multiply  x²  x^{1}     Square s  x^{4}  x^{1}     Next bit is 1, so multiply  x^{4}  x^{5}     Square s  x^{8}  x^{5}     Highest bit is 1, so multiply  x^{8}  x^{13}   Why does this work? Consider the exponent decomposed into binary notation. x^{13} = x^{1101} = x^{(1*2^3 + 1*2^2 + 0*2^1 + 1*2^0)} = x^{1*2^3}* x^{1*2^2}* x^{0*2^1}* x^{1*2^0} = x^{2^3} * x^{2^2} * 1 * x^{2^0} = x^{8} * x^{4} * x^{1} The values to be multiplied are successive squares (variable s above). By multiplying appropriate powers, we can compute an integral power in logarithmic time. There are many variations. For instance, to find a^{n} mod m for very large n, reduce modulo m along the way. Fibonacci numbers can be computed quickly by repeated squaring of a suitable expression. If addition and doubling were much faster than multiplication, one could multiply by repeatedly doubling and summing.
Author: PEB
rescalable
(definition)
Definition:
An optimization for which given any instance of the problem and integer λ >0, there is an easily computed second instance that is the same except that the objective function for the second instance is (elementwise) λ times the objective function of the first instance. For such problems, the best one can hope for is a relative performance guarantee, not an absolute performance guarantee.
Note:
From Algorithms and Theory of Computation Handbook, page 3418, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
reservoir sampling
(algorithm)
Definition:
An algorithm to randomly select k items from a stream of items of unknown length. Save the first k items in an array of size k. For each item j, j > k, choose a random integer M from 1 to j (inclusive). If M ≤ k, replace element M of the array with item j.
Generalization (I am a kind of ...)
randomized algorithm.
Note:
Each possible selection of k items has an equal probability of occurring. This algorithm is an inmemory variant of Knuth's Algorithm R [Knuth97, 2:144, Sect. 3.4.2]. He credits Alan G. Waterman. This algorithm is suggested in exercise 10.
Author: PEB
More information
Vitter's algorithms X, Y, and Z use far fewer random numbers by choosing how many items to skip, rather than deciding whether or not to skip each item. Jeffrey Scott Vitter, Random Sampling with a Reservoir, ACM Transactions on Mathematical Software (TOMS), 11(1):3757, March 1985. Available online, for instance at http://www.cs.umd.edu/~samir/498/vitter.pdf.
restricted universe sort
(definition)
Definition:
A sort algorithm that operates on the basis that the keys are members of a restricted set of values. They may not require comparisons of keys to perform the sorting.
Note:
From Algorithms and Theory of Computation Handbook, page 323, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Rfile
(data structure)
Definition:
A spatial access method which divides space into a hierarchically of nested boxes. Objects are indexed in the lowest cell which completely contains them.
Note:
After [GG98].
Author: PEB
Rice's method
(definition)
Definition:
A method of complex asymptotics that can handle certain alternating sums arising in the analysis of algorithms.
Note:
From Algorithms and Theory of Computation Handbook, page 1435, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
right rotation
(algorithm)
Definition:
(1) In a binary search tree, pushing a node N down and to the right to balance the tree. N's left child replaces N, and the left child's right child becomes N's left child. (2) In an array, moving all items to the next higher location. The last item is moved to the first location, which is now vacant. (3) In a list, removing the tail and inserting it at the head.
Also known as rotate right.
Note:
Also known as right single rotation, in contrast with a double right rotation.
Author: BB
rightthreaded tree
(data structure)
Definition:
A variant of a threaded tree in which only the right thread, i.e. link to the successor, of each node is maintained.
Generalization (I am a kind of ...)
threaded tree.
Note:
Keeping only the right thread, rather than both left and right threads, keeps it quick to find the next greater key and faster to insert and delete.
Author: PEB
Robin Hood hashing
Definition:
In case of collision, the item with the longer probe sequence stays in the position. The other item is moved. This tends to equalize the length of probe sequences.
Aggregate parent (I am a part of or used in ...)
open addressing.
Note:
An item that was previously placed in a position may be displaced by a later arrival. The displaced item is then moved along. It may find an empty position, displace another item and take its position, or leave the other item and check the next position.
Author: PEB
More information
Pedro Celis, Robin Hood Hashing, Doctoral Thesis, Technical Report CS8614, Computer Science Department, University of Waterloo, Waterloo, ON, Canada, 1986. Pedro Celis, P.A. Larson, and J. I. Munro Robin Hood hashing, Proc. 26th IEEE Symp. on Foundations of Comp. Sci., 1985, 281288.
root
(definition)
Definition:
The distinguished initial or fundamental item of a tree. The only item which has no parent. See the figure at tree.
Author: PEB
rooted tree
(definition)
Definition:
A tree in which one node is designated as the root.
Also known as oriented tree.
Author: PMS
rotation
(definition)
Definition:
To switch children and parents among two or three adjacent nodes to restore balance to a tree.
Note:
A rotation may change the depth of some nodes, but does not change their relative ordering.
Author: PMS
RP
(definition)
Definition:
The class of languages for which membership can be determined in polynomial time by a probabilistic Turing machine with no false acceptances and less than half false rejections. "RP" means "Randomized Polynomial" time.
Formal Definition: For a language, S, there exists a probabilistic Turing machine, M, that accepts or rejects any string in polynomial time. If w ∉ S, M rejects w. If w ∈ S, M accepts w with a probability at least 1/2.
Also known as randomized polynomial time.
Note:
By repeating the run, the chance of incorrect rejection may be arbitrarily reduced. After [Hirv01, page 19].
Author: PEB
R^{+}tree
(data structure)
Definition:
A spatial access method which splits space with hierarchically nested boxes. Objects are indexed in each box which intersects them. The tree is heightbalanced.
Note:
After [GG98].
Author: PEB
R^{*}tree
(data structure)
Definition:
A spatial access method which splits space in hierarchically nested, possibly overlapping, boxes. The tree is heightbalanced. It is similar to the Rtree, but reinserts entries upon overflow, rather than splitting.
Note:
After [GG98].
Author: PEB
Rtree
(data structure)
Definition:
(1) A spatial access method which splits space with hierarchically nested, and possibly overlapping, boxes. The tree is heightbalanced. (2) A recursion tree.
Author: PEB
More information
(1) After [GG98]. Also found in Algorithms and Theory of Computation Handbook, page 1824. (2) Used in [GCG92]. Suggested by Rama Maiti, 19 August 2001.
run time
(definition)
Definition:
(1) The amount of time needed to execute an algorithm. (2) The time when a compiled program is executing, versus compile time.
Author: PR
Published  April 2009
Find free glossaries at TranslationDirectory.com
Find free dictionaries at TranslationDirectory.com
Subscribe to free TranslationDirectory.com newsletter
Need more translation jobs from translation agencies? Click here!
Translation agencies are welcome to register here  Free!
Freelance translators are welcome to register here  Free!
Submit your glossary or dictionary for publishing at TranslationDirectory.com
