Binary Trees Top Heaps Contents

Binary Search Trees

Synopsis

A binary search tree is a binary tree where the nodes in the tree are ordered by ther values. Usually nodes on the left side are "less than" than those on the right side of the tree, recursively. When we say a node A is less than a node B, we mean the value stored at node A is less than the value stored at node B. More specifically, the following rules apply at any point in the tree.

Structure

    class binaryTreeNode
        {
        var value;
        var left;
        var right;
        var parent;            //optional
        }

    class binarySearchTree
        {
        var root;               //the top-level binary tree node
        // operations
        ...
        }

Vocabulary

The terms used in describing a binary search tree are the same as those describing a generic binary tree.

Supports

Binary search trees are considered top-level data structures.

Dependencies

Binary search trees are based upon tree nodes.

Operations

The operation descriptions assume unique values in the tree, with values to the left less than those to the right. For trees with duplicate values or a reversed ordering, appropriate modifications to the descriptions should be made.

insert

The typical insertion strategy looks like this:

The helper function implements this straegy, with current referring to its first argument and n refering to the second:

    if node n is less than the current node //n must belong on left side of tree
        if the current node has no left child
            set the left child pointer of the current node to n
        else 
            recur, passing the left child and n to the helper
     else //n must belong on right side of tree
         if the current node has no right child
            set the right child pointer of the current node to n
         else
            recur, passing the right child and n to the helper

A special case exists if the tree is empty, since the root pointer will need to be set. Inserting a value into a binary tree can take linear time, if the tree is pathologically unbalanced.

find

delete

There are a number of deletion strategies. One that preserves the existing balance of the tree to some degree is as follows...

Traversals

Traversals for binary search trees are the same as those of binary trees.

Concept Inventory

     
  1. Consider a binary search tree with n nodes. What is the best case time complexity for finding a value at a leaf?
    1. constant
    2. log n
    3. sqrt(n)
    4. linear
    5. n log n
    6. quadratic
     
  2. Consider a binary search tree with n nodes. What is the worst case time complexity for finding a value at a leaf?
    1. constant
    2. log n
    3. sqrt(n)
    4. linear
    5. n log n
    6. quadratic
     
  3. Which ordering of input values builds the most unbalanced BST? Assume values are inserted from left to right.
    1. 2
    2. 3
    3. 1
     
  4. Which ordering of input values builds the most balanced BST? Assume values are inserted from left to right.
    1. 5
    2. 7
    3. 8
     
  5. For all child nodes in a BST, what relationship holds between the value of a child node and the value of its parent?
    1. greater than or equal to
    2. less than or equal to
    3. greater than or equal to, if the child is a right child
    4. less than or equal to, if the child is a right child
    5. there is no relationship
     
  6. For all sibling nodes in a BST, what relationship holds between the value of a left child node and the value of its sibling?
    1. greater than or equal to
    2. less than or equal to
    3. equal to
    4. there is no relationship
     
  7. Do all these deletion strategies for non-leaf nodes reliably preserve BST ordering?
    1. true
    2. false

lusth@cs.ua.edu


Binary Trees Top Heaps Contents