[RA] Ch22 Binary Search Trees

Reading Assignment: All of Programming Chapter 22 Binary Search Trees

Binary Search Trees Concepts

We can combine the concepts of a linked dynamic data structure with the idea of binary search to come up with the idea of a binary search tree. A binary search tree is a data structure where the nodes have two pointers to other nodes, as well as whatever data they need to hold. The tree maintains he invariant that, for any node, all data to the left of that node is less than the data in the current node, and any all data to the right is greater than to that node. The tree itself holds one pointer to a node.

Observe that for each node in the tree, every node to its left is smaller, and every node to its right is greater.

Terminology

Node: A node in a graph is the structure which holds one item in the tree. That item may be comprised of multiple values depending on how we want to use the graphs.

Edge: An edge represents a connection between two nodes. For now we will only consider directed edges-meaning that they point from one node to another.

Graph: A graph is a collection of nodes and edges.

Directed Path: A path is a sequence of nodes which follows the edges of the graph, but do not repeat an edge.

Undirected Path: An undirected path is a path in which we ignore the direction of the edges, that is, our sequence of nodes can have a “from” node following the node it has an edge “to”.

Cycle: A cycle is a path which starts and ends at the same node-logically a “loop” in the graph. Trees do not have any cycles.

Undirected Cycle: An undirected cycle is an undirected path which starts and ends at the same node.

Connected: A graph is connected when there exists at least one undirected path between any pair of nodes.

Tree: A tree is a data structure comprised of nodes and edges which is a connected graph that has no undirected cycles.

Rooted tree: A rooted tree is a tree in which one particular node is the root node. The root node is special in that there exists directed path from it to every other node in the tree.

Binary Tree: A binary tree is a rooted tree where each node has at most two outgoing edges.

Binary Search Tree: A binary search tree is a binary tree which obeys the binary search tree ordering rules: everything to the left of a given node must be smaller than that node, and everything to the right must be greater or equal to that node.

Parent node: In a binary tree, the parent of a node is the node which points at it.

Children(node): The children of a node are the nodes which it directly points to.

Ancestor of a node: The ancestors of a node are the set of nodes from which there exists a directed path from the ancestor to that node.

Descendant of a node: The descendants of a node are the sets of nodes from which there exists a directed path from the node to its descendant.

Depth of a node: The depth of a node is the length of the path from the root node to that node. We will use the convention that the root is at depth 0.

Leaf Node: A leaf node is a node with no children

Sub-tree A sub-tree is a tree formed by taking the descendants of a particular node in a tree along with the edges that connect them, and forming tree from those.

Height: The height of a node is the maximum length path from it to a leaf node. We will use the convention that a leaf node has height 1, and the height of NULL is 0.

Height of a tree: The height of a tree is the height of its root.

Full: A binary tree is full if every node either has 0 children or 2 children.

Balanced: For every node in the tree, the height of its children differ by at most 1.

Complete: A binary tree is complete when every level, except possibly the last, has as many nodes as it possibly can have, and the last level is filled in from left to right.

Uses

One use of binary seach tress is to implement Map and Set ADTs with $O(lg(N))$ access time for addition, lookup and removal.

A Map or Set implemented with a binary search tree requires that the keys be a totally ordered type-that is a type, where we can compare any two elements and conclude that either $a < b $, $ a = b $ or $ a > b $. This restriction means we would not be able to use a binary tree for keys whose type cannot be compared to form an ordering. However, the fact that this restriction is the only restriction one the type of keys we use means that we may be able to use a binary search tree when we cannot use other types.

Adding to a Binary Search Tree

An example of inserting a node into a binary search tree.

Recursion

The base case is adding to am empty tree, which is trivial-the resulting tree is a single node with the key and that we want. In the recursive case, we compare the current node’s key we want to add, then recursively add to the appropriate sub-tree.

Node * add (Node *current, int toAdd) {
  if (current == NULL){
    return new Node(toAdd);
  }
  else{
    if (toADD < current->data) {
      current->left = add(current->left, toAdd);
    }
    else {
      current->right = add(current->right, toAdd);
    }
  }
  return current;
}

Find the Parent of the Node to Add

We could add to a binary search tree by keeping a pointer to a node, and iteratively seeking out the node whose left or right pointer we need to update. As with linked lists, such an approach must stop at the node which will be the parent of the newly added node, and adding to the empty tree is a special case.

Pointer to a Pointer to a Node

void add(int toAdd){
  Node ** curr = &root;
  while(*curr != NULL){
    if (toAdd < (*curr)->data) {
        curr = &((*curr)->left);
    }
    else{
        curr = &((*curr)->right);
    }
  }
  *curr = new Node(toAdd);
}

Searching a Binary Tree

bool contains(int toFind) {
  Node * current = root;
  while (current != NULL) {
    if (toFind == current->data) {
      return true;
    }
    else if (toFind < current->data) {
      current = current->left;
    }
    else {
      current = current->right;
    }
  }
}

Removing From a Binary Search Tree

Removing from a binary search tree is a matter of first finding the node you want to remove. The standard approach to removing from a tree in the case where the node to be removed has two children is to find the most similar node in the tree that has 0 or 1 children, put its data into the node we want to remove, then remove that node from the tree.

if (node->left == NULL) {
  temp = node->right;
  delete node;
  return temp;
}
else if (node->right == NULL) {
    //...
}
else {
    //...
}

Tree Traversal

Inorder Traversal

An inorder traversal prints the data of the tree in ascending order. We need to

print all items in the left sub-tree in ascending order
print N’s data
print all items in the right sub-tree in ascending order

First, we need a base case. For trees, a very natural base case is the empty tree. We can print the elements in the empty tree quite easily-just do nothing.

We also want to ensure that our algorithm always terminates. We can ensure termination by coming up with a measure function which strictly decreases whenever we recurse.

void printInorder(Node * current) {
  if (current != NULL) {
    printInorder(current->left);
    std::cout << current-> data << " ";
    printInorder(current->right);
  }
}

Preorder Traversals

void printInorder(Node * current) {
  if (current != NULL) {
    std::cout << current-> data << " ";
    printInorder(current->left);
    printInorder(current->right);
  }
}

A preorder traversal produces an ordering that will reconstruct the tree with the exact same structure if you were to use read the items and add them to an empty tree.

Postorder Traversals

void printInorder(Node * current) {
  if (current != NULL) {
    printInorder(current->left);
    printInorder(current->right);
    std::cout << current-> data << " ";
  }
}

If we want to delete all of the nodes in the tree, we need to recursively destroy both children, then delete the node itself.

void destroy(Node *current) {
  if (current != NULL) {
    destroy(current->left);
    destroy(current->right);
    delete current;
  }
}