Randomized binary search tree
- Randomized binary search tree
A randomized binary search tree (abbreviated RBST, also known as Cartesian tree) is a type of binary search tree, with data nodes organizedas in a normal binary search tree. Each node has also an access priority, namely p(n) which is chosen in a random fashion according to subtree size, every time a new node is inserted. [ Citation | title=Randomized binary search trees | journal=Journal of the ACM | volume=45 | issue=2 | year=1998 | first1=Conrado | last1=Martinez | first2=Salvador | last2=Roura | pages=pp. 288-323 | publisher=ACM Press | url=http://citeseer.ist.psu.edu/article/martinez97randomized.html] These priorities are organized in a max heap order.]The expected value of the tree's height is logarithmic in its number of nodes, which ensures good asymptotic running time.
Operations on RBST
Insertions
When a new node is inserted in an RBST of size , it must be the root of the new tree with probability , and with complementary probability it must be inserted into the appropriate subtree of the root. Inserting at the root requires the "split" operation, which splits an RBST into two trees. The new root node links up these two subtrees as its left child and right child.
Deletions
When the RBST node to be deleted is found, its left child and its right child are joined together to form a new RBST. The no longer referenced node is deleted.
RBST versus treaps
A RBST node has a random priority of the range from 0 to the subtree size, while a treap [ Citation | title=Randomized Search Trees | first1=Raimund | last1=Seidel | first2=Cecilia R. | last2=Aragon | journal=Algorithmica | volume=16 | issue=4/5 | pages=pp. 464-497 | year=1996 | url=http://citeseer.ist.psu.edu/seidel96randomized.html ] node has a random priority of the machine's word size. RBST supports searches and deletions by rank.
References
ee also
* Treap
External links
* [http://nist.gov/dads/HTML/randomizedBinarySearchTree.html Definition from NIST]
Wikimedia Foundation.
2010.
Look at other dictionaries:
Binary search tree — In computer science, a binary search tree (BST) is a binary tree data structurewhich has the following properties: *each node (item in the tree) has a value; *a total order (linear order) is defined on these values; *the left subtree of a node… … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
Treap — In computer science, a treap is a binary search tree that orders the nodes by adding a random priority attribute to a node, as well as a key. Citation | title=Introduction to Algorithms, Second Edition publisher=MIT Press and McGraw Hill |… … Wikipedia
Adaptive heap sort — The adaptive heap sort is a sorting algorithm that is similar to heap sort, but uses a randomized binary search tree to structure the input according to any preexisting order. The randomized binary search tree is used to select candidates that… … Wikipedia
RBST — or rBST may refer to:* Randomized binary search tree, a computer data structure * Rare Breeds Survival Trust, a UK charity * Recombinant bovine somatotropin (usually rBST ), a synthetic growth hormone that is injected into a cow to increase its… … Wikipedia
Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… … Wikipedia
Skip list — Invented in 1990 by William Pugh, a skip list is a probabilistic data structure, based on multiple parallel, sorted linked lists, with efficiency comparable to a binary search tree (order log n average time for most operations).Underlying the… … Wikipedia
Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… … Wikipedia
