binary search tree

<2024-02-01 Thu 17:29:43> mahmood
cs
a binary search tree is a binary tree that has the following restrictions:
  • the keys of all the nodes in the left subtree of any given node x is smaller than the key of x
  • the keys of all the nodes in the right side of the tree are bigger or equal to the key of x
for example the following tree is a binary search tree:
a new key is always inserted as a leaf. we start from the root, making our way downwards by comparing the new key to the key of the current node to decide which child to move to on each iteration, until we hit a leaf node, then we add the new node as its child
a BST can be viewed is a model of computation where data must be stored as keys in a binary search tree. each key has a pointer to its parent (unless it is the root) and a pointer to its left and right children, or a null pointer if they do not exist. the value of the key stored in the left child of a node must be less than or equal to the value of the key stored at the node, which is in turn less than or equal to the value of the key stored at the right child. the model supports the following unit-cost operations:
  • walk to left child,
  • walk to right child,
  • walk to parent,
  • rotate node .
the first three operations only change a pointer into the tree. the last operation updates the tree itself.
these models support the query \code{search(x)}, which starts with a pointer to the root and can use the above operations, but must at some point visit the node with key .
[cite:;taken2 from @ds_demaine_2012 chapter 5.2 binary search trees]