'A'

{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Search Trees\n", "\n", "In this reading, we'll learn about how to use trees as an efficient way to search for data.\n", "\n", "By the end, you should be comfortable with the following terms:\n", "* binary tree\n", "* search\n", "* range query\n", "* binary search tree\n", "* balanced tree\n", "\n", "formatting..." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "application/javascript": [ "IPython.OutputArea.prototype._should_scroll = function(lines) {\n", " return false;\n", "}\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%javascript\n", "IPython.OutputArea.prototype._should_scroll = function(lines) {\n", " return false;\n", "}" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "scrolled": true }, "outputs": [], "source": [ "from graphviz import Graph, Digraph" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Binary Tree\n", "\n", "Below is a binary tree, cleaned up from last time.\n", "\n", "Remember that a tree is a directed graph. It has one root node (that is, a node without a parent). Every other node has a parent. Nodes without children are called leaves.\n", "\n", "This tree is a *binary tree* because each node has at most two children." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e0a0>" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Node:\n", " def __init__(self, val):\n", " self.val = val\n", " self.left = None\n", " self.right = None\n", " \n", " def to_graphviz(self, g=None):\n", " if g == None:\n", " g = Digraph()\n", " \n", " # draw self\n", " g.node(repr(self.val))\n", " \n", " for label, child in [(\"L\", self.left), (\"R\", self.right)]:\n", " if child != None:\n", " # draw child, recursively\n", " child.to_graphviz(g)\n", " \n", " # draw edge from self to child\n", " g.edge(repr(self.val), repr(child.val), label=label)\n", " return g\n", " \n", " def _repr_svg_(self):\n", " return self.to_graphviz()._repr_image_svg_xml()\n", " \n", "root = Node(\"A\")\n", "root.left = Node(\"B\")\n", "root.right = Node(\"C\")\n", "root.left.left = Node(\"Y\")\n", "root.left.right = Node(\"X\")\n", "root.right.right = Node(\"Z\")\n", "root" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Search\n", "\n", "What if we want to check whether a tree *contains* a value? We know it does if one of the following is true:\n", "\n", "1. the root has that value\n", "2. the left subtree contains that value\n", "3. the right subtree contains that value\n", "\n", "Let's write a recursive function, `contains`, to do this search. At each step, we'll display the subtree being searched." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "Is the root B?" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e0a0>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "Is the root B?" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e100>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.core.display import display, HTML\n", "\n", "def contains(node, target):\n", " if node == None:\n", " return False\n", "\n", " display(HTML(\"Is the root %s?\" % target))\n", " display(node)\n", "\n", " if node.val == target:\n", " return True\n", " return contains(node.left, target) or contains(node.right, target)\n", "\n", "contains(root, \"B\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Cool, we found the value in the second place we looked because we check left first. What if the data is deep on the right side? Worse, what if the thing we're searching for isn't even in the tree? Let's try that:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "Is the root M?" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e0a0>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "Is the root M?" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e100>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "Is the root M?" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e130>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "Is the root M?" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39ed60>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "Is the root M?" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e0d0>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "Is the root M?" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39ef10>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "False" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "contains(root, \"M\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Search Tree\n", "\n", "Ouch, that was slow. It would be great if we could determine that an entry isn't in the tree without needing to look at every entry.\n", "\n", "One way we can guarantee this is if every value in a left subtree is less than the value of the parent and every value in the right subtree is greater than the value of the parent.\n", "\n", "## Constructing a Search Tree\n", "\n", "Let's create a function for adding values that guarantees this." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "scrolled": true }, "outputs": [], "source": [ "# TODO: make this a method...\n", "def add(node, val):\n", " if node.val == val:\n", " return # no duplicates\n", " elif val < node.val:\n", " if node.left != None:\n", " add(node.left, val)\n", " else:\n", " node.left = Node(val)\n", " else:\n", " if node.right != None:\n", " add(node.right, val)\n", " else:\n", " node.right = Node(val)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "root = Node(\"C\")\n", "root" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "add(root, \"A\")\n", "root" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# duplicate shouldn't be added\n", "add(root, \"A\")\n", "root" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "add(root, \"B\")\n", "root" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "add(root, \"E\")\n", "root" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "add(root, \"D1\")\n", "root" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "scrolled": false }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "add(root, \"D2\")\n", "root" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "scrolled": false }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "add(root, \"F\")\n", "root" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Using a Search Tree\n", "\n", "Now that we've built a search tree, we can write a function for efficiently searching it. It's like the previous `contains` function, but now we only need to check one child instead of checking both each time." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "'Is the root D2?'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'Go Right'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'Is the root D2?'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39b220>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'Go Left'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'Is the root D2?'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39aaf0>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'Go Right'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'Is the root D2?'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39ab20>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def contains(node, target):\n", " if node == None:\n", " return False\n", "\n", " display(\"Is the root %s?\" % target)\n", " display(node)\n", "\n", " if node.val == target:\n", " return True\n", " \n", " if target < node.val:\n", " display(\"Go Left\")\n", " return contains(node.left, target)\n", " else:\n", " display(\"Go Right\")\n", " return contains(node.right, target)\n", "\n", "contains(root, \"D2\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Range Query\n", "\n", "For the previous lookups, using a Python set would probably do about as well. But what if we want get all the values in some range?\n", "\n", "We can write a similar function. But now, we'll sometimes need to search both sides (depending on the width of the range).\n", "\n", "Rather than returning found values, we can accumulate everything in a list." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "'Is the root C between D1 and D9'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'NO'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39e760>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'Is the root E between D1 and D9'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'NO'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39b220>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'Is the root D1 between D1 and D9'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'YES'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39aaf0>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'Is the root D2 between D1 and D9'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'YES'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d39ab20>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "['D1', 'D2']" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def range_query(node, lower, upper, results=None):\n", " if results == None:\n", " results = []\n", "\n", " if node == None:\n", " return results\n", " \n", " display(\"Is the root %s between %s and %s\" % (node.val, str(lower), str(upper)))\n", " if lower <= node.val <= upper:\n", " display(\"YES\")\n", " results.append(node.val)\n", " else:\n", " display(\"NO\")\n", " \n", " display(node)\n", "\n", " if lower < node.val:\n", " range_query(node.left, lower, upper, results)\n", " if upper > node.val:\n", " range_query(node.right, lower, upper, results)\n", "\n", " return results\n", "\n", "range_query(root, \"D1\", \"D9\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Balancing\n", "\n", "If the depth of all nodes are roughly equal, the time to check a values will be O(log N), which is pretty great! But the insertion order matters a lot. Let's consider these 8 numbers:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nums1 = list(range(20))\n", "nums1" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[17, 9, 4, 18, 12, 7, 0, 6, 11, 15, 16, 3, 8, 1, 14, 19, 5, 10, 2, 13]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from numpy import random\n", "\n", "nums2 = nums1[:] # shallow copy\n", "random.seed(320)\n", "random.shuffle(nums2)\n", "nums2" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "tree1 = Node(nums1[0])\n", "for num in nums1[1:]:\n", " add(tree1, num)\n", " \n", "tree2 = Node(nums2[0])\n", "for num in nums2[1:]:\n", " add(tree2, num)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d7f5340>" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# lookup with be very slow!\n", "tree1" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17d3bc8e0>" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# a bit better!\n", "tree2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Balance\n", "\n", "The second tree is definitely a lot more balanced than the first. If we really want to measure this, we would like to identify openings that are shallower than the deepest nodes." ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(2, 6)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def nearest_open(node):\n", " if node is None:\n", " return 0\n", " return min(nearest_open(node.left), nearest_open(node.right)) + 1\n", "\n", "def max_depth(node):\n", " if node is None or (node.left is None and node.right is None):\n", " return 0\n", " return 1 + max(max_depth(node.left), max_depth(node.right))\n", "\n", "nearest_open(tree2), max_depth(tree2)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [], "source": [ "def is_balanced(node):\n", " return nearest_open(node) >= max_depth(node)" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17e0a83a0>" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# test is_balanced\n", "t = Node(\"B\")\n", "t.left = Node(\"A\")\n", "t.right = Node(\"C\")\n", "t" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17e0a83a0>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t.right.right = Node(\"D\")\n", "display(t)\n", "is_balanced(t)" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "<__main__.Node at 0x7fd17e0a83a0>" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "False" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t.right.right.right = Node(\"E\")\n", "display(t)\n", "is_balanced(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Conclusion\n", "\n", "In this reading, we have seen that a binary tree is a BST (Binary Search Tree) if all the left descendents of a node have lesser values than the node, and all the right descendents have greater values. Binary search trees allow us to find values and ranges of values without checking every node.\n", "\n", "In a perfectly balanced tree, looking for a single item is O(log N). A tree if balanced if there are no nodes that could be moved closer to the root.\n", "\n", "Randomizing insertion order can improve balance. There are also algorithms (not covered) to rearrange trees as values are inserted, maintaining balance (perhaps within some tolerance)." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.6" } }, "nbformat": 4, "nbformat_minor": 2 }