Binary Search Tree Queries

Source

This is the next post in a series on Binary Search Trees that start with this post. In this post we'll look at some basic queries we can make using the tree.

A Query Class

The textbook(s) treat these as functions, but they seem to suggest to me methods of a class, so I'll make one. The TYPE_CHECKING and annotations imports are to prevent circular imports as noted on Adam Johnson's blog.

# python
from __future__ import annotations
from typing import TYPE_CHECKING

# this project
if TYPE_CHECKING:
    from .node import Node
    from .tree import Tree

class Query:
    """Holds a tree and performs queries on it

    Args:
     tree: A Binary Search Tree
    """
    def __init__(self, tree: Tree):
        self.tree = tree
        return

Search

The first thing we'll look at is searching for a Node in a Binary Search Tree. Because of the way the tree is structured the search looks a lot like a Binary Search where we start at the root of the tree and then work our way downwards, picking the next child to follow based on whether the key we're searching for is greater than the right child's key or less than the left child's key. If it's equal then we've found the node we want.

The Algorithm

The Iterative Version

The recursive version of TreeSearch is quite nice, but it also translates easily to an iterative version if for some reason performance or size becomes a problem.

The Implementation

I'll add the iterative version of the Tree Search as a method for our Query class.

def search(self, key) -> Node:
    """Searches the tree for the node with the matching key

    Args:
     key: node's key to search for

    Returns:
     the node with the key or None if it isn't in the tree
    """
    node = self.tree.root
    while node is not None and key != node.key:
        if key < node.key:
            node = node.left
        else:
           node = node.right
    return node

Testing

# pypi
from expects import be,be_none, equal, expect
from bowling.data_structures.binary_search_tree import Node, Tree
from bowling.data_structures.binary_search_tree import Query

root = Node(10)
tree = Tree(root)
query = Query(tree)
output = query.search(5)
expect(output).to(be_none)
expect(query.search(10)).to(equal(root))

five = Node(5)
tree.insert(five)
expect(query.search(5)).to(be(five))

fifteen = Node(15)
tree.insert(fifteen)
expect(query.search(15)).to(be(fifteen))

I'll have to think of something more interesting to show for this…

Miminum and Maximum

Mimimum

\begin{algorithm}
\caption{TreeMinimum}
\begin{algorithmic}
\INPUT The Node to start the search from.
\OUTPUT The Node with the smallest key.
\PROCEDURE{TreeMinimum}{x}
\WHILE {\textit{x}.left $\neq$ \textsc{NIL}}
   \STATE \textit{x} $\gets$ \textit{x}.left
\ENDWHILE
\RETURN \textit{x}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

The Implementation

I originally didn't take the root node as an argument, since I thought the minimum of the tree is always the smallest item. But this method gets used later on in the successor method where we want to find the smallest item in the right-subtree of a particular node, so the outcome won't necessarily be the smallest item in the tree.

def min(self, node: Node=None) -> Node:
    """Returns the node with the smallest key

    Args:
     node: a node to use as the starting root
    """
    if node is None:
        node = self.tree.root

    while node.left is not None:
        node = node.left
    return node

Testing

tree = Tree(Node(10))
query = Query(tree)
tree.insert(Node(5))
tree.insert(Node(2))
tree.insert(Node(15))
tree.insert(Node(17))
tree.insert(Node(11))
expect(query.min()).to(equal(Node(2)))

tree.insert(Node(1))
expect(query.min()).to(equal(Node(1)))

expect(query.min(tree.root.right)).to(equal(Node(11)))

Maximum

\begin{algorithm}
\caption{TreeMaximum}
\begin{algorithmic}
\INPUT The Node to start the search from.
\OUTPUT The Node with the largest key.
\PROCEDURE{TreeMaximum}{x}
\WHILE {\textit{x}.right $\neq$ \textsc{NIL}}
   \STATE \textit{x} $\gets$ \textit{x}.right
\ENDWHILE
\RETURN \textit{x}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

The Implementation

def max(self, root: Node=None) -> Node:
    """Returns the node with the largest key

    Args:
     root: subtree root to start at

    Returns:
     node with the largest key in tree/subtree
    """
    if root is None:
        root = self.tree.root
    while root.right is not None:
        root = root.right
    return root

Testing

tree = Tree(Node(10))
query = Query(tree)
tree.insert(Node(5))
tree.insert(Node(2))
tree.insert(Node(15))

expect(query.max()).to(equal(Node(15)))

tree.insert(Node(17))
expect(query.max()).to(equal(Node(17)))
expect(query.min()).to(equal(Node(2)))

expect(query.max(tree.root.left)).to(equal(Node(5)))

Tree Successor

