Content deleted Content added
just use the redirect rather than a broken slink |
|||
Line 88:
|
BST-Successor(x)
'''if''' x.right ≠ NIL '''then'''
'''return''' BST-Minimum(x.right)
'''end if'''
y := x.parent
'''while''' y ≠ NIL '''and''' x = y.right '''do'''
x := y
y := y.parent
'''repeat'''
'''return''' y
|
BST-Predecessor(x)
'''if''' x.left ≠ NIL '''then'''
'''return''' BST-Maximum(x.left)
'''end if'''
y := x.parent
'''while''' y ≠ 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}}
Line 114:
|
BST-Maximum(x)
'''while''' x.right ≠ NIL '''do'''
x := x.right
'''repeat'''
'''return''' x
|
BST-Minimum(x)
'''while''' x.left ≠ NIL '''do'''
x := x.left
'''repeat'''
'''return''' x
|}
| |||