Binary Search Tree

In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.
  • There must be no duplicate nodes.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.

Read more about Binary Search TreeOperations, Types

Other articles related to "binary search tree, search tree, search, tree, binary, search trees":

Types - Optimal Binary Search Trees
... If we do not plan on modifying a search tree, and we know exactly how often each item will be accessed, we can construct an optimal binary search tree, which is a search tree where the average ... Even if we only have estimates of the search costs, such a system can considerably speed up lookups on average ... English words used in a spell checker, you might balance the tree based on word frequency in text corpora, placing words like the near the root and words like agerasia near the leaves ...
Cartesian Tree - Treaps
... Main article Treap Because a Cartesian tree is a binary tree, it is natural to use it as a binary search tree for an ordered sequence of values ... However, defining a Cartesian tree based on the same values that form the search keys of a binary search tree does not work well the Cartesian tree of a sorted sequence is just a path, rooted ... However, it is possible to generate more-balanced search trees by generating priority values for each search key that are different than the key itself, sorting the ...
Michael Wood (historian)
... including Great Railway Journeys (1980), Art of the Western World, Legacy A Search for the Origins of Civilization, In the Footsteps of Alexander the Great, Conquistadors, In Search of Myths and Heroes ... has also written a number of books on English history including In Search of the Dark Ages, The Domesday Quest, The Story of England and In Search of Shakespeare ...
Tango Tree
... A Tango tree is a type of binary search tree proposed by Erik D ... It is an online binary search tree that achieves an competitive ratio relative to the optimal offline binary search tree, while only using additional bits of memory per node ...
Random Binary Tree - Binary Trees From Random Permutations - Treaps and Randomized Binary Search Trees
... In applications of binary search tree data structures, it is rare for the values in the tree to be inserted without deletion in a random order, limiting the direct applications of random binary ... that allow insertions and deletions to be performed in a binary search tree, at each step maintaining as an invariant the property that the shape of ... unrelated to their values), these priorities may be used to construct a Cartesian tree for the numbers, a binary tree that has as its inorder traversal ...

Famous quotes containing the words tree and/or search:

    The Anglo-American can indeed cut down, and grub up all this waving forest, and make a stump speech, and vote for Buchanan on its ruins, but he cannot converse with the spirit of the tree he fells, he cannot read the poetry and mythology which retire as he advances. He ignorantly erases mythological tablets in order to print his handbills and town-meeting warrants on them.
    Henry David Thoreau (1817–1862)

    At the root of all these noble races, the beast of prey, the splendid blond beast prowling greedily in search of spoils and victory, cannot be mistaken.
    Friedrich Nietzsche (1844–1900)