Growing with the Web

Binary search tree

Published , updated
Tags:

A binary search tree (BST) is a node-based tree data structure in which each node can have at most two children, it supports several operations common to any search tree such as search, insert and delete.

Operations on a BST always start at the root node and work their way down, due of this the maximum time each operation takes is based on how high the tree is. For example a tree with n nodes where there are no right children will take O(n) time, a complete BST however (every level except the last is completely filled, with nodes on the last as left as possible) has the worst case time of O(\log n).

Time complexity

Operation Description Complexity
Delete Deletes a node given a key O(n)*
Insert Inserts a node with an associated key O(n)*
Search Searches for and returns a node using its key O(n)*

* O(\log n) average case

Properties

As the name suggests, a BST is a binary tree, only with the following restrictions placed on what nodes can go where:

  • For each node x, every value found in the left sub-tree of x is less than or equal to the value found in x.
  • For each node x, every value found in the right sub-tree of x is greater than or equal to the value found in x.

Representation

There are two main ways of representing a binary tree. The first is using node objects that have references to their children.

Tree representation

The second is using a regular array and manipulating the index of the node to find its children. The index of the left child of a node is 2i + 1 and the index of the right is 2i + 2 where i is the index of the parent.

Array representation

The index of node's parent can also be retrieved with \lfloor(i - 1) / 2\rfloor.

Operations

Delete

The delete operation looks at the root node and compares its value with the function parameter n. If the node is equal to n then this node to be deleted has been found. If not, binary search is performed; if n is less than the node it moves to the left node, if n is greater than the node it moves to the right now. This continues until the node has been found.

When a node has been selected for deletion, the tree needs to be reorganised depending on how many children the node being deleted has.

  • If the node has no children then it is simply deleted.
  • If the node has only a left child node, move the left child to the deleted node’s position.
  • If the node has only a right child node, move the right child to the deleted node’s position.
  • If the node has both left and right children, the minimum node from the right sub-tree is moved to the deleted node’s position. If the minimum node had a right child, it is moved into the minimum node’s old position.
Deleting a node with both children
Resulting tree

Insert

The insert operation performs binary search on the root node, moving to the left child if n is less than the current node or right if n is greater than the current node. This continues until the left or right children do not exist, which is where the new node is inserted.

The search operation performs binary search much like the insert operation to determine whether n exists.

Code

/**
 * Generic implementation of a binary search tree.
 */
public class BinarySearchTree<K extends Comparable<K>> implements BinarySearchTreeInterface<K> {

    /**
     * The root node of the binary search tree.
     */
    private BinarySearchTreeNode<K> root;

    /**
     * The size of the binary search tree.
     */
    private int size;

    /**
     * Creates a new {@link BinarySearchTree}.
     */
    public BinarySearchTree() { }

    /** {@inheritDoc} */
    public void insert(K key) {
        if (root == null) {
            root = new BinarySearchTreeNode<K>(key);
            size++;
            return;
        }

        insert(key, root);
    }

    /**
     * Inserts a {@link BinarySearchTreeNode} with a specific key.
     *
     * @param key The key of the node being inserted.
     * @param node The current tree being looked at.
     */
    private void insert(K key, BinarySearchTreeNode<K> node) {
        if (node == null) {
            node = new BinarySearchTreeNode(key);
            size++;
            return;
        }

        if (key.compareTo(node.getKey()) < 0) {
            if (node.leftExists()) {
                insert(key, node.getLeft());
            } else {
                node.setLeft(new BinarySearchTreeNode(key));
                size++;
            }
        }

        if (key.compareTo(node.getKey()) > 0) {
            if (node.rightExists()) {
                insert(key, node.getRight());
            } else {
                node.setRight(new BinarySearchTreeNode(key));
                size++;
            }
        }
    }

    /** {@inheritDoc} */
    public void delete(K key) {
        if (root == null) {
            return;
        }

        deleteInternal(key, root);
    }

    /**
     * Finds a {@link BinarySearchTreeNode} matching a specific key from the
     * tree and deletes it.
     *
     * @param key The key of the node being deleted.
     * @param node The current tree being looked at.
     */
    private void deleteInternal(K key, BinarySearchTreeNode<K> node) {
        if (key.compareTo(node.getKey()) < 0) {
            if (node.leftExists()) {
                deleteInternal(key, node.getLeft());
            }
            if (node.leftExists() && node.getLeft().isDeleted()) {
                node.setLeft(null);
            }
            return;
        }

        if (key.compareTo(node.getKey()) > 0) {
            if (node.rightExists()) {
                deleteInternal(key, node.getRight());
            }
            if (node.rightExists() && node.getRight().isDeleted()) {
                node.setRight(null);
            }
            return;
        }

        deleteInternal(node);
    }

