Editing Binary search tree (section)

==Operations==
===Searching===
Searching in a binary search tree for a specific key can be programmed [[recursion (computer science)|recursively]] or [[iteration#Computing|iteratively]].

Searching begins by examining the [[root node]]. If the tree is [[Null pointer|{{math|{{text|nil}}}}]], 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 is <math>\text{nil}</math>. If the searched key is not found after a <math>\text{nil}</math> subtree is reached, then the key is not present in the tree.{{r|algo_cormen|pp=290-291}}

====Recursive search====
The following [[pseudocode]] implements the BST search procedure through [[recursion (computer science)|recursion]].<ref name="algo_cormen" />{{rp|290}}
{|
|- style="vertical-align:top"
|
 Recursive-Tree-Search(x, key)
     '''if''' x = NIL '''or''' key = x.key '''then'''
         '''return''' x
     '''if''' key < x.key '''then'''
         '''return''' Recursive-Tree-Search(x.left, key)
     '''else'''
         '''return''' Recursive-Tree-Search(x.right, key)
     '''end if'''
|}
The recursive procedure continues until a <math>\text{nil}</math> or the <math>\text{key}</math> being searched for are encountered.

====Iterative search====
The recursive version of the search can be "unrolled" into a [[while loop]]. On most machines, the iterative version is found to be more [[Computer performance|efficient]].<ref name="algo_cormen" />{{rp|291}}
{|
|- style="vertical-align:top"
|
 Iterative-Tree-Search(x, key)
     '''while''' x &ne; NIL '''and''' key &ne; x.key '''do'''
         '''if''' key < x.key '''then'''
             x := x.left
         '''else'''
             x := x.right
         '''end if'''
     '''repeat'''
     '''return''' x
|}
Since the search may proceed till some [[leaf node]], the running time complexity of BST search is <math>O(h)</math> where <math>h</math> is the [[Tree (data structure)#Terminology|height of the tree]]. However, the worst case for BST search is <math>O(n)</math> where <math>n</math> is the total number of nodes in the BST, because an unbalanced BST may degenerate to a linked list. However, if the BST is [[height-balanced tree|height-balanced]] the height is <math>O(\log n)</math>.<ref name="algo_cormen" />{{rp|290}}

====Successor and predecessor====
For certain operations, given a node <math>\text{x}</math>, finding the successor or predecessor of <math>\text{x}</math> is crucial. Assuming all the keys of a BST are distinct, the successor of a node <math>\text{x}</math> in a BST is the node with the smallest key greater than <math>\text{x}</math>'s key. On the other hand, the predecessor of a node <math>\text{x}</math> in a BST is the node with the largest key smaller than <math>\text{x}</math>'s key. The following pseudocode finds the successor and predecessor of a node <math>\text{x}</math> in a BST.<ref>{{cite web|url=https://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-url=https://web.archive.org/web/20210413045057/http://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-date=13 April 2021|page=12|publisher=[[University of Texas at Arlington]]|access-date=17 May 2021|url-status=live|title=Design and Analysis of Algorithms|author=Junzhou Huang}}</ref><ref>{{cite web |author=Ray |first=Ray |title=Binary Search Tree |url=https://cs.lmu.edu/~ray/notes/binarysearchtrees/ |access-date=17 May 2022 |publisher=[[Loyola Marymount University]], Department of Computer Science}}</ref><ref name="algo_cormen" />{{rp|292–293}}
{|
|- style="vertical-align:top"
|
  BST-Successor(x)
      '''if''' x.right &ne; NIL '''then'''
          '''return''' BST-Minimum(x.right)
      '''end if'''
      y := x.parent
      '''while''' y &ne; NIL '''and''' x = y.right '''do'''
          x := y
          y := y.parent
      '''repeat'''
      '''return''' y
|
  BST-Predecessor(x)
      '''if''' x.left &ne; NIL '''then'''
          '''return''' BST-Maximum(x.left)
      '''end if'''
      y := x.parent
      '''while''' y &ne; NIL '''and''' x = y.left '''do'''
          x := y
          y := y.parent
      '''repeat'''
      '''return''' 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.<ref name="algo_cormen" />{{rp|291–292}}
{|
|- style="vertical-align:top"
|
  BST-Maximum(x)
      '''while''' x.right &ne; NIL '''do'''
          x := x.right
      '''repeat'''
      '''return''' x
|
  BST-Minimum(x)
      '''while''' x.left &ne; NIL '''do'''
          x := x.left
      '''repeat'''
      '''return''' x
|}

===Insertion===
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 as [[leaf nodes]] in the BST.<ref name="algo_cormen" />{{rp|294–295}} Following is an iterative implementation of the insertion operation.<ref name="algo_cormen" />{{rp|294}}
{|
|- style="vertical-align:top"
|
 1    BST-Insert(T, z)
 2      y := NIL
 3      x := T.root
 4      '''while''' x &ne; NIL '''do'''
 5        y := x
 6        '''if''' z.key < x.key '''then'''
 7          x := x.left
 8        '''else'''
 9          x := x.right
 10       '''end if'''
 11     '''repeat'''
 12     z.parent := y
 13     '''if''' y = NIL '''then'''
 14       T.root := z
 15     '''else if''' z.key < y.key '''then'''
 16       y.left := z
 17     '''else'''
 18       y.right := z
 19     '''end if'''
|}
The procedure maintains a "trailing pointer" <math>\text{y}</math> as a parent of <math>\text{x}</math>. After initialization on line 2, the '''while''' loop along lines 4-11 causes the pointers to be updated. If <math>\text{y}</math> is <math>\text{nil}</math>, the BST is empty, thus <math>\text{z}</math> is inserted as the root node of the binary search tree <math>\text{T}</math>, if it is not <math>\text{nil}</math>, insertion proceeds by comparing the keys to that of <math>\text{y}</math> on the lines 15-19 and the node is inserted accordingly.<ref name="algo_cormen" />{{rp|295}}

===Deletion===
[[File:BST node deletion.png|thumb|400px|right|Binary search tree node deletion process.]]
The deletion of a node, say <math>\text{Z}</math>, from the binary search tree <math>\text{BST}</math> has three cases:{{r|algo_cormen|p=295-297}}
# If <math>\text{Z}</math> is a leaf node, it is replaced by <math>\text{NIL}</math> as shown in (a).
# If <math>\text{Z}</math> has only one child, the child node of <math>\text{Z}</math> gets elevated by modifying the parent node of <math>\text{Z}</math> to point to the child node, consequently taking <math>\text{Z}</math>'s position in the tree, as shown in (b) and (c).
# If <math>\text{Z}</math> has both left and right children, the [[Tree_traversal#In-order,_LNR|in-order]] successor of <math>\text{Z}</math>, say <math>\text{Y}</math>, displaces <math>\text{Z}</math> by following the two cases:
## If <math>\text{Y}</math> is <math>\text{Z}</math>'s right child, as shown in (d), <math>\text{Y}</math> displaces <math>\text{Z}</math> and <math>\text{Y}</math>'s right child remain unchanged.
## If <math>\text{Y}</math> lies within <math>\text{Z}</math>'s right subtree but is not <math>\text{Z}</math>'s right child, as shown in (e), <math>\text{Y}</math> first gets replaced by its own right child, and then it displaces <math>\text{Z}</math>'s position in the tree.
# Alternatively, the in-order predecessor can also be used.

The following pseudocode implements the deletion operation in a binary search tree.{{r|algo_cormen|p=296-298}}
{|
|- style="vertical-align:top"
|
 1    BST-Delete(BST, z)
 2      '''if''' z.left = NIL '''then'''
 3        Shift-Nodes(BST, z, z.right)
 4      '''else if''' z.right = NIL '''then'''
 5        Shift-Nodes(BST, z, z.left)
 6      '''else'''
 7        y := BST-Successor(z)
 8        '''if''' y.parent &ne; z '''then'''
 9          Shift-Nodes(BST, y, y.right)
 10         y.right := z.right
 11         y.right.parent := y
 12       '''end if'''
 13       Shift-Nodes(BST, z, y)
 14       y.left := z.left
 15       y.left.parent := y
 16     '''end if'''
|-
|
 1    Shift-Nodes(BST, u, v)
 2      '''if''' u.parent = NIL '''then'''
 3        BST.root := v
 4      '''else if''' u = u.parent.left '''then'''
 5        u.parent.left := v
 5      '''else'''
 6        u.parent.right := v
 7      '''end if'''
 8      '''if''' v &ne; NIL '''then'''
 9        v.parent := u.parent
 10     '''end if'''
|}
The <math>\text{BST-Delete}</math> 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. The [[helper function]] <math>\text{Shift-Nodes}</math> is used within the deletion algorithm for the purpose of replacing the node <math>\text{u}</math> with <math>\text{v}</math> in the binary search tree <math>\text{BST}</math>.{{r|algo_cormen|p=298}} This procedure handles the deletion (and substitution) of <math>\text{u}</math> from <math>\text{BST}</math>.