P.F. Windley, A.D. Booth, A.J.T. Colin, and T.N. Hibbard
Time complexity in big O notation
Operation
Average
Worst case
Search
O(log n)
O(n)
Insert
O(log n)
O(n)
Delete
O(log n)
O(n)
Space complexity
Space
O(n)
O(n)
Fig. 1: A binary search tree of size 9 and depth 3, with 8 at the root. The leaves are not drawn.
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. The time complexity of operations on the binary search tree is linear with respect to the height of the tree.
Binary search trees allow binary search for fast lookup, addition, and removal of data items. Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm. BSTs were devised in the 1960s for the problem of efficient storage of labeled data and are attributed to Conway Berners-Lee and David Wheeler.
The performance of a binary search tree is dependent on the order of insertion of the nodes into the tree since arbitrary insertions may lead to degeneracy; several variations of the binary search tree can be built with guaranteed worst-case performance. The basic operations include: search, traversal, insert and delete. BSTs with guaranteed worst-case complexities perform better than an unsorted array, which would require linear search time.
The complexity analysis of BST shows that, on average, the insert, delete and search takes for nodes. In the worst case, they degrade to that of a singly linked list: . To address the boundless increase of the tree height with arbitrary insertions and deletions, self-balancing variants of BSTs are introduced to bound the worst lookup complexity to that of the binary logarithm. AVL trees were the first self-balancing binary search trees, invented in 1962 by Georgy Adelson-Velsky and Evgenii Landis.
Binary search trees can be used to implement abstract data types such as dynamic sets, lookup tables and priority queues, and used in sorting algorithms such as tree sort.
and 24 Related for: Binary search tree information
In computer science, binarysearch, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position...
In computer science, a binarytree is a tree data structure in which each node has at most two children, referred to as the left child and the right child...
splay tree is a binarysearchtree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search...
application stores the entire key–value pair at that particular location. A BinarySearchTree is a node-based data structure where each node contains a key and...
binarysearchtree are two closely related forms of binarysearchtree data structures that maintain a dynamic set of ordered keys and allow binary searches...
depth-first search (DFS), the searchtree is deepened as much as possible before going to the next sibling. To traverse binarytrees with depth-first search, perform...
for these trees. Random binarytrees have been used for analyzing the average-case complexity of data structures based on binarysearchtrees. For this...
approach to the dynamic optimality problem on online algorithms for binarysearchtrees involves reformulating the problem geometrically, in terms of augmenting...
computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binarysearchtree. In an AVL tree, the heights of the...
A tree sort is a sort algorithm that builds a binarysearchtree from the elements to be sorted, and then traverses the tree (in-order) so that the elements...
the intervals do not overlap and they can be inserted into a simple binarysearchtree and queried in O ( log n ) {\displaystyle O(\log n)} time. However...
computing, a threaded binarytree is a binarytree variant that facilitates traversal in a particular order. An entire binarysearchtree can be easily traversed...
hash tables and searchtrees. It is sometimes also possible to solve the problem using directly addressed arrays, binarysearchtrees, or other more specialized...
between nodes, which represent each character in the key. Unlike a binarysearchtree, nodes in the trie do not store their associated key. Instead, a node's...
In computer science, a scapegoat tree is a self-balancing binarysearchtree, invented by Arne Andersson in 1989 and again by Igal Galperin and Ronald...
representation of objects within the space in the form of a tree data structure known as a BSP tree. Binary space partitioning was developed in the context of...
mathematics, tree rotation is an operation on a binarytree that changes the structure without interfering with the order of the elements. A tree rotation...
used in the definition of the treap and randomized binarysearchtree data structures for binarysearch problems, in comparison sort algorithms that perform...
level-order sequence of the corresponding balanced binarysearchtree. This places the first pivot of a binarysearch as the first element in the array. The second...
a WAVL tree or weak AVL tree is a self-balancing binarysearchtree. WAVL trees are named after AVL trees, another type of balanced searchtree, and are...
algorithms Searching in balanced binarysearchtrees Exponentiation by squaring Longest increasing subsequence Binary logarithms also occur in the exponents...
Global Information