    /**
     * Deletes a {@link BinarySearchTreeNode} from the tree.
     *
     * @param node The node to delete.
     */
    private void deleteInternal(BinarySearchTreeNode<K> node) {
        size--;
        // No children exist, mark this node as deleted
        if (!(node.leftExists() || node.rightExists())) {
            node.setDeleted(true);
            return;
        }

        // Only the left child exists, move the left node to this position
        if (node.leftExists() && !node.rightExists()) {
            node.setKey(node.getLeft().getKey());
            if (node.getLeft().rightExists()) {
                node.setRight(node.getLeft().getRight());
            }
            if (node.getLeft().leftExists()) {
                node.setLeft(node.getLeft().getLeft());
            } else {
                node.setLeft(null);
            }
            return;
        }

        // Only the right child exists, move the right node to this position
        if (node.rightExists() && !node.leftExists()) {
            node.setKey(node.getRight().getKey());
            if (node.getRight().leftExists()) {
                node.setLeft(node.getRight().getLeft());
            }
            if (node.getRight().rightExists()) {
                node.setRight(node.getRight().getRight());
            } else {
                node.setRight(null);
            }
            return;
        }

        // Both children exist, replace this node with with minimum node from
        // the right sub-tree
        K min = findMin(node.getRight());
        node.setKey(min);
    }

    /** {@inheritDoc} */
    public int size() {
        return size;
    }

    /** {@inheritDoc} */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Recursively finds the {@link BinarySearchTreeNode} with the smallest key.
     *
     * @param node The current tree being looked at.
     */
    private K findMin(BinarySearchTreeNode<K> node) {
        if (!node.leftExists()) {
            node.setDeleted(true);
            return node.getKey();
        }

        K min = findMin(node.getLeft());
        if (node.getLeft().isDeleted()) {
            node.setLeft(null);
        }
        return min;
    }

    /** {@inheritDoc} */
    public boolean contains(K key) {
        if (root == null) {
            return false;
        }

        return contains(key, root);
    }

    /**
     * Recursively determines whether a {@link BinarySearchTreeNode} matching a
     * specific key exists.
     *
     * @param key The key to search for.
     * @param node The current tree being looked at.
     * @return Whether a node with the key exists.
     */
    private boolean contains(K key, BinarySearchTreeNode<K> node) {
        if (key == node.getKey()) {
            return true;
        }

        if (key.compareTo(node.getKey()) < 0) {
            if (!node.leftExists()) {
                return false;
            }
            return contains(key, node.getLeft());
        }

        if (key.compareTo(node.getKey())> 0 ) {
            if (!node.rightExists()) {
                return false;
            }
            return contains(key, node.getRight());
        }

        return false;
    }

    /**
     * @return A string that textually describes the tree.
     */
    public String toString() {
        return root.toString();
    }
}



/**
 * Generic implementation of a binary search tree node.
 */
public class BinarySearchTreeNode<K extends Comparable<K>> implements Comparable<BinarySearchTreeNode<K>> {

    /**
     * The string to represent a deleted node in {@link toString}.
     */
    private final String nullNodeString = "_";

    /**
     * The left child node.
     */
    private BinarySearchTreeNode<K> left;

    /**
     * The right child node.
     */
    private BinarySearchTreeNode<K> right;

    /**
     * The key.
     */
    private K key;

    /**
     * Whether the node is deleted.
     */
    private boolean isDeleted = false;

    /**
     * Creates a new {@link BinarySearchTreeNode}.
     *
     * @param key The key of the new node.
     */
    public BinarySearchTreeNode(K key) {
        this.key = key;
    }

    /**
     * @return A string that textually describes the tree rooted at this node.
     */
    @Override
    public String toString() {
        return key + " : " + ((leftExists() || rightExists()) ? ("{ " +
                (leftExists() ? left.toString() : nullNodeString) + " , " +
                (rightExists() ? right.toString() : nullNodeString) + " }") : "<leaf>");
    }

    /**
     * @return Whether the node has a left child.
     */
    public boolean leftExists() {
        return left != null;
    }

    /**
     * @return Whether the node has a right child.
     */
    public boolean rightExists() {
        return right != null;
    }

    /**
     * @return The key of this node.
     */
    public K getKey() {
        return key;
    }

    /**
     * Sets the key of this node.
     *
     * @param key The new key.
     */
    public void setKey(K key) {
        this.key = key;
    }

    /**
     * @return The left child node.
     */
    public BinarySearchTreeNode<K> getLeft() {
        return left;
    }

    /**
     * Sets the left child node.
     *
     * @param left The new left child node.
     */
    public void setLeft(BinarySearchTreeNode<K> left) {
        this.left = left;
    }

    /**
     * @return The right child node.
     */
    public BinarySearchTreeNode<K> getRight() {
        return right;
    }

