Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Binary search tree

This is a good article. Click here for more information.
From Wikipedia, the free encyclopedia

Rooted binary tree data structure
Binary search tree
Typetree
Invented1960
Invented byP.F. Windley,A.D. Booth,A.J.T. Colin, andT.N. Hibbard
Time complexity inbig O notation
OperationAverageWorst case
SearchΘ(logn)O(n)
InsertΘ(logn)O(n)
DeleteΘ(logn)O(n)
Space complexity
SpaceΘ(n)O(n)
Fig. 1: A binary search tree of size 9 and depth 3, with 8 at the root.

Incomputer science, abinary search tree (BST), also called anordered orsorted binary tree, is arootedbinary treedata 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. Thetime complexity of operations on the binary search tree islinear with respect to the height of the tree.

Binary search trees allowbinary 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 ofbinary logarithm. BSTs were devised in the 1960s for the problem of efficient storage of labeled data and are attributed toConway Berners-Lee andDavid 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 requirelinear search time.

Thecomplexity analysis of BST shows that,on average, the insert, delete and search takesθ(log⁡n){\displaystyle \theta (\log n)} forn{\displaystyle n} nodes. In the worst case, they degrade to that of a singly linked list:O(n){\displaystyle O(n)}. 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 byGeorgy Adelson-Velsky andEvgenii Landis.[1][2][3]

Binary search trees can be used to implementabstract data types such asdynamic sets,lookup tables andpriority queues, and used insorting algorithms such astree sort.

History

[edit]

The binary search tree algorithm was discovered independently by several researchers, including P.F. Windley,Andrew Donald Booth,Andrew Colin,Thomas N. Hibbard.[4][5] The algorithm is attributed toConway Berners-Lee andDavid Wheeler, who used it for storinglabeled data inmagnetic tapes in 1960.[6] One of the earliest and popular binary search tree algorithm is that of Hibbard.[4]

The time complexity of a binary search tree increases boundlessly with the tree height if the nodes are inserted in an arbitrary order, thereforeself-balancing binary search trees were introduced to bound the height of the tree toO(log⁡n){\displaystyle O(\log n)}.[7] Variousheight-balanced binary search trees were introduced to confine the tree height, such asAVL trees,Treaps, andred–black trees.[8]

Overview

[edit]

A binary search tree is a rooted binary tree in which nodes are arranged instrict total order in which the nodes with keys greater than any particular nodeA is stored on the rightsub-trees to that nodeA and the nodes with keys equal to or less thanA are stored on the left sub-trees toA, satisfying thebinary search property.[9]: 298 [10]: 287 

Binary search trees are also efficacious insortings andsearch algorithms. However, the search complexity of a BST depends upon the order in which the nodes are inserted and deleted; since in worst case, successive operations in the binary search tree may lead to degeneracy and form asingly linked list (or "unbalanced tree") like structure, thus has the same worst-case complexity as alinked list.[11][9]: 299-302 

Binary search trees are also a fundamental data structure used in construction ofabstract data structures such as sets,multisets, andassociative arrays.

Operations

[edit]

Searching

[edit]

Searching in a binary search tree for a specific key can be programmedrecursively oriteratively.

Searching begins by examining theroot node. If the tree isnil, the key being searched for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and the node is returned. If the key is less than that of the root, the search proceeds by examining the left subtree. Similarly, if the key is greater than that of the root, the search proceeds by examining the right subtree. This process is repeated until the key is found or the remaining subtree isnil{\displaystyle {\text{nil}}}. If the searched key is not found after anil{\displaystyle {\text{nil}}} subtree is reached, then the key is not present in the tree.[10]: 290–291 

Recursive search

[edit]

The followingpseudocode implements the BST search procedure throughrecursion.[10]: 290 

Recursive-Tree-Search(x, key)if x = NILor key = x.keythenreturn xif key < x.keythenreturn Recursive-Tree-Search(x.left, key)elsereturn Recursive-Tree-Search(x.right, key)end if

The recursive procedure continues until anil{\displaystyle {\text{nil}}} or thekey{\displaystyle {\text{key}}} being searched for are encountered.

Iterative search

[edit]

