A node-based tree data structure in which each node's left subtree holds only lesser values and its right subtree only greater ones, giving search, insertion and deletion roughly proportional to the tree's height. The structure was discovered independently by several researchers around 1960, including P.F. Windley, Andrew Donald Booth, Andrew Colin and Thomas N. Hibbard; it is formally attributed to Conway Berners-Lee and David Wheeler, who used it for storing labeled data on magnetic tape in 1960, while Hibbard's own variant became especially influential in practice. A genuine case of simultaneous discovery rather than a single inventor, and a different entity from this atlas's existing Binary Search algorithm despite the shared name. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Disputed
Origin YearSeveral researchers (Windley, Booth, Colin, Hibbard) described the structure independently around 1960; formal attribution to Berners-Lee and Wheeler names one specific 1960 application (magnetic tape storage) rather than settling a single inventor for the underlying idea. Core PrincipleEvery node orders its two subtrees, lesser values left and greater values right, so a search can discard half the remaining tree at each step, the same principle behind binary search on a sorted array. 1 FAQs
Why can a binary search tree become slow, and what fixes it?
Its speed depends on insertion order, and balanced variants guarantee worst-case performance.
A binary search tree is only as fast as its shape, and its shape depends on the order in which items are inserted. Arbitrary insertions can lead to degeneracy, where the tree loses the balance that makes lookups quick. Several variations of the binary search tree exist that are built to give guaranteed worst-case performance.
Connections
Associated With
In Field
Source Wikipedia: Binary search tree
Sources
1. Wikipedia: Binary search tree
Wikimedia FoundationHistory section
discovered independently by several researchers
Lead section
The time complexity of operations on the binary search tree is linear with respect to the height of the tree.
In Group: Tree Data Structures, Lead
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.