3.8.4.1 Binary Search Tree

Knowledge Base > Algorithm > Data Structure

Overview

Binary Search Tree is a binary tree data structure whose left subtree of a node contains only values less than the value of the node, and right subtree of a node contains only values greater than or equal to the value of the node.

Basic Operation

• void insert(val):
  insert a new node into a binary search tree. This operations runs at O(h) time, where h is the height of the tree.
• void delete(<E>):
  To remove a node, named x, from a binary search the tree. The deletion runs at O(h) time on a tree of height h.
• <E> search(key):
  an operation to search for a node with a given key runs at O(h) time on a tree of height h.
• <E> min():
  an operation that returns a pointer to the minimum element in the left-most subtree has a O(h) running time on a tree of height h.
• <E> max():
  an operation that returns a pointer to the maximum element in the right-most subtree has a O(h) running time on a tree of height h.
• void traversal():
  a Θ(n)-time operation that step through all elements of the tree. There are three ways to traverse a tree, depending on the order of stepping into a child nodes. The common traversal methods are in-order, pre-order, and post-order traversal.
• <E> successor(<E>):
  return the successor of node x in the tree. A successor is either the minimum value in the left subtree of x or the lowest ancestor of x whose left child is also an ancestor of x. This operations runs at O(h) time on a tree of height h.
• <E> predecessor(<E>):
  return the predecessor of node x in the tree. A predecessor is either the maximum value in the right subtree of x or the lowest ancestor of x whose right child is also an ancestor of x. This operations runs at O(h) time on a tree of height h.
• <E> parent(<E>);
  return the parent of node x in the tree. This operations runs at O(h) time on a tree of height h.
• int height(<E>):
  return the height of node x in the tree. This operations runs at O(h) time on a tree of height h.
• int depth(<E>):
  return the depth of node x in the tree. This operations runs at O(h) time on a tree of height h.

Algorithm

Pseudocode

Tree-Successor(x)

1 if right[x]≠nil 2    then return Tree-Minimum(right[x]) 3 y ← p[x] 4 while y≠nil and x = right[y] 5 do x ← y 6       y ← p[y] 7 return y

Tree-Predecessor(x)

1 if left[x]≠nil 2    then return Tree-Maximum(left[x]) 3 y ← p[x] 4 while y≠nil and x = left[y] 5 do x ← y 6       y ← p[y] 7 return y

Tree-Insert(T,z)
 

1 y ← nil 2 x ← root[T] 3 while x≠nil 4 do y ← x 5       if key[z] < key[x] 6          then x ← left[x] 7          else x ← right[x] 8 p[z] ← y 9 if y = nil 10    then root[T] ← z   ⊴ Tree T was empty 11    else if key[z] <  idkey[y] 12          then left[y] getsz 13          else right[y] ← z

Tree-Delete(T,z)
 

1 if left[z] = nil or right[z] = nil 2    then y ← z 3    else y ← Tree-Successor(z) 4 if left[y]≠nil 5    then x ← left[y] 6    else x ← right[y] 7 if x≠nil 8    then p[x] ← p[y] 9 if p[y] = nil 10    then root[T] ← x 11    else if y = left[p[y]] 12          then left[p[y]] ← x 13          else right[p[y]] ← x 14 if y≠z 15    then key[z] ← key[y] 16       copy y’s satellite data into z 17 return y

Source Code

Here is the BST implementation, written in C:

• Binary Search Tree (C)
  
  
  

Related Topics

• Red-Black Tree
• AVL Tree