The recursive version of the search can be "unrolled" into awhile loop. On most machines, the iterative version is found to be moreefficient.[10]: 291 

Iterative-Tree-Search(x, key)while x ≠ NILand key ≠ x.keydoif key < x.keythen            x := x.leftelse            x := x.rightend ifrepeatreturn x

Since the search may proceed till someleaf node, the running time complexity of BST search isO(h){\displaystyle O(h)} whereh{\displaystyle h} is theheight of the tree. However, the worst case for BST search isO(n){\displaystyle O(n)} wheren{\displaystyle n} is the total number of nodes in the BST, because an unbalanced BST may degenerate to a linked list. However, if the BST isheight-balanced the height isO(log⁡n){\displaystyle O(\log n)}.[10]: 290 

Successor and predecessor

[edit]

For certain operations, given a nodex{\displaystyle {\text{x}}}, finding the successor or predecessor ofx{\displaystyle {\text{x}}} is crucial. Assuming all the keys of a BST are distinct, the successor of a nodex{\displaystyle {\text{x}}} in a BST is the node with the smallest key greater thanx{\displaystyle {\text{x}}}'s key. On the other hand, the predecessor of a nodex{\displaystyle {\text{x}}} in a BST is the node with the largest key smaller thanx{\displaystyle {\text{x}}}'s key. The following pseudocode finds the successor and predecessor of a nodex{\displaystyle {\text{x}}} in a BST.[12][13][10]: 292–293 

 BST-Successor(x)if x.right ≠ NILthenreturn BST-Minimum(x.right)end if     y := x.parentwhile y ≠ NILand x = y.rightdo         x := y         y := y.parentrepeatreturn y
 BST-Predecessor(x)if x.left ≠ NILthenreturn BST-Maximum(x.left)end if     y := x.parentwhile y ≠ NILand x = y.leftdo         x := y         y := y.parentrepeatreturn y

Operations such as finding a node in a BST whose key is the maximum or minimum are critical in certain operations, such as determining the successor and predecessor of nodes. Following is the pseudocode for the operations.[10]: 291–292 

 BST-Maximum(x)while x.right ≠ NILdo         x := x.rightrepeatreturn x
 BST-Minimum(x)while x.left ≠ NILdo         x := x.leftrepeatreturn x

Insertion

[edit]

Operations such as insertion and deletion cause the BST representation to change dynamically. The data structure must be modified in such a way that the properties of BST continue to hold. New nodes are inserted asleaf nodes in the BST.[10]: 294–295  Following is an iterative implementation of the insertion operation.[10]: 294 

1    BST-Insert(T, z)2      y := NIL3      x := T.root4while x ≠ NILdo5        y := x6if z.key < x.keythen7          x := x.left8else9          x := x.right10end if11repeat12     z.parent := y13if y = NILthen14       T.root := z15else if z.key < y.keythen16       y.left := z17else18       y.right := z19end if

The procedure maintains a "trailing pointer"y{\displaystyle {\text{y}}} as a parent ofx{\displaystyle {\text{x}}}. After initialization on line 2, thewhile loop along lines 4-11 causes the pointers to be updated. Ify{\displaystyle {\text{y}}} isnil{\displaystyle {\text{nil}}}, the BST is empty, thusz{\displaystyle {\text{z}}} is inserted as the root node of the binary search treeT{\displaystyle {\text{T}}}, if it is notnil{\displaystyle {\text{nil}}}, insertion proceeds by comparing the keys to that ofy{\displaystyle {\text{y}}} on the lines 15-19 and the node is inserted accordingly.[10]: 295 

Deletion

[edit]
Binary search tree node deletion process.