    /**
     * Sets the right child node.
     *
     * @param right The new right child node.
     */
    public void setRight(BinarySearchTreeNode<K> right) {
        this.right = right;
    }

    /**
     * @return Whether the node has been deleted.
     */
    public boolean isDeleted() {
        return isDeleted;
    }

    /**
     * Sets whether the node has been soft-deleted, allowing a node to be
     * be excluded from searching without requiring a reference to its parent.
     *
     * @param isDeleted Whether the node is deleted
     */
    public void setDeleted(boolean isDeleted) {
        this.isDeleted = isDeleted;
    }

    @Override
    public int compareTo(BinarySearchTreeNode<K> o) {
        return key.compareTo(o.key);
    }
}
// file: binary-search-tree.js

var BaseBinaryTree = require('./base-binary-tree');
var BinaryTreeNode = require('./binary-tree-node');

/**
 * Creates a binary search tree.
 *
 * @constructor
 * @param {function} customCompare An optional custom node comparison
 * function.
 */
var BinarySearchTree = function (customCompare) {
  BaseBinaryTree.call(this);

  /**
   * The number of nodes in the tree.
   * @private
   */
  this.nodeCount = 0;

  if (customCompare) {
    this.compare = customCompare;
  }
};

BinarySearchTree.prototype = Object.create(BaseBinaryTree.prototype);

BinarySearchTree.prototype.constructor = BinarySearchTree;

/**
 * Adds a key to the {@link BinarySearchTree}.
 *
 * @param {Object} key The key to add.
 * @return {boolean} Whether the node was added.
 */
BinarySearchTree.prototype.add = function (key) {
  var newNode = new BinaryTreeNode(key);

  if (!this.root) {
    this.nodeCount++;
    this.root = newNode;
    return true;
  }

  var current = this.root;
  while (true) {
    if (this.compare(key, current.key) < 0) {
      if (!current.left) {
        current.left = newNode;
        this.nodeCount++;
        return true;
      }
      current = current.left;
    } else if (this.compare(key, current.key) > 0) {
      if (!current.right) {
        current.right = newNode;
        this.nodeCount++;
        return true;
      }
      current = current.right;
    } else {
      return false;
    }
  }
};

/**
 * Removes a key from the tree.
 *
 * @param {Object} key The key to remove.
 * @return {boolean} Whether the key was removed.
 */
BinarySearchTree.prototype.remove = function (key) {
  if (!this.root) {
    return false;
  }

  var parent;
  var current = this.root;
  while (true) {
    if (this.compare(key, current.key) < 0) {
      if (!current.left) {
        return false;
      }
      parent = current;
      current = current.left;
    } else if (this.compare(key, current.key) > 0) {
      if (!current.right) {
        return false;
      }
      parent = current;
      current = current.right;
    } else {
      this.nodeCount--;
      deleteNode(current, parent, this);
      return true;
    }
  }
};

/**
 * Determines whether the {@link BinarySearchTree} contains a key.
 *
 * @param {Object} key The key to check.
 * @return {boolean} Whether the node contains the key.
 */
BinarySearchTree.prototype.contains = function (key) {
  if (!this.root) {
    return false;
  }

  var current = this.root;
  while (true) {
    if (this.compare(key, current.key) < 0) {
      if (!current.left) {
        return false;
      }
      current = current.left;
    } else if (this.compare(key, current.key) > 0) {
      if (!current.right) {
        return false;
      }
      current = current.right;
    } else {
      return true;
    }
  }
};

/**
 * @return {Object} The maximum key of the tree.
 */
BinarySearchTree.prototype.findMaximum = function () {
  if (!this.root) {
    return undefined;
  }

  var current = this.root;
  while (true) {
    if (current.right) {
      current = current.right;
    } else {
      return current.key;
    }
  }
};

/**
 * @return {Object} The minimum key of the tree.
 */
BinarySearchTree.prototype.findMinimum = function () {
  if (!this.root) {
    return undefined;
  }

  var current = this.root;
  while (true) {
    if (current.left) {
      current = current.left;
    } else {
      return current.key;
    }
  }
};

/**
 * @return {boolean} Whether the tree is empty.
 */
BinarySearchTree.prototype.isEmpty = function () {
  return !this.root;
};

/**
 * @return The size of the tree.
 */
BinarySearchTree.prototype.size = function () {
  return this.nodeCount;
};

/**
 * Compares two nodes with each other.
 *
 * @param {Object} a The first key to compare.
 * @param {Object} b The second key to compare.
 * @return -1, 0 or 1 if a < b, a == b or a > b respectively.
 */
BinarySearchTree.prototype.compare = function (a, b) {
  if (a > b) {
    return 1;
  }
  if (a < b) {
    return -1;
  }
  return 0;
};

