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
$12 per month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
R
- Rabin-Karp: see Karp-Rabin
- 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
- Randomized-Select
- 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
- red-black 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
- R-file
- Rice's method
- right rotation
- right-threaded 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
- R-tree
- 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 in-place 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 89-94.)
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 5-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 10-17 and 15-21, 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: CRC-A
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):288-323, March 1998. Jean Vuillemin, A Unifying Look at Data Structures, CACM, 23(4):229-239, 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 26-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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):464-497 (1996).
Also in 30th Annual Symposium on Foundations of Computer Science, pages 540-545, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
random number generator
(algorithm)
Definition:
See pseudo-random number generator.
Also known as RNG.
Note: Any computer program is likely to generate
pseudo-random 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 47-40, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 639-640, 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 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
rapid sort
(algorithm)
Definition:
A 2-pass 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 minimum-length 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(n-1) + F(n-2), 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 1-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 non-negative integer.
- Write a function to compute any number to the power of a non-negative 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(n-m, 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 non-negative integer using repeated squaring, that is, x2n = (xn)² and x2n+1 = x × x2n. (after "ML for the Working Programmer", pages 45 and 46).
- Write a function to compute the integer square root of a non-negative 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 trade-off 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 "R-tree".
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 24-19 and 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
red-black tree
(data structure)
Definition:
A nearly-balanced 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 red-black tree with n internal nodes has height at most 2log2(n+1).
Also known as symmetric binary B-tree.
Generalization (I am a kind of ...)
B-tree.
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 B-trees" 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 red-black tree.
Author: PEB
More information
Rudolf Bayer, Symmetric Binary B-Trees: Data Structures and Maintenance Algorithms, Acta Informatica, 1:290-306, 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 8-21. 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 32-39, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
reduction
(definition)
Definition:
A computable transformation of one problem into another.
Note:
From Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 18-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 object-oriented 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 29-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 32-39 and 34-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 well-defined 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 nth 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 x13 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 | | | x1 | 1 | | | | Least significant bit of exponent is 1, so multiply a = a * s | | x1 | x1 | | | | Square s | | x² | x1 | | | | Next bit is 0, so don't multiply | | x² | x1 | | | | Square s | | x4 | x1 | | | | Next bit is 1, so multiply | | x4 | x5 | | | | Square s | | x8 | x5 | | | | Highest bit is 1, so multiply | | x8 | x13 | | Why does this work? Consider the exponent decomposed into binary notation. x13 = x1101
= x(1*2^3 + 1*2^2 + 0*2^1 + 1*2^0)
= x1*2^3* x1*2^2* x0*2^1* x1*2^0
= x2^3 * x2^2 * 1 * x2^0
= x8 * x4 * x1
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 an 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 (element-wise) λ 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 34-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 in-memory 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):37-57, March 1985.
Available on-line, 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 3-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
R-file
(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 14-35, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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
right-threaded 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 CS-86-14, 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, 281-288.
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 height-balanced.
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 height-balanced. It is similar to the R-tree, but reinserts entries upon overflow, rather than splitting.
Note:
After [GG98].
Author: PEB
R-tree
(data structure)
Definition:
(1) A spatial access method which splits space with hierarchically nested, and possibly overlapping, boxes. The tree is height-balanced. (2) A recursion tree.
Author: PEB
More information
(1) After [GG98]. Also found in Algorithms and Theory of Computation Handbook, page 18-24. (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
|