A "Successor" node is the next largest node after a given node. Since all the nodes in a right subtree are greater than the node, it's the smallest node in the right (if it exists). If the right subtree is empty then we traverse up the ancestors of the node until we find the first one that is greater than our node.

\begin{algorithm}
\caption{TreeSuccessor}
\begin{algorithmic}
\INPUT The Node to start the search from.
\OUTPUT The Node with the next largest key.
\PROCEDURE{TreeSuccessor}{x}
\IF {\textit{x}.right $\neq$ \textsc{NIL}}
  \RETURN \textsc{TreeMinimum}(\textit{x}.right)
\ENDIF

\STATE \textit{y} $\gets$ \textit{x}.parent

\WHILE {\textit{y} $\neq$ \textsc{NIL} and \textit{x} = \textit{y}.right}
   \STATE \textit{x} $\gets$ \textit{y}
   \STATE \textit{y} $\gets$ \textit{y}.parent
\ENDWHILE
\RETURN \textit{y}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

def successor(self, node: Node) -> Node:
    """Returns the next largest node

    Args:
     node: the node who's successor to find

    Returns:
     successor node to the input node
    """
    if node.right is not None:
        return self.min(node.right)

    successor = node.parent
    while successor is not None and node == successor.right:
        node = successor
        successor = successor.parent
    return successor

tree = Tree(Node(10))
query = Query(tree)
tree.insert(Node(5))
tree.insert(Node(2))
tree.insert(Node(15))
tree.insert(Node(17))
expect(query.successor(query.search(15))).to(equal(Node(17)))
expect(query.successor(query.search(2))).to(equal(Node(5)))
expect(query.successor(query.search(5))).to(equal(tree.root))
expect(query.successor(tree.root)).to(equal(Node(15)))

Tree Predecessor

Similar in concept to a node successor, a node predecessor is the largest node less than the given node.

\begin{algorithm}
\caption{TreePredecessor}
\begin{algorithmic}
\INPUT The Node to start the search from.
\OUTPUT The Node with the next smallest key.
\PROCEDURE{TreePredecessor}{x}
\IF {\textit{x}.left $\neq$ \textsc{NIL}}
  \RETURN \textsc{TreeMaximum}(\textit{x}.right)
\ENDIF

\STATE \textit{y} $\gets$ \textit{x}.parent

\WHILE {\textit{y} $\neq$ \textsc{NIL} and \textit{x} = \textit{y}.left}
   \STATE \textit{x} $\gets$ \textit{y}
   \STATE \textit{y} $\gets$ \textit{y}.parent
\ENDWHILE
\RETURN \textit{y}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

def predecessor(self, node: Node) -> Node:
    """Returns the predecessor node

    Args:
     node: the node whose predecessor we want

    Returns:
     largest node smaller than given node
    """
    if node.left is not None:
        return self.max(node.left)
    predecessor = node.parent
    while predecessor is not None and node == predecessor.left:
        node, predecessor = predecessor, predecessor.parent
    return predecessor

tree = Tree(Node(10))
query = Query(tree)
expect(query.predecessor(tree.root)).to(be_none)
expect(query.predecessor(Node(5))).to(be_none)
tree.insert(Node(12))
expect(query.predecessor(query.search(12))).to(be(query.search(10)))

tree.insert(Node(8))
expect(query.predecessor(query.tree.root)).to(be(query.search(8)))
tree.insert(Node(4))
expect(query.predecessor(query.search(8))).to(equal(Node(4)))

Height

The height of the Binary Search Tree is the number of edges from the root of the tree to the furthest node. The algorithms we're looking at here don't use them but I'm going to use height to look at how the order you insert nodes in the tree affects the height.

@property
def height(self) -> int:
    """The length of the longest path starting at the root

    Returns:
     number of edges from root to furthest leaf
    """
    return self.tree_height(self.tree.root)

def tree_height(self, node: Node=None) -> int:
    """The length of the longest path starting at the node

    Args:
     the node to start the measurement from

    Returns:
     number of edges from root to furthest leaf
    """
    if node is None:
        return -1

    left = self.tree_height(node.left) + 1
    right = self.tree_height(node.right) + 1
    return max(left, right)

tree = Tree()
query = Query(tree)

expect(query.height).to(equal(-1))
tree.insert(Node(10))
expect(query.height).to(equal(0))
tree.insert(Node(8))
expect(query.height).to(equal(1))
tree.insert(Node(12))
expect(query.height).to(equal(1))
tree.insert(Node(4))
expect(query.height).to(equal(2))
tree.insert(Node(2))
expect(query.height).to(equal(3))

tree = Tree()
query = Query(tree)

n = 20
for key in range(n):
    tree.insert(Node(key))

expect(query.height).to(equal(n - 1))

Sources