The deletion of a node, sayZ{\displaystyle {\text{Z}}}, from the binary search treeBST{\displaystyle {\text{BST}}} has three cases:[10]: 295-297 

  1. IfZ{\displaystyle {\text{Z}}} is a leaf node, it is replaced byNIL{\displaystyle {\text{NIL}}} as shown in (a).
  2. IfZ{\displaystyle {\text{Z}}} has only one child, the child node ofZ{\displaystyle {\text{Z}}} gets elevated by modifying the parent node ofZ{\displaystyle {\text{Z}}} to point to the child node, consequently takingZ{\displaystyle {\text{Z}}}'s position in the tree, as shown in (b) and (c).
  3. IfZ{\displaystyle {\text{Z}}} has both left and right children, thein-order successor ofZ{\displaystyle {\text{Z}}}, sayY{\displaystyle {\text{Y}}}, displacesZ{\displaystyle {\text{Z}}} by following the two cases:
    1. IfY{\displaystyle {\text{Y}}} isZ{\displaystyle {\text{Z}}}'s right child, as shown in (d),Y{\displaystyle {\text{Y}}} displacesZ{\displaystyle {\text{Z}}} andY{\displaystyle {\text{Y}}}'s right child remain unchanged.
    2. IfY{\displaystyle {\text{Y}}} lies withinZ{\displaystyle {\text{Z}}}'s right subtree but is notZ{\displaystyle {\text{Z}}}'s right child, as shown in (e),Y{\displaystyle {\text{Y}}} first gets replaced by its own right child, and then it displacesZ{\displaystyle {\text{Z}}}'s position in the tree.
  4. Alternatively, the in-order predecessor can also be used.

The following pseudocode implements the deletion operation in a binary search tree.[10]: 296-298 

1    BST-Delete(BST, z)2if z.left = NILthen3        Shift-Nodes(BST, z, z.right)4else if z.right = NILthen5        Shift-Nodes(BST, z, z.left)6else7        y := BST-Successor(z)8if y.parent ≠ zthen9          Shift-Nodes(BST, y, y.right)10         y.right := z.right11         y.right.parent := y12end if13       Shift-Nodes(BST, z, y)14       y.left := z.left15       y.left.parent := y16end if
1    Shift-Nodes(BST, u, v)2if u.parent = NILthen3        BST.root := v4else if u = u.parent.leftthen5        u.parent.left := v5else6        u.parent.right := v7end if8if v ≠ NILthen9        v.parent := u.parent10end if

TheBST-Delete{\displaystyle {\text{BST-Delete}}} procedure deals with the 3 special cases mentioned above. Lines 2-3 deal with case 1; lines 4-5 deal with case 2 and lines 6-16 for case 3. Thehelper functionShift-Nodes{\displaystyle {\text{Shift-Nodes}}} is used within the deletion algorithm for the purpose of replacing the nodeu{\displaystyle {\text{u}}} withv{\displaystyle {\text{v}}} in the binary search treeBST{\displaystyle {\text{BST}}}.[10]: 298  This procedure handles the deletion (and substitution) ofu{\displaystyle {\text{u}}} fromBST{\displaystyle {\text{BST}}}.

Traversal

[edit]
Main article:Tree traversal
See also:Threaded binary tree

A BST can betraversed through three basic algorithms:inorder,preorder, andpostorder tree walks.[10]: 287 

  • Inorder tree walk: Nodes from the left subtree get visited first, followed by the root node and right subtree. Such a traversal visits all the nodes in the order of non-decreasing key sequence.
  • Preorder tree walk: The root node gets visited first, followed by left and right subtrees.
  • Postorder tree walk: Nodes from the left subtree get visited first, followed by the right subtree, and finally, the root.

Following is a recursive implementation of the tree walks.[10]: 287–289 

 Inorder-Tree-Walk(x)if x ≠ NILthen     Inorder-Tree-Walk(x.left)visit node     Inorder-Tree-Walk(x.right)end if
 Preorder-Tree-Walk(x)if x ≠ NILthenvisit node     Preorder-Tree-Walk(x.left)     Preorder-Tree-Walk(x.right)end if
 Postorder-Tree-Walk(x)if x ≠ NILthen     Postorder-Tree-Walk(x.left)     Postorder-Tree-Walk(x.right)visit nodeend if

Balanced binary search trees

[edit]
Main article:Self-balancing binary search tree

Without rebalancing, insertions or deletions in a binary search tree may lead to degeneration, resulting in a heightn{\displaystyle n} of the tree (wheren{\displaystyle n} is number of items in a tree), so that the lookup performance is deteriorated to that of a linear search.[14] Keeping the search tree balanced and height bounded byO(log⁡n){\displaystyle O(\log n)} is a key to the usefulness of the binary search tree. This can be achieved by "self-balancing" mechanisms during the updation operations to the tree designed to maintain the tree height to the binary logarithmic complexity.[7][15]: 50 

