Editing Binary search (section)

=== Trees ===
[[File:Binary search tree search 4.svg|thumb|right|[[Binary search tree]]s are searched using an algorithm similar to binary search.]]

A [[binary search tree]] is a [[binary tree]] data structure that works based on the principle of binary search. The records of the tree are arranged in sorted order, and each record in the tree can be searched using an algorithm similar to binary search, taking on average logarithmic time. Insertion and deletion also require on average logarithmic time in binary search trees. This can be faster than the linear time insertion and deletion of sorted arrays, and binary trees retain the ability to perform all the operations possible on a sorted array, including range and approximate queries.<ref name="pred" />{{Sfn|Sedgewick|Wayne|2011|loc=§3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion"}}

However, binary search is usually more efficient for searching as binary search trees will most likely be imperfectly balanced, resulting in slightly worse performance than binary search. This even applies to [[self-balancing binary search tree|balanced binary search tree]]s, binary search trees that balance their own nodes, because they rarely produce the tree with the fewest possible levels. Except for balanced binary search trees, the tree may be severely imbalanced with few internal nodes with two children, resulting in the average and worst-case search time approaching <math display="inline">n</math> comparisons.{{Efn|Inserting the values in sorted order or in an alternating lowest-highest key pattern will result in a binary search tree that maximizes the average and worst-case search time.{{Sfn|Knuth|1998|loc=§6.2.2 ("Binary tree searching"), subsection "But what about the worst case?"}}}} Binary search trees take more space than sorted arrays.{{Sfn|Sedgewick|Wayne|2011|loc=§3.5 ("Applications"), "Which symbol-table implementation should I use?"}}

Binary search trees lend themselves to fast searching in external memory stored in hard disks, as binary search trees can be efficiently structured in filesystems. The [[B-tree]] generalizes this method of tree organization. B-trees are frequently used to organize long-term storage such as [[database]]s and [[filesystem]]s.{{Sfn|Knuth|1998|loc=§5.4.9 ("Disks and Drums")}}{{Sfn|Knuth|1998|loc=§6.2.4 ("Multiway trees")}}