blanketglossary

Binary search tree

Definition

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.

Related concepts

(a,b)-tree 2–3 tree 2–3–4 tree AA tree AVL tree AVL trees Abstract data structures Abstract data type Addison-Wesley Algorithmica Andrew Colin Andrew Donald Booth Array (data structure)Association list Associative array B*-tree B+ tree B-tree BK-tree BSP tree Ball tree Best, worst and average case Big O notation Binary decision diagram Binary heap Binary logarithm Binary search Binary search algorithm Binary tree Binomial heap Bit array Brodal queue Bx-tree C-trie Cambridge University Press Cartesian tree Charles E. Leiserson Circular buffer Clifford Stein Collection (abstract data type)Computational complexity theory Computer performance Computer science Container (abstract data type)Conway Berners-Lee Copyright status of works by the federal government of the United States Cornell University Cornell University College of Engineering Cover tree Ctrie D-ary heap Dancing tree Daniel Sleator Data structure David Wheeler (computer scientist)Deterministic acyclic finite state automaton Dictionary of Algorithms and Data Structures Directed acyclic graph Disjoint-set data structure Donald Knuth Double-ended priority queue Double-ended queue Douglas Comer Dynamic array Evgenii Landis Exponential tree Fenwick tree Fibonacci heap Finger tree Fractal tree index Fusion tree Geometry of binary search trees Georgy Adelson-Velsky Graph (abstract data type)HTree Hash calendar Hash table Hash tree (persistent data structure)Hashed array tree Heap (data structure)Height-balanced tree Helper function Hilbert R-tree IDistance Implicit k-d tree Inorder traversal Interval tree Introduction to Algorithms Iteration Join-based tree algorithms Journal of the ACM K-D-B-tree K-ary tree K-d tree Labeled data Leaf node Leaf nodes Left-child right-sibling binary tree Left-leaning red–black tree Leftist tree Linear time Link/cut tree Linked data structure Linked list List (abstract data type)List of data structures Log-structured merge-tree Lookup table Loyola Marymount University M-tree MIT Press MVP tree Magnetic tape Merkle tree Metric tree Microsoft PowerPoint Multimap National Institute of Standards and Technology Null pointer Octree Optimal binary search tree Order statistic tree Oxford College of Emory University Oxford University Press PH-tree PQ tree Pairing heap Palindrome tree Post-order traversal Pre-order traversal Princeton University School of Engineering and Applied Science Priority R-tree Priority queue Proceedings of the USSR Academy of Sciences Pseudocode Quadtree Queue (abstract data type)Quicksort R* tree R+ tree R-tree Radix tree Range tree Recursion (computer science)Red-black tree Red–black tree Retrieval Data Structure Robert Tarjan Ronald L. Rivest Root node Rooted tree Rope (data structure)SPQR tree SUNY Oneonta Scapegoat tree Search algorithm Search tree Segment tree Self-balancing binary search tree Set (abstract data type)Set (computer science)Singly linked list Skew binomial heap Skew heap Skip list Sorting algorithm Space complexity Sparse matrix Spatial index Splay tree Springer Publishing Stack (abstract data type)Stanford University Suffix tree Symposium on Foundations of Computer Science T-tree Ternary search tree The Art of Computer Programming The Computer Journal Thomas H. Cormen Thomas N. Hibbard Threaded binary tree Time complexity Top tree Total order Treap Tree (abstract data type)Tree (data structure)Tree sort Tree traversal Trie UB-tree University of California, Irvine University of Maryland University of Texas at Arlington University of Toronto University of Waterloo Unrolled linked list Van Emde Boas tree Vantage-point tree Weak heap Weight-balanced tree While loop X-fast trie X-tree XOR linked list Y-fast trie

9 concepts already in your glossary