Height-balanced trees

[edit]

A tree is height-balanced if the heights of the left sub-tree and right sub-tree are guaranteed to be related by a constant factor. This property was introduced by theAVL tree and continued by thered–black tree.[15]: 50–51  The heights of all the nodes on the path from the root to the modified leaf node have to be observed and possibly corrected on every insert and delete operation to the tree.[15]: 52 

Weight-balanced trees

[edit]
Main article:Weight-balanced tree

In a weight-balanced tree, the criterion of a balanced tree is the number of leaves of the subtrees. The weights of the left and right subtrees differ at most by1{\displaystyle 1}.[16][15]: 61  However, the difference is bound by a ratioα{\displaystyle \alpha } of the weights, since a strong balance condition of1{\displaystyle 1} cannot be maintained withO(log⁡n){\displaystyle O(\log n)} rebalancing work during insert and delete operations. Theα{\displaystyle \alpha }-weight-balanced trees gives an entire family of balance conditions, where each left and right subtrees have each at least a fraction ofα{\displaystyle \alpha } of the total weight of the subtree.[15]: 62 

Types

[edit]

There are several self-balanced binary search trees, includingT-tree,[17]treap,[18]red-black tree,[19]B-tree,[20]2–3 tree,[21] andSplay tree.[22]

Examples of applications

[edit]

Sort

[edit]
Main article:Tree sort

Binary search trees are used in sorting algorithms such astree sort, where all the elements are inserted at once and the tree is traversed at an in-order fashion.[23] BSTs are also used inquicksort.[24]

Priority queue operations

[edit]
Main article:Priority queue

Binary search trees are used in implementingpriority queues, using the node's key as priorities. Adding new elements to the queue follows the regular BST insertion operation but the removal operation depends on the type of priority queue:[25]

  • If it is an ascending order priority queue, removal of an element with the lowest priority is done through leftward traversal of the BST.
  • If it is a descending order priority queue, removal of an element with the highest priority is done through rightward traversal of the BST.

See also

[edit]

References

