{ "id": "epmqk8knmv", "slug": "search-tree-computer-science", "title": "Search tree (computer science)", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.algorithms" }, { "id": "technology.computing.ai.data_structures", "label": "Data structures", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.data_structures" }, { "id": "technology.computing.ai.data_structures.data_structures.trees", "label": "Trees", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.data_structures.data_structures.trees" } ], "geo": [ { "id": "geo.nongeo.t1800.technology.computing", "label": "Non-geographic · 1800 to 1945: Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.technology.computing", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1800", "label": "Non-geographic · 1800 to 1945", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800" }, { "id": "geo.nongeo.t1800.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.technology" }, { "id": "geo.nongeo.t1800.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.technology.computing" } ] }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Non-geographic · 1946 to 2000: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms" } ] } ], "excerpt": "A search tree is a tree data structure in which each node holds a key, and key ordering directs efficient search, insertion, deletion, and range queries.", "snippet": "A search tree is a tree data structure in which each node holds a key, and key ordering directs efficient search, insertion, deletion, and range queries.", "node": "technology.computing.ai.data_structures.data_structures.trees", "markdown": "# Search tree (computer science)\n\nA search tree is a tree-structured data organization in which each node holds a key, and the ordering of keys among nodes directs a systematic search for a target value, its position, or a range of values. The binary search tree was formally introduced by Thomas N. Hibbard in 1962 for a practical reason: the need for a list that could be searched efficiently and also changed efficiently, where inserting or deleting in an ordinary sequence list requires moving on average \\( n/2 \\) items, while a tree-shaped list gives expected search and update time proportional to log n.[1](https://doi.org/10.1145/321105.321108) A search tree keeps keys ordered, so the same structure also supports minimum, maximum, floor, ceiling, rank, and range queries.[2](https://algs4.cs.princeton.edu/32bst/index.php)\n\n| Property | Value |\n|---|---|\n| Ordering invariant | each node's key is larger than all keys in its left subtree and smaller than all keys in its right subtree [2](https://algs4.cs.princeton.edu/32bst/index.php) |\n| Unbalanced BST cost | search, insert, delete, min/max, floor, ceiling, rank, select, and range count all take time proportional to tree height in the worst case [2](https://algs4.cs.princeton.edu/32bst/index.php) |\n| Random-key average | a successful search in a BST built from N random keys takes about 2 ln N, roughly 1.39 lg N, compares [2](https://algs4.cs.princeton.edu/32bst/index.php) |\n| B-tree cost | retrieval, insertion, and deletion in time proportional to \\( \\log_{k} l \\), with storage utilization at least 50% [3](https://liacs.leidenuniv.nl/~stefanovtp/courses/StudentenSeminarium/Papers/DB/OMLO.pdf) |\n| AVL height bound | at most 1.4405 lg(n+2) − 0.3277 [4](https://web.stanford.edu/~blp/papers/libavl.pdf) |\n| Red-black height bound | at most 2 lg(n+1) [4](https://web.stanford.edu/~blp/papers/libavl.pdf) |\n| Splay tree cost | amortized per standard operation [5](https://doi.org/10.1145/3828.3835) |\n\n## How it works\n\nThe search tree property orders keys by position: the key in any node is larger than all keys in its left subtree and smaller than all keys in its right subtree.[2](https://algs4.cs.princeton.edu/32bst/index.php) Search compares the target against the root and follows one branch, so every operation touches a single root-to-node path and costs time proportional to the tree's height.[2](https://algs4.cs.princeton.edu/32bst/index.php)\n\n## How it is done\n\n**Search and insertion.** A search compares the query key with the current node's key and descends left or right until it finds the key or reaches a null link. Insertion of a missing key follows the same path; the null link where the search ends is replaced by a new node.[2](https://algs4.cs.princeton.edu/32bst/index.php)\n\n**Deletion.** A node with at most one child is spliced out directly. A node with two children is replaced by its successor, the node with the smallest key in its right subtree, which necessarily has no left child; this method was first proposed by T. Hibbard in 1962.[2](https://algs4.cs.princeton.edu/32bst/index.php) • [6](https://web.stanford.edu/class/archive/cs/cs161/cs161.1176/Lectures/CS161Lecture07.pdf) A common implementation copies the successor's key into the deleted node's position and then recursively deletes the successor from the right subtree.[7](https://dsa.handbook.academy/curriculum/trees-heaps/binary-search-trees/)\n\n**Rotations.** A rotation restructures the tree locally in \\( O(1) \\) time while preserving the BST property, and is the tool rebalancing schemes apply.[6](https://web.stanford.edu/class/archive/cs/cs161/cs161.1176/Lectures/CS161Lecture07.pdf)\n\n## Origin\n\nHibbard introduced the binary search tree in \"Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting,\" published in the Journal of the ACM in 1962.[1](https://doi.org/10.1145/321105.321108) The first balanced tree with search, insertion, and deletion all optimal in time is the [AVL tree](https://www.edgepedia.org/avl-tree), which requires the height difference between any node's two child subtrees to be at most 1.[8](https://people.apache.org/~shv/docs/amcs04.pdf) Rudolf Bayer described the symmetric binary B-tree, the precursor of red-black trees, in a 1971 Purdue report.[9](https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1457&context=cstech) Splay trees were developed and analyzed by Daniel D. Sleator and [Robert E. Tarjan](https://www.edgepedia.org/robert-e-tarjan) in 1985 in the Journal of the ACM.[5](https://doi.org/10.1145/3828.3835) Knuth's dynamic programming algorithm computes an optimum binary search tree in \\( O(n^{2}) \\) time and was published in Acta Informatica in 1971.[10](https://doi.org/10.1007/bf00264289)\n\n## Variants\n\n**Perfectly balanced multiway nodes.** In a 2-3 tree all null links are the same distance from the root, and search or insert with N keys visits at most lg N nodes.[11](https://algs4.cs.princeton.edu/33balanced/) Red-black BSTs encode 2-3 trees in a binary tree: each 3-node becomes two 2-nodes connected by a single left-leaning red link; height is at most 2 lg N and average path length about 1.00 lg N.[11](https://algs4.cs.princeton.edu/33balanced/)\n\n**Randomization.** A treap keeps keys in BST order and independently drawn random priorities in heap order; find, insert, delete, split, and join run in expected \\( O(\\log n) \\) time.[12](https://ti.inf.ethz.ch/ew/courses/APC22/Chapter_2.pdf) B-trees generalize 2-3-4 trees to branching factors sometimes in the thousands, which suits disks with slow access times.[13](https://www.cs.cmu.edu/afs/cs/academic/class/15210-s14/www/lectures/bst.pdf)\n\n**Self-adjustment.** Splay trees impose no structural constraint; instead, the splaying heuristic rotates the accessed node to the root along the access path, and all standard operations run in amortized logarithmic time.[5](https://doi.org/10.1145/3828.3835) Splay trees are conjectured to be dynamically optimal, and established guarantees include static optimality, the working-set bound, and the dynamic-finger bound.[14](https://erikdemaine.org/papers/BST_SODA2009/paper.pdf) Tango trees achieved an O(lg lg n)-competitive ratio, the first major progress on the 1985 conjecture, by Erik D. Demaine and colleagues in 2007 in the SIAM Journal on [Computing](https://www.edgepedia.org/computing).[15](https://epubs.siam.org/doi/10.1137/S0097539705447347)\n\n**Concurrency.** Fatourou and Ruppert gave a general technique, published in 2024, that augments any lock-free tree with fields computable from a node and its children, enabling lock-free order-statistic, interval, and segment trees; their augmented BST answers order-statistic queries in \\( O(h) \\) steps on a tree of height \\( h \\).[16](https://doi.org/10.4230/lipics.disc.2024.23) For concurrent B-trees, Philip L. Lehman and S. Bing Yao published efficient locking for concurrent operations in ACM Transactions on Database Systems in 1981.[17](https://doi.org/10.1145/319628.319663)\n\n## Applications\n\n**B-trees on disk.** A B-tree of class \\( (k, h) \\) has root-to-leaf paths all of equal height h, and every non-root internal node has between \\( k+1 \\) and \\( 2k+1 \\) children, where \\( k \\) is a device-dependent page parameter.[3](https://liacs.leidenuniv.nl/~stefanovtp/courses/StudentenSeminarium/Papers/DB/OMLO.pdf) Retrieval, insertion, and deletion run in time proportional to \\( \\log_{k} l \\) for an index of size l, with storage utilization at least 50%.[3](https://liacs.leidenuniv.nl/~stefanovtp/courses/StudentenSeminarium/Papers/DB/OMLO.pdf) Insertion splits full pages and propagates splits toward the root; a root split, which creates a new root, is the only way the height increases.[3](https://liacs.leidenuniv.nl/~stefanovtp/courses/StudentenSeminarium/Papers/DB/OMLO.pdf) • [18](https://www.cs.ubc.ca/~liorma/cpsc320/files/B-trees.pdf) Because each node read requires a slow random disk access, databases use high branching factors to minimize I/O overhead, so a root-to-leaf traversal needs few secondary memory accesses.[18](https://www.cs.ubc.ca/~liorma/cpsc320/files/B-trees.pdf) • [19](https://cs.nyu.edu/~shasha/papers/datastructuresbook.pdf)\n\nThe term B+-tree refers to the variant in which all keys reside in leaves and internal nodes hold copies used only to direct searches, and sorted, linked leaves support range queries.[20](https://users.cs.utah.edu/~pandey/courses/cs6530/fall22/papers/trees/p121-comer.pdf) • [19](https://cs.nyu.edu/~shasha/papers/datastructuresbook.pdf)\n\n## Limitations and alternatives\n\n**Degeneration.** Inserting keys in sorted order produces an extremely unbalanced tree and \\( O(n^{2}) \\) total build time, with search cost growing to \\( n \\) [21](https://chalmersgu-data-structure-courses.github.io/dsabook/html/section-10.1.html); in the worst case a BST's height is \\( O(n) \\), for example a long rightward path.[6](https://web.stanford.edu/class/archive/cs/cs161/cs161.1176/Lectures/CS161Lecture07.pdf) Almost no one uses plain BSTs because no worst-case guarantee holds, and standard libraries ship red-black trees instead: Java's TreeMap, .NET's SortedDictionary, and C++'s std::map, which common implementations build as a red-black tree even though the C++ standard does not mandate that structure.[7](https://dsa.handbook.academy/curriculum/trees-heaps/binary-search-trees/) Hibbard deletion drifts: always taking the right-subtree successor biases the tree leftward over many mixed insert and delete cycles, with average path length drifting from about 1.39 lg N toward \\( \\sqrt{N} \\).[7](https://dsa.handbook.academy/curriculum/trees-heaps/binary-search-trees/)\n\n**Hash tables.** A hash index with few collisions reads one data block for a point query, but it does not support range queries as efficiently as a sorted tree index.[19](https://cs.nyu.edu/~shasha/papers/datastructuresbook.pdf)\n\n**Skip lists and tries.** Skip lists use randomized coin-toss insertion to give \\( O(\\log n) \\) expected search, insertion, and deletion [22](https://users.cs.utah.edu/~pandey/courses/cs6530/fall22/slides/Lecture03.pdf); tries examine key prefixes one at a time, need no rebalancing, and run in \\( O(k) \\) for a key of length \\( k \\), with 256-way [radix trees](https://www.edgepedia.org/radix-tree) such as the Adaptive Radix Tree built for in-memory database systems.[22](https://users.cs.utah.edu/~pandey/courses/cs6530/fall22/slides/Lecture03.pdf)\n\n**Learned indexes.** A B-tree index can be seen as a model mapping a key to a position in a sorted array, and existing index structures can be replaced with other types of models, including deep-learning models, termed learned indexes.[23](https://dl.acm.org/doi/10.1145/3183713.3196909)\n\n## References\n\n1. [Thomas N. Hibbard (1962). Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting. Journal of the ACM.](https://doi.org/10.1145/321105.321108)\n2. [Binary Search Trees (Sedgewick & Wayne, Algorithms 4th ed.)](https://algs4.cs.princeton.edu/32bst/index.php)\n3. [Organization and Maintenance of Large Ordered Indices (Bayer & McCreight)](https://liacs.leidenuniv.nl/~stefanovtp/courses/StudentenSeminarium/Papers/DB/OMLO.pdf)\n4. [Performance of BST data structures in system software (Stanford libavl study)](https://web.stanford.edu/~blp/papers/libavl.pdf)\n5. [Daniel Dominic Sleator, Robert Endre Tarjan (1985). Self-adjusting binary search trees. Journal of the ACM.](https://doi.org/10.1145/3828.3835)\n6. [Stanford CS161 Lecture 7: BSTs and Red-Black Trees](https://web.stanford.edu/class/archive/cs/cs161/cs161.1176/Lectures/CS161Lecture07.pdf)\n7. [Binary search trees, The DSA Handbook](https://dsa.handbook.academy/curriculum/trees-heaps/binary-search-trees/)\n8. [S(b)-trees: external dynamic dictionaries with variable length keys](https://people.apache.org/~shv/docs/amcs04.pdf)\n9. [Symmetric Binary B-Trees (Bayer, 1972)](https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1457&context=cstech)\n10. [D. E. Knuth (1971). Optimum binary search trees. Acta Informatica.](https://doi.org/10.1007/bf00264289)\n11. [Balanced Search Trees (Sedgewick & Wayne, Algorithms 4th ed.)](https://algs4.cs.princeton.edu/33balanced/)\n12. [Random(ized) Search Trees (ETH Zürich course chapter)](https://ti.inf.ethz.ch/ew/courses/APC22/Chapter_2.pdf)\n13. [CMU 15-210 Lecture: Binary Search Trees](https://www.cs.cmu.edu/afs/cs/academic/class/15210-s14/www/lectures/bst.pdf)\n14. [The Geometry of Binary Search Trees (Demaine et al., SODA 2009)](https://erikdemaine.org/papers/BST_SODA2009/paper.pdf)\n15. [Dynamic Optimality, Almost (Demaine, Harmon, Iacono, Pătraşcu, Tango trees, SICOMP)](https://epubs.siam.org/doi/10.1137/S0097539705447347)\n16. [Fatourou, Panagiota, Ruppert, Eric (2024). Lock-Free Augmented Trees. DISC 2024, Leibniz International Proceedings in Informatics (LIPIcs).](https://doi.org/10.4230/lipics.disc.2024.23)\n17. [Philip L. Lehman, s. Bing Yao (1981). Efficient locking for concurrent operations on B-trees. ACM Transactions on Database Systems.](https://doi.org/10.1145/319628.319663)\n18. [B-Trees (UBC CPSC 320 notes, CLRS-based)](https://www.cs.ubc.ca/~liorma/cpsc320/files/B-trees.pdf)\n19. [Data Structures for Data-Intensive Applications (Shasha et al.)](https://cs.nyu.edu/~shasha/papers/datastructuresbook.pdf)\n20. [The Ubiquitous B-Tree (Comer, Computing Surveys, 1979)](https://users.cs.utah.edu/~pandey/courses/cs6530/fall22/papers/trees/p121-comer.pdf)\n21. [DSABook – Binary search trees](https://chalmersgu-data-structure-courses.github.io/dsabook/html/section-10.1.html)\n22. [Utah CS6530 Lecture 3: In-memory indexing (Trees, Tries, Skip Lists)](https://users.cs.utah.edu/~pandey/courses/cs6530/fall22/slides/Lecture03.pdf)\n23. [The Case for Learned Index Structures (Kraska et al., SIGMOD 2018)](https://dl.acm.org/doi/10.1145/3183713.3196909)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Data structures › Trees*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://web.stanford.edu/~blp/papers/libavl.pdf", "https://cs.nyu.edu/~shasha/papers/datastructuresbook.pdf", "https://users.cs.utah.edu/~pandey/courses/cs6530/fall22/papers/trees/p121-comer.pdf", "https://users.cs.utah.edu/~pandey/courses/cs6530/fall22/slides/Lecture03.pdf" ], "url": "https://www.edgepedia.org/search-tree-computer-science", "markdown_url": "https://www.edgepedia.org/search-tree-computer-science.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Search tree (computer science)\", Edgepedia (EdgeChat), https://www.edgepedia.org/search-tree-computer-science. Edgepedia Community License 1.0.", "credit_md": "\"[Search tree (computer science)](https://www.edgepedia.org/search-tree-computer-science)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/search-tree-computer-science](https://www.edgepedia.org/search-tree-computer-science). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Search tree (computer science)\", Edgepedia (EdgeChat), https://www.edgepedia.org/search-tree-computer-science. Edgepedia Community License 1.0.", "speakable": "A search tree is a tree data structure in which each node holds a key, and key ordering directs efficient search, insertion, deletion, and range queries." }