/**
 * Deletes a node from the tree.
 *
 * @private
 * @param {BinaryTreeNode} node The node being deleted.
 * @param {BinaryTreeNode} parent The parent of the node being deleted.
 * @param {BinaryTreeNode} tree The root of the tree.
 */
function deleteNode(node, parent, tree) {
  // No children exist, mark this node as deleted
  if (!node.left && !node.right) {
    if (parent) {
      parent.removeChild(node);
    } else {
      tree.root = undefined;
    }
    return;
  }

  // Only the left child exists, move the left node to this position
  if (node.left && !node.right) {
    node.key = node.left.key;
    node.right = node.left.right;
    node.left = node.left.left;
    return;
  }

  // Only the right child exists, move the right node to this position
  if (node.right && !node.left) {
    node.key = node.right.key;
    node.left = node.right.left;
    node.right = node.right.right;
    return;
  }

  // Both children exist, replace this node with with minimum node from the
  // right sub-tree
  var minParent = findParentOfMinimum(node.right, node);
  var minNode = minParent.left ? minParent.left : minParent.right;
  var newKey = minNode.key;
  deleteNode(minNode, minParent, tree);
  node.key = newKey;
}

/**
 * Finds the parent of the minimum node.
 *
 * @private
 * @param {BinaryTreeNode} node The node being searched.
 * @param {BinaryTreeNode} parent The parent of the node being searched.
 * @return The parent of the minimum node.
 */
function findParentOfMinimum(node, parent) {
  if (!node.left) {
    return parent;
  }

  return findParentOfMinimum(node.left, node);
}

module.exports = BinarySearchTree;



// file: base-binary-tree.js

/**
 * Creates a base binary tree.
 * @constructor
 */
var BaseBinaryTree = function () {
  /**
   * The root of the tree.
   * @protected
   */
  this.root = undefined;
};

/**
 * Performs a pre-order traversal, calling a function on each node.
 *
 * @param {function} visit A function that takes a node's key.
 */
BaseBinaryTree.prototype.traversePreOrder = function (visit) {
  if (!this.root) {
    return;
  }

  var parentStack = [];
  parentStack.push(this.root);
  do {
    var top = parentStack.pop();
    visit(top.key);
    if (top.right) {
      parentStack.push(top.right);
    }
    if (top.left) {
      parentStack.push(top.left);
    }
  } while (parentStack.length);
};

/**
 * Performs a in-order traversal, calling a function on each node.
 *
 * @param {function} visit A function that takes a node's key.
 */
BaseBinaryTree.prototype.traverseInOrder = function (visit) {
  var parentStack = [];
  var node = this.root;
  while (parentStack.length || node) {
    if (node) {
      parentStack.push(node);
      node = node.left;
    } else {
      node = parentStack.pop();
      visit(node.key);
      node = node.right;
    }
  }
};

/**
 * Performs a post-order traversal, calling a function on each node.
 *
 * @param {function} visit A function that takes a node's key.
 */
BaseBinaryTree.prototype.traversePostOrder = function (visit) {
  var parentStack = [];
  var node = this.root;
  var lastVisitedNode;
  while (parentStack.length || node) {
    if (node) {
      parentStack.push(node);
      node = node.left;
    } else {
      var nextNode = parentStack[parentStack.length - 1];
      if (nextNode.right && lastVisitedNode !== nextNode.right) {
        // if right child exists AND traversing node from left child, move
        // right
        node = nextNode.right;
      } else {
        parentStack.pop();
        visit(nextNode.key);
        lastVisitedNode = nextNode;
      }
    }
  }
};

module.exports = BaseBinaryTree;



// file: binary-tree-node.js

/**
 * Creates a binary tree node.
 *
 * @constructor
 * @param {Object} key The key of the node.
 * @param {BinaryTreeNode} parent The parent of the node.
 */
function BinaryTreeNode(key, parent) {
  /**
   * The key of the node.
   * @public
   */
  this.key = key;

  /**
   * The parent of the node.
   * @public
   */
  this.parent = parent;

  /**
   * The left child of the node.
   * @public
   */
  this.left = undefined;

  /**
   * The right child of the node.
   * @public
   */
  this.right = undefined;
}

/**
 * Removes a child from the node. This will remove the left or right node
 * depending on which one matches the argument.
 *
 * @param {Object} node The node to remove.
 */
BinaryTreeNode.prototype.removeChild = function (node) {
  if (this.left === node) {
    this.left = undefined;
  }
  if (this.right === node) {
    this.right = undefined;
  }
};

module.exports = BinaryTreeNode;

References

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Binary Search Trees” in Introduction to Algorithms, 2nd ed., Cambridge, MA: The MIT Press, 2001, ch. 12, pp.253-272

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.

 

Comments

comments powered by Disqus
Like this article?
Subscribe for more!