[edit]
  1. ^Pitassi, Toniann (2015)."CSC263: Balanced BSTs, AVL tree"(PDF).University of Toronto, Department of Computer Science. p. 6.Archived(PDF) from the original on 14 February 2019. Retrieved19 May 2022.
  2. ^Myers, Andrew."CS 312 Lecture: AVL Trees".Cornell University, Department of Computer Science.Archived from the original on 27 April 2021. Retrieved19 May 2022.
  3. ^Adelson-Velsky, Georgy; Landis, Evgenii (1962). "An algorithm for the organization of information".Proceedings of the USSR Academy of Sciences (in Russian).146:263–266.English translation by Myron J. Ricci inSoviet Mathematics - Doklady, 3:1259–1263, 1962.
  4. ^abCulberson, J.; Munro, J. I. (1 January 1989)."Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations".The Computer Journal.32 (1):68–69.doi:10.1093/comjnl/32.1.68.
  5. ^Culberson, J.; Munro, J. I. (28 July 1986)."Analysis of the standard deletion algorithms in exact fit domain binary search trees".Algorithmica.5 (1–4).Springer Publishing,University of Waterloo: 297.doi:10.1007/BF01840390.S2CID 971813.
  6. ^P. F. Windley (1 January 1960)."Trees, Forests and Rearranging".The Computer Journal.3 (2): 84.doi:10.1093/comjnl/3.2.84.
  7. ^abKnuth, Donald (1998). "Section 6.2.3: Balanced Trees".The Art of Computer Programming(PDF). Vol. 3 (2 ed.).Addison-Wesley. pp. 458–481.ISBN 978-0201896855.Archived(PDF) from the original on 2022-10-09.
  8. ^Paul E. Black, "red-black tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 November 2019. (accessed May 19 2022) from:https://www.nist.gov/dads/HTML/redblack.html
  9. ^abThareja, Reema (13 October 2018). "Hashing and Collision".Data Structures Using C (2 ed.).Oxford University Press.ISBN 9780198099307.
  10. ^abcdefghijklmnoCormen, Thomas H.;Leiserson, Charles E.;Rivest, Ronald L.;Stein, Clifford (2001).Introduction to Algorithms (2nd ed.).MIT Press.ISBN 0-262-03293-7.
  11. ^R. A. Frost; M. M. Peterson (1 February 1982)."A Short Note on Binary Search Trees".The Computer Journal.25 (1).Oxford University Press: 158.doi:10.1093/comjnl/25.1.158.
  12. ^Junzhou Huang."Design and Analysis of Algorithms"(PDF).University of Texas at Arlington. p. 12.Archived(PDF) from the original on 13 April 2021. Retrieved17 May 2021.
  13. ^Ray, Ray."Binary Search Tree".Loyola Marymount University, Department of Computer Science. Retrieved17 May 2022.
  14. ^Thornton, Alex (2021)."ICS 46: Binary Search Trees".University of California, Irvine.Archived from the original on 4 July 2021. Retrieved21 October 2021.
  15. ^abcdeBrass, Peter (January 2011).Advanced Data Structure.Cambridge University Press.doi:10.1017/CBO9780511800191.ISBN 9780511800191.
  16. ^Blum, Norbert; Mehlhorn, Kurt (1978)."On the Average Number of Rebalancing Operations in Weight-Balanced Trees"(PDF).Theoretical Computer Science.11 (3):303–320.doi:10.1016/0304-3975(80)90018-3.Archived(PDF) from the original on 2022-10-09.
  17. ^Lehman, Tobin J.; Carey, Michael J. (25–28 August 1986).A Study of Index Structures for Main Memory Database Management Systems. Twelfth International Conference on Very Large Databases (VLDB 1986). Kyoto.ISBN 0-934613-18-4.
  18. ^Aragon, Cecilia R.; Seidel, Raimund (1989),"Randomized Search Trees"(PDF),30th Annual Symposium on Foundations of Computer Science, Washington, D.C.: IEEE Computer Society Press, pp. 540–545,doi:10.1109/SFCS.1989.63531,ISBN 0-8186-1982-1,archived(PDF) from the original on 2022-10-09
  19. ^Cormen, Thomas H.;Leiserson, Charles E.;Rivest, Ronald L.;Stein, Clifford (2001). "Red–Black Trees".Introduction to Algorithms (second ed.). MIT Press. pp. 273–301.ISBN 978-0-262-03293-3.
  20. ^Comer, Douglas (June 1979), "The Ubiquitous B-Tree",Computing Surveys,11 (2):123–137,doi:10.1145/356770.356776,ISSN 0360-0300,S2CID 101673
  21. ^Knuth, Donald M (1998). "6.2.4".The Art of Computer Programming. Vol. 3 (2 ed.). Addison Wesley.ISBN 9780201896855.The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3.
  22. ^Sleator, Daniel D.;Tarjan, Robert E. (1985)."Self-Adjusting Binary Search Trees"(PDF).Journal of the ACM.32 (3):652–686.doi:10.1145/3828.3835.S2CID 1165848.
  23. ^Narayanan, Arvind (2019)."COS226: Binary search trees".Princeton University School of Engineering and Applied Science.Archived from the original on 22 March 2021. Retrieved21 October 2021 – via cs.princeton.edu.
  24. ^Xiong, Li."A Connection Between Binary Search Trees and Quicksort".Oxford College of Emory University, The Department of Mathematics and Computer Science.Archived from the original on 26 February 2021. Retrieved4 June 2022.
  25. ^Myers, Andrew."CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps".Cornell University,Department of Computer Science.Archived from the original on 21 October 2021. Retrieved21 October 2021.

Further reading

[edit]

External links

[edit]
Wikimedia Commons has media related toBinary search trees.
Search trees
(dynamic sets,
associative arrays)
Heaps
Tries
Spatial data
partitioning trees
Other trees
Types
Abstract
Arrays
Linked
Trees
Graphs
Retrieved from "https://en.wikipedia.org/w/index.php?title=Binary_search_tree&oldid=1325045229"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp