6. Trees and Tree Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6. Trees and Tree Algorithms\n",
    "## 6.1. Objectives\n",
    "\n",
    "* To understand what a tree data structure is and how it is used.\n",
    "* To see how trees can be used to implement a map data structure.\n",
    "* To implement trees using a list.\n",
    "* To implement trees using classes and references.\n",
    "* To implement trees as a recursive data structure.\n",
    "* To implement a priority queue using a heap."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.2. Examples of Trees\n",
    "\n",
    "Now that we have studied linear data structures like stacks and queues and have some experience with recursion, we will look at a common data structure called the tree. Trees are used in many areas of computer science, including operating systems, graphics, database systems, and computer networking. Tree data structures have many things in common with their botanical cousins. A tree data structure has a root, branches, and leaves. The difference between a tree in nature and a tree in computer science is that a tree data structure has its root at the top and its leaves on the bottom.\n",
    "\n",
    "Before we begin our study of tree data structures, let’s look at a few common examples. Our first example of a tree is a classification tree from biology. Figure 1 shows an example of the biological classification of some animals. From this simple example, we can learn about several properties of trees. The first property this example demonstrates is that trees are hierarchical. By hierarchical, we mean that trees are structured in layers with the more general things near the top and the more specific things near the bottom. The top of the hierarchy is the Kingdom, the next layer of the tree (the “children” of the layer above) is the Phylum, then the Class, and so on. However, no matter how deep we go in the classification tree, all the organisms are still animals.\n",
    "\n",
    "<img src=\"images/biology.png\" alt=\"Drawing\" style=\"width: 500px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that you can start at the top of the tree and follow a path made of circles and arrows all the way to the bottom. At each level of the tree we might ask ourselves a question and then follow the path that agrees with our answer. For example we might ask, “Is this animal a Chordate or an Arthropod?” If the answer is “Chordate” then we follow that path and ask, “Is this Chordate a Mammal?” If not, we are stuck (but only in this simplified example). When we are at the Mammal level we ask, “Is this Mammal a Primate or a Carnivore?” We can keep following paths until we get to the very bottom of the tree where we have the common name.\n",
    "\n",
    "A second property of trees is that all of the children of one node are independent of the children of another node. For example, the Genus Felis has the children Domestica and Leo. The Genus Musca also has a child named Domestica, but it is a different node and is independent of the Domestica child of Felis. This means that we can change the node that is the child of Musca without affecting the child of Felis.\n",
    "\n",
    "A third property is that each leaf node is unique. We can specify a path from the root of the tree to a leaf that uniquely identifies each species in the animal kingdom; for example, Animalia → Chordate → Mammal → Carnivora → Felidae → Felis → Domestica.\n",
    "\n",
    "Another example of a tree structure that you probably use every day is a file system. In a file system, directories, or folders, are structured as a tree. Figure 2 illustrates a small part of a Unix file system hierarchy.\n",
    "\n",
    "![](images/directory.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "The file system tree has much in common with the biological classification tree. You can follow a path from the root to any directory. That path will uniquely identify that subdirectory (and all the files in it). Another important property of trees, derived from their hierarchical nature, is that you can move entire sections of a tree (called a subtree) to a different position in the tree without affecting the lower levels of the hierarchy. For example, we could take the entire subtree staring with `/etc/`, detach `etc/` from the root and reattach it under `usr/`. This would change the unique pathname to httpd from `/etc/httpd` to `/usr/etc/httpd`, but would not affect the contents or any children of the httpd directory.\n",
    "\n",
    "A final example of a tree is a web page. The following is an example of a simple web page written using HTML. Figure 3 shows the tree that corresponds to each of the HTML tags used to create the page."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "<!DOCTYPE html>\n",
    "<html lang=\"en\">\n",
    "<head>\n",
    "    <meta charset=\"utf-8\">\n",
    "    <title>simple</title>\n",
    "</head>\n",
    "<body>\n",
    "<h1>A simple web page</h1>\n",
    "<ul>\n",
    "    <li>List item one</li>\n",
    "    <li>List item two</li>\n",
    "</ul>\n",
    "<h2><a href=\"http://nvcc.edu\">Northern Virginia Community College</a><h2>\n",
    "</body>\n",
    "</html>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/htmltree.png)\n",
    "\n",
    "The HTML source code and the tree accompanying the source illustrate another hierarchy. Notice that each level of the tree corresponds to a level of nesting inside the HTML tags. The first tag in the source is `<html>` and the last is `</html>` All the rest of the tags in the page are inside the pair. If you check, you will see that this nesting property is true at all levels of the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.3. Vocabulary and Definitions\n",
    "\n",
    "Now that we have looked at examples of trees, we will formally define a tree and its components.\n",
    "\n",
    "**Node**\n",
    "\n",
    "    A node is a fundamental part of a tree. It can have a name, which we call the “key.” A node may also have additional information. We call this additional information the “payload.” While the payload information is not central to many tree algorithms, it is often critical in applications that make use of trees.\n",
    "    \n",
    "**Edge**\n",
    "\n",
    "    An edge is another fundamental part of a tree. An edge connects two nodes to show that there is a relationship between them. Every node (except the root) is connected by exactly one incoming edge from another node. Each node may have several outgoing edges.\n",
    "    \n",
    "**Root**\n",
    "\n",
    "    The root of the tree is the only node in the tree that has no incoming edges. In Figure Figure 2, / is the root of the tree.\n",
    "    \n",
    "**Path**\n",
    "\n",
    "    A path is an ordered list of nodes that are connected by edges. For example, Mammal → Carnivora → Felidae → Felis → Domestica is a path.\n",
    "    \n",
    "**Children**\n",
    "\n",
    "    The set of nodes c\n",
    "    that have incoming edges from the same node to are said to be the children of that node. In Figure Figure 2, nodes log/, spool/, and yp/ are the children of node var/.\n",
    "    \n",
    "**Parent**\n",
    "\n",
    "    A node is the parent of all the nodes it connects to with outgoing edges. In Figure 2 the node var/ is the parent of nodes log/, spool/, and yp/.\n",
    "    \n",
    "**Sibling**\n",
    "\n",
    "    Nodes in the tree that are children of the same parent are said to be siblings. The nodes etc/ and usr/ are siblings in the filesystem tree.\n",
    "    \n",
    "**Subtree**\n",
    "\n",
    "    A subtree is a set of nodes and edges comprised of a parent and all the descendants of that parent.\n",
    "    \n",
    "**Leaf Node**\n",
    "\n",
    "    A leaf node is a node that has no children. For example, Human and Chimpanzee are leaf nodes in Figure 1.\n",
    "    \n",
    "**Level**\n",
    "    The level of a node n is the number of edges on the path from the root node to n\n",
    "\n",
    "    . For example, the level of the Felis node in Figure 1 is five. By definition, the level of the root node is zero.\n",
    "Height\n",
    "    The height of a tree is equal to the maximum level of any node in the tree. The height of the tree in Figure 2 is two.\n",
    "\n",
    "With the basic vocabulary now defined, we can move on to a formal definition of a tree. In fact, we will provide two definitions of a tree. One definition involves nodes and edges. The second definition, which will prove to be very useful, is a recursive definition.\n",
    "\n",
    "**Definition One**: A tree consists of a set of nodes and a set of edges that connect pairs of nodes. A tree has the following properties:\n",
    "\n",
    "* One node of the tree is designated as the root node.\n",
    "* Every node `n`, except the root node, is connected by an edge from exactly one other node `p`, where `p` is the parent of `n`.\n",
    "* A unique path traverses from the root to each node.\n",
    "* If each node in the tree has a maximum of two children, we say that the tree is a binary tree.\n",
    "\n",
    "Figure 3 illustrates a tree that fits definition one. The arrowheads on the edges indicate the direction of the connection.\n",
    "\n",
    "![](images/treedef1.png)\n",
    "\n",
    "**Definition Two**: A tree is either empty or consists of a root and zero or more subtrees, each of which is also a tree. The root of each subtree is connected to the root of the parent tree by an edge. Figure 4 illustrates this recursive definition of a tree. Using the recursive definition of a tree, we know that the tree in Figure 4 has at least four nodes, since each of the triangles representing a subtree must have a root. It may have many more nodes than that, but we do not know unless we look deeper into the tree.\n",
    "\n",
    "![](images/TreeDefRecursive.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.4. List of Lists Representation\n",
    "\n",
    "In a tree represented by a list of lists, we will begin with Python’s list data structure and write the functions defined above. Although writing the interface as a set of operations on a list is a bit different from the other abstract data types we have implemented, it is interesting to do so because it provides us with a simple recursive data structure that we can look at and examine directly. In a list of lists tree, we will store the value of the root node as the first element of the list. The second element of the list will itself be a list that represents the left subtree. The third element of the list will be another list that represents the right subtree. To illustrate this storage technique, let’s look at an example. Figure 1 shows a simple tree and the corresponding list implementation.\n",
    "\n",
    "![](images/smalltree.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_tree = ['a',   # root\n",
    "          ['b',  # left subtree\n",
    "          ['d', [], []],\n",
    "          ['e', [], []] ],\n",
    "          ['c',  # right subtree\n",
    "          ['f', [], []],\n",
    "          [] ]\n",
    "          ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that we can access subtrees of the list using standard list indexing. The root of the tree is `myTree[0]`, the left subtree of the root is `myTree[1]`, and the right subtree is `myTree[2]`. ActiveCode 1 illustrates creating a simple tree using a list. Once the tree is constructed, we can access the root and the left and right subtrees. One very nice property of this list of lists approach is that the structure of a list representing a subtree adheres to the structure defined for a tree; the structure itself is recursive! A subtree that has a root value and two empty lists is a leaf node. Another nice feature of the list of lists approach is that it generalizes to a tree that has many subtrees. In the case where the tree is more than a binary tree, another subtree is just another list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]\n",
      "left subtree =  ['b', ['d', [], []], ['e', [], []]]\n",
      "root =  a\n",
      "right subtree =  ['c', ['f', [], []], []]\n"
     ]
    }
   ],
   "source": [
    "my_tree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]\n",
    "print(my_tree)\n",
    "print('left subtree = ', my_tree[1])\n",
    "print('root = ', my_tree[0])\n",
    "print('right subtree = ', my_tree[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let’s formalize this definition of the tree data structure by providing some functions that make it easy for us to use lists as trees. Note that we are not going to define a binary tree class. The functions we will write will just help us manipulate a standard list as though we are working with a tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_tree(r):\n",
    "    return [r, [], []]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `binary_tree` function simply constructs a list with a root node and two empty sublists for the children. To add a left subtree to the root of a tree, we need to insert a new list into the second position of the root list. We must be careful. If the list already has something in the second position, we need to keep track of it and push it down the tree as the left child of the list we are adding. Listing 1 shows the Python code for inserting a left child."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_left(root, new_branch):\n",
    "    t = root.pop(1)\n",
    "    if len(t) > 1:\n",
    "        root.insert(1, [new_branch, t, []])\n",
    "    else:\n",
    "        root.insert(1,[new_branch, [], []])\n",
    "    return root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that to insert a left child, we first obtain the (possibly empty) list that corresponds to the current left child. We then add the new left child, installing the old left child as the left child of the new one. This allows us to splice a new node into the tree at any position. The code for `insert_right` is similar to `insert_left` and is shown in Listing 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_right(root, new_branch):\n",
    "    t = root.pop(2)\n",
    "    if len(t) > 1:\n",
    "        root.insert(2, [new_branch, [], t])\n",
    "    else:\n",
    "        root.insert(2, [new_branch, [], []])\n",
    "    return root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To round out this set of tree-making functions(see Listing 3), let’s write a couple of access functions for getting and setting the root value, as well as getting the left or right subtrees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_root_val(root):\n",
    "    return root[0]\n",
    "\n",
    "def set_root_val(root, new_val):\n",
    "    root[0] = new_val\n",
    "\n",
    "def get_left_child(root):\n",
    "    return root[1]\n",
    "\n",
    "def get_right_child(root):\n",
    "    return root[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ActiveCode 2 exercises the tree functions we have just written. You should try it out for yourself. One of the exercises asks you to draw the tree structure resulting from this set of calls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, [4, [], []], []]\n",
      "[3, [9, [4, [], []], []], [7, [], [6, [], []]]]\n",
      "[3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]\n",
      "[6, [], []]\n"
     ]
    }
   ],
   "source": [
    "r = binary_tree(3)\n",
    "insert_left(r, 4)\n",
    "insert_left(r, 5)\n",
    "insert_right(r, 6)\n",
    "insert_right(r, 7)\n",
    "l = get_left_child(r)\n",
    "print(l)\n",
    "\n",
    "set_root_val(l, 9)\n",
    "print(r)\n",
    "insert_left(l, 11)\n",
    "print(r)\n",
    "print(get_right_child(get_right_child(r)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">Self Check\n",
    "\n",
    ">Q-26: Given the following statments:\n",
    ">```\n",
    "x = BinaryTree('a')\n",
    "insert_left(x,'b')\n",
    "insert_right(x,'c')\n",
    "insert_right(get_right_child(x),'d')\n",
    "insert_left(get_right_child(get_right_child(x)),'e')\n",
    ">```\n",
    ">Which of the answers is the correct representation of the tree?\n",
    ">    * A. `['a', ['b', [], []], ['c', [], ['d', [], []]]]`\n",
    ">    * B. `['a', ['c', [], ['d', ['e', [], []], []]], ['b', [], []]]`\n",
    ">    * C. `['a', ['b', [], []], ['c', [], ['d', ['e', [], []], []]]]`\n",
    ">    * D. `['a', ['b', [], ['d', ['e', [], []], []]], ['c', [], []]]`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.5. Nodes and References\n",
    "\n",
    "Our second method to represent a tree uses nodes and references. In this case we will define a class that has attributes for the root value, as well as the left and right subtrees. Since this representation more closely follows the object-oriented programming paradigm, we will continue to use this representation for the remainder of the chapter.\n",
    "\n",
    "Using nodes and references, we might think of the tree as being structured like the one shown in Figure 2.\n",
    "\n",
    "![](images/treerecs.png)\n",
    "\n",
    "We will start out with a simple class definition for the nodes and references approach as shown in Listing 4. The important thing to remember about this representation is that the attributes `left` and `right` will become references to other instances of the `BinaryTree` class. For example, when we insert a new left child into the tree we create another instance of `BinaryTree` and modify `self.leftChild` in the root to reference the new tree.\n",
    "\n",
    "**Listing 4**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self,rootObj):\n",
    "        self.key = rootObj\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that in Listing 4, the constructor function expects to get some kind of object to store in the root. Just like you can store any object you like in a list, the root object of a tree can be a reference to any object. For our early examples, we will store the name of the node as the root value. Using nodes and references to represent the tree in Figure 2, we would create six instances of the BinaryTree class.\n",
    "\n",
    "Next let’s look at the functions we need to build the tree beyond the root node. To add a left child to the tree, we will create a new binary tree object and set the `left` attribute of the root to refer to this new object. The code for `insertLeft` is shown in Listing 5.\n",
    "\n",
    "**Listing 5**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertLeft(self,newNode):\n",
    "    if self.leftChild == None:\n",
    "        self.leftChild = BinaryTree(newNode)\n",
    "    else:\n",
    "        t = BinaryTree(newNode)\n",
    "        t.leftChild = self.leftChild\n",
    "        self.leftChild = t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We must consider two cases for insertion. The first case is characterized by a node with no existing left child. When there is no left child, simply add a node to the tree. The second case is characterized by a node with an existing left child. In the second case, we insert a node and push the existing child down one level in the tree. The second case is handled by the else statement on line 4 of Listing 5.\n",
    "\n",
    "The code for insertRight must consider a symmetric set of cases. There will either be no right child, or we must insert the node between the root and an existing right child. The insertion code is shown in Listing 6.\n",
    "\n",
    "**Listing 6**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertRight(self,newNode):\n",
    "    if self.rightChild == None:\n",
    "        self.rightChild = BinaryTree(newNode)\n",
    "    else:\n",
    "        t = BinaryTree(newNode)\n",
    "        t.rightChild = self.rightChild\n",
    "        self.rightChild = t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To round out the definition for a simple binary tree data structure, we will write accessor methods (see Listing 7) for the left and right children, as well as the root values.\n",
    "\n",
    "**Listing 7**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getRightChild(self):\n",
    "    return self.rightChild\n",
    "\n",
    "def getLeftChild(self):\n",
    "    return self.leftChild\n",
    "\n",
    "def setRootVal(self,obj):\n",
    "    self.key = obj\n",
    "\n",
    "def getRootVal(self):\n",
    "    return self.key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have all the pieces to create and manipulate a binary tree, let’s use them to check on the structure a bit more. Let’s make a simple tree with node a as the root, and add nodes b and c as children. ActiveCode 1 creates the tree and looks at the some of the values stored in `key`, `left`, and `right`. Notice that both the left and right children of the root are themselves distinct instances of the `BinaryTree` class. As we said in our original recursive definition for a tree, this allows us to treat any child of a binary tree as a binary tree itself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "None\n",
      "<__main__.BinaryTree object at 0x7f7e4897a490>\n",
      "b\n",
      "<__main__.BinaryTree object at 0x7f7e48137280>\n",
      "c\n",
      "hello\n"
     ]
    }
   ],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self,rootObj):\n",
    "        self.key = rootObj\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None\n",
    "\n",
    "    def insertLeft(self,newNode):\n",
    "        if self.leftChild == None:\n",
    "            self.leftChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.leftChild = self.leftChild\n",
    "            self.leftChild = t\n",
    "\n",
    "    def insertRight(self,newNode):\n",
    "        if self.rightChild == None:\n",
    "            self.rightChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.rightChild = self.rightChild\n",
    "            self.rightChild = t\n",
    "\n",
    "\n",
    "    def getRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    def getLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    def setRootVal(self,obj):\n",
    "        self.key = obj\n",
    "\n",
    "    def getRootVal(self):\n",
    "        return self.key\n",
    "\n",
    "\n",
    "r = BinaryTree('a')\n",
    "print(r.getRootVal())\n",
    "print(r.getLeftChild())\n",
    "r.insertLeft('b')\n",
    "print(r.getLeftChild())\n",
    "print(r.getLeftChild().getRootVal())\n",
    "r.insertRight('c')\n",
    "print(r.getRightChild())\n",
    "print(r.getRightChild().getRootVal())\n",
    "r.getRightChild().setRootVal('hello')\n",
    "print(r.getRightChild().getRootVal())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.6. Parse Tree\n",
    "\n",
    "With the implementation of our tree data structure complete, we now look at an example of how a tree can be used to solve some real problems. In this section we will look at parse trees. Parse trees can be used to represent real-world constructions like sentences or mathematical expressions.\n",
    "\n",
    "![](images/nlParse.png)\n",
    "Figure 1 shows the hierarchical structure of a simple sentence. Representing a sentence as a tree structure allows us to work with the individual parts of the sentence by using subtrees."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/meParse.png)\n",
    "We can also represent a mathematical expression such as $((7+3)∗(5−2))$ as a parse tree, as shown in Figure 2. We have already looked at fully parenthesized expressions, so what do we know about this expression? We know that multiplication has a higher precedence than either addition or subtraction. Because of the parentheses, we know that before we can do the multiplication we must evaluate the parenthesized addition and subtraction expressions. The hierarchy of the tree helps us understand the order of evaluation for the whole expression. Before we can evaluate the top-level multiplication, we must evaluate the addition and the subtraction in the subtrees. The addition, which is the left subtree, evaluates to 10. The subtraction, which is the right subtree, evaluates to 3. Using the hierarchical structure of trees, we can simply replace an entire subtree with one node once we have evaluated the expressions in the children. Applying this replacement procedure gives us the simplified tree shown in Figure 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/meSimple.png)\n",
    "In the rest of this section we are going to examine parse trees in more detail. In particular we will look at\n",
    "\n",
    "* How to build a parse tree from a fully parenthesized mathematical expression.\n",
    "* How to evaluate the expression stored in a parse tree.\n",
    "* How to recover the original mathematical expression from a parse tree.\n",
    "\n",
    "The first step in building a parse tree is to break up the expression string into a list of tokens. There are four different kinds of tokens to consider: left parentheses, right parentheses, operators, and operands. We know that whenever we read a left parenthesis we are starting a new expression, and hence we should create a new tree to correspond to that expression. Conversely, whenever we read a right parenthesis, we have finished an expression. We also know that operands are going to be leaf nodes and children of their operators. Finally, we know that every operator is going to have both a left and a right child.\n",
    "\n",
    "Using the information from above we can define four rules as follows:\n",
    "\n",
    "1. If the current token is a `'('`, add a new node as the left child of the current node, and descend to the left child.\n",
    "2. If the current token is in the list `['+','-','/','*']`, set the root value of the current node to the operator represented by the current token. Add a new node as the right child of the current node and descend to the right child.\n",
    "3. If the current token is a number, set the root value of the current node to the number and return to the parent.\n",
    "4. If the current token is a `')'`, go to the parent of the current node.\n",
    "\n",
    "Before writing the Python code, let’s look at an example of the rules outlined above in action. We will use the expression $(3+(4∗5)$)\n",
    ". We will parse this expression into the following list of character tokens `['(', '3', '+', '(', '4', '*', '5' ,')',')']`. Initially we will start out with a parse tree that consists of an empty root node. Figure 4 illustrates the structure and contents of the parse tree, as each new token is processed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/combine_images_1.jpg)\n",
    "![](images/combine_images_2.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using Figure 4, let’s walk through the example step by step:\n",
    "\n",
    "   1. Create an empty tree.\n",
    "   2. Read ( as the first token. By rule 1, create a new node as the left child of the root. Make the current node this new child.\n",
    "   3. Read 3 as the next token. By rule 3, set the root value of the current node to 3 and go back up the tree to the parent.\n",
    "   4. Read + as the next token. By rule 2, set the root value of the current node to + and add a new node as the right child. The new right child becomes the current node.\n",
    "   5. Read a ( as the next token. By rule 1, create a new node as the left child of the current node. The new left child becomes the current node.\n",
    "   6. Read a 4 as the next token. By rule 3, set the value of the current node to 4. Make the parent of 4 the current node.\n",
    "   7. Read * as the next token. By rule 2, set the root value of the current node to * and create a new right child. The new right child becomes the current node.\n",
    "   8. Read 5 as the next token. By rule 3, set the root value of the current node to 5. Make the parent of 5 the current node.\n",
    "   9. Read ) as the next token. By rule 4 we make the parent of * the current node.\n",
    "   10. Read ) as the next token. By rule 4 we make the parent of + the current node. At this point there is no parent for + so we are done.\n",
    "\n",
    "From the example above, it is clear that we need to keep track of the current node as well as the parent of the current node. The tree interface provides us with a way to get children of a node, through the `getLeftChild` and `getRightChild` methods, but how can we keep track of the parent? A simple solution to keeping track of parents as we traverse the tree is to use a stack. Whenever we want to descend to a child of the current node, we first push the current node on the stack. When we want to return to the parent of the current node, we pop the parent off the stack.\n",
    "\n",
    "Using the rules described above, along with the `Stack` and `BinaryTree` operations, we are now ready to write a Python function to create a parse tree. The code for our parse tree builder is presented in ActiveCode 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "5\n",
      "+\n",
      "3\n",
      "*\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "from pythonds.trees.binaryTree import BinaryTree\n",
    "\n",
    "def buildParseTree(fpexp):\n",
    "    fplist = fpexp.split()\n",
    "    pStack = Stack()\n",
    "    eTree = BinaryTree('')\n",
    "    pStack.push(eTree)\n",
    "    currentTree = eTree\n",
    "\n",
    "    for i in fplist:\n",
    "        if i == '(':\n",
    "            currentTree.insertLeft('')\n",
    "            pStack.push(currentTree)\n",
    "            currentTree = currentTree.getLeftChild()\n",
    "\n",
    "        elif i in ['+', '-', '*', '/']:\n",
    "            currentTree.setRootVal(i)\n",
    "            currentTree.insertRight('')\n",
    "            pStack.push(currentTree)\n",
    "            currentTree = currentTree.getRightChild()\n",
    "\n",
    "        elif i == ')':\n",
    "            currentTree = pStack.pop()\n",
    "\n",
    "        elif i not in ['+', '-', '*', '/', ')']:\n",
    "            try:\n",
    "                currentTree.setRootVal(int(i))\n",
    "                parent = pStack.pop()\n",
    "                currentTree = parent\n",
    "\n",
    "            except ValueError:\n",
    "                raise ValueError(\"token '{}' is not a valid integer\".format(i))\n",
    "\n",
    "    return eTree\n",
    "\n",
    "pt = buildParseTree(\"( ( 10 + 5 ) * 3 )\")\n",
    "pt.postorder()  #defined and explained in the next section"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The four rules for building a parse tree are coded as the first four clauses of the if statement on lines 12, 17, 23, and 26 of ActiveCode 1. In each case you can see that the code implements the rule, as described above, with a few calls to the `BinaryTree` or `Stack` methods. The only error checking we do in this function is in the else clause where a `ValueError` exception will be raised if we get a token from the list that we do not recognize.\n",
    "\n",
    "Now that we have built a parse tree, what can we do with it? As a first example, we will write a function to evaluate the parse tree, returning the numerical result. To write this function, we will make use of the hierarchical nature of the tree. Look back at Figure 2. Recall that we can replace the original tree with the simplified tree shown in Figure 3. This suggests that we can write an algorithm that evaluates a parse tree by recursively evaluating each subtree.\n",
    "\n",
    "As we have done with past recursive algorithms, we will begin the design for the recursive evaluation function by identifying the base case. A natural base case for recursive algorithms that operate on trees is to check for a leaf node. In a parse tree, the leaf nodes will always be operands. Since numerical objects like integers and floating points require no further interpretation, the `evaluate` function can simply return the value stored in the leaf node. The recursive step that moves the function toward the base case is to call `evaluate` on both the left and the right children of the current node. The recursive call effectively moves us down the tree, toward a leaf node.\n",
    "\n",
    "To put the results of the two recursive calls together, we can simply apply the operator stored in the parent node to the results returned from evaluating both children. In the example from Figure 3 we see that the two children of the root evaluate to themselves, namely 10 and 3. Applying the multiplication operator gives us a final result of 30.\n",
    "\n",
    "The code for a recursive `evaluate` function is shown in Listing 1. First, we obtain references to the left and the right children of the current node. If both the left and right children evaluate to `None`, then we know that the current node is really a leaf node. This check is on line 7. If the current node is not a leaf node, look up the operator in the current node and apply it to the results from recursively evaluating the left and right children.\n",
    "\n",
    "To implement the arithmetic, we use a dictionary with the keys `'+', '-', '*'`, and `'/'`. The values stored in the dictionary are functions from Python’s operator module. The operator module provides us with the functional versions of many commonly used operators. When we look up an operator in the dictionary, the corresponding function object is retrieved. Since the retrieved object is a function, we can call it in the usual way `function(param1,param2)`. So the lookup `opers['+'](2,2)` is equivalent to `operator.add(2,2)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate(parseTree):\n",
    "    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}\n",
    "\n",
    "    leftC = parseTree.getLeftChild()\n",
    "    rightC = parseTree.getRightChild()\n",
    "\n",
    "    if leftC and rightC:\n",
    "        fn = opers[parseTree.getRootVal()]\n",
    "        return fn(evaluate(leftC),evaluate(rightC))\n",
    "    else:\n",
    "        return parseTree.getRootVal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we will trace the `evaluate` function on the parse tree we created in Figure 4. When we first call `evaluate`, we pass the root of the entire tree as the parameter `parseTree`. Then we obtain references to the left and right children to make sure they exist. The recursive call takes place on line 9. We begin by looking up the operator in the root of the tree, which is `'+'`. The `'+'` operator maps to the `operator.add` function call, which takes two parameters. As usual for a Python function call, the first thing Python does is to evaluate the parameters that are passed to the function. In this case both parameters are recursive function calls to our evaluate function. Using left-to-right evaluation, the first recursive call goes to the left. In the first recursive call the evaluate function is given the left subtree. We find that the node has no left or right children, so we are in a leaf node. When we are in a leaf node we just return the value stored in the leaf node as the result of the evaluation. In this case we return the integer 3.\n",
    "\n",
    "At this point we have one parameter evaluated for our top-level call to `operator.add`. But we are not done yet. Continuing the left-to-right evaluation of the parameters, we now make a recursive call to evaluate the right child of the root. We find that the node has both a left and a right child so we look up the operator stored in this node, `'*'`, and call this function using the left and right children as the parameters. At this point you can see that both recursive calls will be to leaf nodes, which will evaluate to the integers four and five respectively. With the two parameters evaluated, we return the result of `operator.mul(4,5)`. At this point we have evaluated the operands for the top level `'+'` operator and all that is left to do is finish the call to `operator.add(3,20)`. The result of the evaluation of the entire expression tree for $(3+(4∗5)$)\n",
    "is 23."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.7. Tree Traversals\n",
    "Now that we have examined the basic functionality of our tree data structure, it is time to look at some additional usage patterns for trees. These usage patterns can be divided into the three ways that we access the nodes of the tree. There are three commonly used patterns to visit all the nodes in a tree. The difference between these patterns is the order in which each node is visited. We call this visitation of the nodes a “*traversal*” The three traversals we will look at are called **preorder**, **inorder**, and **postorder**. Let’s start out by defining these three traversals more carefully, then look at some examples where these patterns are useful."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**preorder**\n",
    "\n",
    "In a preorder traversal, we visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree.\n",
    "\n",
    "**inorder**\n",
    "\n",
    "In an inorder traversal, we recursively do an inorder traversal on the left subtree, visit the root node, and finally do a recursive inorder traversal of the right subtree.\n",
    "\n",
    "**postorder**\n",
    "\n",
    "In a postorder traversal, we recursively do a postorder traversal of the left subtree and the right subtree followed by a visit to the root node. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let’s look at some examples that illustrate each of these three kinds of traversals. First let’s look at the preorder traversal. As an example of a tree to traverse, we will represent this book as a tree. The book is the root of the tree, and each chapter is a child of the root. Each section within a chapter is a child of the chapter, and each subsection is a child of its section, and so on. Figure 5 shows a limited version of a book with only two chapters. Note that the traversal algorithm works for trees with any number of children, but we will stick with binary trees for now.\n",
    "\n",
    "![](images/booktree.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose that you wanted to read this book from front to back. The preorder traversal gives you exactly that ordering. Starting at the root of the tree (the Book node) we will follow the preorder traversal instructions. We recursively call `preorder` on the left child, in this case Chapter1. We again recursively call preorder on the left child to get to Section 1.1. Since Section 1.1 has no children, we do not make any additional recursive calls. When we are finished with Section 1.1, we move up the tree to Chapter 1. At this point we still need to visit the right subtree of Chapter 1, which is Section 1.2. As before we visit the left subtree, which brings us to Section 1.2.1, then we visit the node for Section 1.2.2. With Section 1.2 finished, we return to Chapter 1. Then we return to the Book node and follow the same procedure for Chapter 2.\n",
    "\n",
    "The code for writing tree traversals is surprisingly elegant, largely because the traversals are written recursively. Listing 2 shows the Python code for a preorder traversal of a binary tree.\n",
    "\n",
    "You may wonder, what is the best way to write an algorithm like preorder traversal? Should it be a function that simply uses a tree as a data structure, or should it be a method of the tree data structure itself? Listing 2 shows a version of the preorder traversal written as an external function that takes a binary tree as a parameter. The external function is particularly elegant because our base case is simply to check if the tree exists. If the tree parameter is `None`, then the function returns without taking any action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preorder(tree):\n",
    "    if tree:\n",
    "        print(tree.getRootVal())\n",
    "        preorder(tree.getLeftChild())\n",
    "        preorder(tree.getRightChild())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also implement `preorder` as a method of the `BinaryTree` class. The code for implementing `preorder` as an internal method is shown in Listing 3. Notice what happens when we move the code from internal to external. In general, we just replace `tree` with `self`. However, we also need to modify the base case. The internal method must check for the existence of the left and the right children before making the recursive call to `preorder`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preorder(self):\n",
    "    print(self.key)\n",
    "    if self.leftChild:\n",
    "        self.leftChild.preorder()\n",
    "    if self.rightChild:\n",
    "        self.rightChild.preorder()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which of these two ways to implement `preorder` is best? The answer is that implementing `preorder` as an external function is probably better in this case. The reason is that you very rarely want to just traverse the tree. In most cases you are going to want to accomplish something else while using one of the basic traversal patterns. In fact, we will see in the next example that the `postorder` traversal pattern follows very closely with the code we wrote earlier to evaluate a parse tree. Therefore we will write the rest of the traversals as external functions.\n",
    "\n",
    "The algorithm for the `postorder` traversal, shown in Listing 4, is nearly identical to `preorder` except that we move the call to print to the end of the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def postorder(tree):\n",
    "    if tree != None:\n",
    "        postorder(tree.getLeftChild())\n",
    "        postorder(tree.getRightChild())\n",
    "        print(tree.getRootVal())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have already seen a common use for the postorder traversal, namely evaluating a parse tree. Look back at Listing 1 again. What we are doing is evaluating the left subtree, evaluating the right subtree, and combining them in the root through the function call to an operator. Assume that our binary tree is going to store only expression tree data. Let’s rewrite the evaluation function, but model it even more closely on the `postorder` code in Listing 4 (see Listing 5)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def postordereval(tree):\n",
    "    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}\n",
    "    res1 = None\n",
    "    res2 = None\n",
    "    if tree:\n",
    "        res1 = postordereval(tree.getLeftChild())\n",
    "        res2 = postordereval(tree.getRightChild())\n",
    "        if res1 and res2:\n",
    "            return opers[tree.getRootVal()](res1,res2)\n",
    "        else:\n",
    "            return tree.getRootVal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the form in Listing 4 is the same as the form in Listing 5, except that instead of printing the key at the end of the function, we return it. This allows us to save the values returned from the recursive calls in lines 6 and 7. We then use these saved values along with the operator on line 9.\n",
    "\n",
    "The final traversal we will look at in this section is the inorder traversal. In the inorder traversal we visit the left subtree, followed by the root, and finally the right subtree. Listing 6 shows our code for the inorder traversal. Notice that in all three of the traversal functions we are simply changing the position of the `print` statement with respect to the two recursive function calls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inorder(tree):\n",
    "    if tree != None:\n",
    "        inorder(tree.getLeftChild())\n",
    "        print(tree.getRootVal())\n",
    "        inorder(tree.getRightChild())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we perform a simple inorder traversal of a parse tree we get our original expression back, without any parentheses. Let’s modify the basic inorder algorithm to allow us to recover the fully parenthesized version of the expression. The only modifications we will make to the basic template are as follows: print a left parenthesis before the recursive call to the left subtree, and print a right parenthesis after the recursive call to the right subtree. The modified code is shown in Listing 7."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printexp(tree):\n",
    "    sVal = \"\"\n",
    "    if tree:\n",
    "        sVal = '(' + printexp(tree.getLeftChild())\n",
    "        sVal = sVal + str(tree.getRootVal())\n",
    "        sVal = sVal + printexp(tree.getRightChild())+')'\n",
    "    return sVal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the `printexp` function as we have implemented it puts parentheses around each number. While not incorrect, the parentheses are clearly not needed. In the exercises at the end of this chapter you are asked to modify the `printexp` function to remove this set of parentheses."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.8. Priority Queues with Binary Heaps\n",
    "\n",
    "In earlier sections you learned about the first-in first-out data structure called a queue. One important variation of a queue is called a **priority queue**. A priority queue acts like a queue in that you dequeue an item by removing it from the front. However, in a priority queue the logical order of items inside a queue is determined by their priority. The highest priority items are at the front of the queue and the lowest priority items are at the back. Thus when you enqueue an item on a priority queue, the new item may move all the way to the front. We will see that the priority queue is a useful data structure for some of the graph algorithms we will study in the next chapter.\n",
    "\n",
    "You can probably think of a couple of easy ways to implement a priority queue using sorting functions and lists. However, inserting into a list is $O(n)$\n",
    "and sorting a list is $O(nlogn)$. We can do better. The classic way to implement a priority queue is using a data structure called a binary heap. A **binary heap** will allow us both enqueue and dequeue items in $O(logn)$\n",
    "\n",
    ".\n",
    "\n",
    "The binary heap is interesting to study because when we diagram the heap it looks a lot like a tree, but when we implement it we use only a single list as an internal representation. The binary heap has two common variations: the **min heap**, in which the smallest key is always at the front, and the **max heap**, in which the largest key value is always at the front. In this section we will implement the min heap. We leave a max heap implementation as an exercise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.9. Binary Heap Operations\n",
    "\n",
    "The basic operations we will implement for our binary heap are as follows:\n",
    "\n",
    "   * `BinaryHeap()` creates a new, empty, binary heap.\n",
    "   * `insert(k)` adds a new item to the heap.\n",
    "   * `findMin()` returns the item with the minimum key value, leaving item in the heap.\n",
    "   * `delMin()` returns the item with the minimum key value, removing the item from the heap.\n",
    "   * `isEmpty()` returns true if the heap is empty, false otherwise.\n",
    "   * `size()` returns the number of items in the heap.\n",
    "   * `buildHeap(list)` builds a new heap from a list of keys.\n",
    "\n",
    "ActiveCode 1 demonstrates the use of some of the binary heap methods. Notice that no matter the order that we add items to the heap, the smallest is removed each time. We will now turn our attention to creating an implementation for this idea."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "5\n",
      "7\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "from pythonds.trees.binheap import BinHeap\n",
    "\n",
    "bh = BinHeap()\n",
    "bh.insert(5)\n",
    "bh.insert(7)\n",
    "bh.insert(3)\n",
    "bh.insert(11)\n",
    "\n",
    "print(bh.delMin())\n",
    "\n",
    "print(bh.delMin())\n",
    "\n",
    "print(bh.delMin())\n",
    "\n",
    "print(bh.delMin())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.10. Binary Heap Implementation\n",
    "### 6.10.1. The Structure Property\n",
    "In order to make our heap work efficiently, we will take advantage of the logarithmic nature of the binary tree to represent our heap. In order to guarantee logarithmic performance, we must keep our tree balanced. A balanced binary tree has roughly the same number of nodes in the left and right subtrees of the root. In our heap implementation we keep the tree balanced by creating a **complete binary tree**. A complete binary tree is a tree in which each level has all of its nodes. The exception to this is the bottom level of the tree, which we fill in from left to right. Figure 1 shows an example of a complete binary tree.\n",
    "![](images/compTree.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another interesting property of a complete tree is that we can represent it using a single list. We do not need to use nodes and references or even lists of lists. Because the tree is complete, the left child of a parent (at position $p$\n",
    ") is the node that is found in position $2p$ in the list. Similarly, the right child of the parent is at position $2p+1$ in the list. To find the parent of any node in the tree, we can simply use Python’s integer division. Given that a node is at position n in the list, the parent is at position $n/2$. Figure 2 shows a complete binary tree and also gives the list representation of the tree. Note the $2p$ and $2p+1$ relationship between parent and children. The list representation of the tree, along with the full structure property, allows us to efficiently traverse a complete binary tree using only a few simple mathematical operations. We will see that this also leads to an efficient implementation of our binary heap."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.10.2. The Heap Order Property\n",
    "\n",
    "The method that we will use to store items in a heap relies on maintaining the heap order property. The **heap order property** is as follows: In a heap, for every node $x$\n",
    "with parent $p$, the key in $p$ is smaller than or equal to the key in $x$. Figure 2 also illustrates a complete binary tree that has the heap order property.\n",
    "\n",
    "![](images/heapOrder.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.10.3. Heap Operations\n",
    "\n",
    "We will begin our implementation of a binary heap with the constructor. Since the entire binary heap can be represented by a single list, all the constructor will do is initialize the list and an attribute `currentSize` to keep track of the current size of the heap. Listing 1 shows the Python code for the constructor. You will notice that an empty binary heap has a single zero as the first element of `heapList` and that this zero is not used, but is there so that simple integer division can be used in later methods.\n",
    "\n",
    "**Listing 1**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinHeap:\n",
    "    def __init__(self):\n",
    "        self.heapList = [0]\n",
    "        self.currentSize = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next method we will implement is `insert`. The easiest, and most efficient, way to add an item to a list is to simply append the item to the end of the list. The good news about appending is that it guarantees that we will maintain the complete tree property. The bad news about appending is that we will very likely violate the heap structure property. However, it is possible to write a method that will allow us to regain the heap structure property by comparing the newly added item with its parent. If the newly added item is less than its parent, then we can swap the item with its parent. Figure 2 shows the series of swaps needed to percolate the newly added item up to its proper position in the tree.\n",
    "\n",
    "![](images/percUp.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that when we percolate an item up, we are restoring the heap property between the newly added item and the parent. We are also preserving the heap property for any siblings. Of course, if the newly added item is very small, we may still need to swap it up another level. In fact, we may need to keep swapping until we get to the top of the tree. Listing 2 shows the `percUp` method, which percolates a new item as far up in the tree as it needs to go to maintain the heap property. Here is where our wasted element in `heapList` is important. Notice that we can compute the parent of any node by using simple integer division. The parent of the current node can be computed by dividing the index of the current node by 2.\n",
    "\n",
    "We are now ready to write the `insert` method (see Listing 3). Most of the work in the `insert` method is really done by `percUp`. Once a new item is appended to the tree, `percUp` takes over and positions the new item properly.\n",
    "\n",
    "**Listing 2**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def percUp(self,i):\n",
    "    while i // 2 > 0:\n",
    "        if self.heapList[i] < self.heapList[i // 2]:\n",
    "            tmp = self.heapList[i // 2]\n",
    "            self.heapList[i // 2] = self.heapList[i]\n",
    "            self.heapList[i] = tmp\n",
    "        i = i // 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Listing 3**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert(self,k):\n",
    "    self.heapList.append(k)\n",
    "    self.currentSize = self.currentSize + 1\n",
    "    self.percUp(self.currentSize)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the `insert` method properly defined, we can now look at the `delMin` method. Since the heap property requires that the root of the tree be the smallest item in the tree, finding the minimum item is easy. The hard part of `delMin` is restoring full compliance with the heap structure and heap order properties after the root has been removed. We can restore our heap in two steps. First, we will restore the root item by taking the last item in the list and moving it to the root position. Moving the last item maintains our heap structure property. However, we have probably destroyed the heap order property of our binary heap. Second, we will restore the heap order property by pushing the new root node down the tree to its proper position. Figure 3 shows the series of swaps needed to move the new root node to its proper position in the heap.\n",
    "\n",
    "![](images/percDown.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to maintain the heap order property, all we need to do is swap the root with its smallest child less than the root. After the initial swap, we may repeat the swapping process with a node and its children until the node is swapped into a position on the tree where it is already less than both children. The code for percolating a node down the tree is found in the `percDown` and `minChild` methods in Listing 4.\n",
    "\n",
    "**Listing 4**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def percDown(self,i):\n",
    "    while (i * 2) <= self.currentSize:\n",
    "        mc = self.minChild(i)\n",
    "        if self.heapList[i] > self.heapList[mc]:\n",
    "            tmp = self.heapList[i]\n",
    "            self.heapList[i] = self.heapList[mc]\n",
    "            self.heapList[mc] = tmp\n",
    "        i = mc\n",
    "\n",
    "def minChild(self,i):\n",
    "    if i * 2 + 1 > self.currentSize:\n",
    "        return i * 2\n",
    "    else:\n",
    "        if self.heapList[i*2] < self.heapList[i*2+1]:\n",
    "            return i * 2\n",
    "        else:\n",
    "            return i * 2 + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code for the `delmin` operation is in Listing 5. Note that once again the hard work is handled by a helper function, in this case `percDown`.\n",
    "\n",
    "**Listing 5**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delMin(self):\n",
    "    retval = self.heapList[1]\n",
    "    self.heapList[1] = self.heapList[self.currentSize]\n",
    "    self.currentSize = self.currentSize - 1\n",
    "    self.heapList.pop()\n",
    "    self.percDown(1)\n",
    "    return retval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To finish our discussion of binary heaps, we will look at a method to build an entire heap from a list of keys. The first method you might think of may be like the following. Given a list of keys, you could easily build a heap by inserting each key one at a time. Since you are starting with a list of one item, the list is sorted and you could use binary search to find the right position to insert the next key at a cost of approximately $O(logn)$ operations. However, remember that inserting an item in the middle of the list may require $O(n)$ operations to shift the rest of the list over to make room for the new key. Therefore, to insert n keys into the heap would require a total of $O(nlogn)$ operations. However, if we start with an entire list then we can build the whole heap in $O(n)$\n",
    "\n",
    "operations. Listing 6 shows the code to build the entire heap.\n",
    "\n",
    "**Listing 6**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def buildHeap(self,alist):\n",
    "    i = len(alist) // 2\n",
    "    self.currentSize = len(alist)\n",
    "    self.heapList = [0] + alist[:]\n",
    "    while (i > 0):\n",
    "        self.percDown(i)\n",
    "        i = i - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/buildheap.png)\n",
    "Figure 4 shows the swaps that the `buildHeap` method makes as it moves the nodes in an initial tree of `[9, 6, 5, 2, 3]` into their proper positions. Although we start out in the middle of the tree and work our way back toward the root, the `percDown` method ensures that the largest child is always moved down the tree. Because the heap is a complete binary tree, any nodes past the halfway point will be leaves and therefore have no children. Notice that when `i=1`, we are percolating down from the root of the tree, so this may require multiple swaps. As you can see in the rightmost two trees of Figure 4, first the 9 is moved out of the root position, but after 9 is moved down one level in the tree, `percDown` ensures that we check the next set of children farther down in the tree to ensure that it is pushed as low as it can go. In this case it results in a second swap with 3. Now that 9 has been moved to the lowest level of the tree, no further swapping can be done. It is useful to compare the list representation of this series of swaps as shown in Figure 4 with the tree representation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "5\n",
      "6\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "class BinHeap:\n",
    "    def __init__(self):\n",
    "        self.heapList = [0]\n",
    "        self.currentSize = 0\n",
    "\n",
    "\n",
    "    def percUp(self,i):\n",
    "        while i // 2 > 0:\n",
    "            if self.heapList[i] < self.heapList[i // 2]:\n",
    "                tmp = self.heapList[i // 2]\n",
    "                self.heapList[i // 2] = self.heapList[i]\n",
    "                self.heapList[i] = tmp\n",
    "            i = i // 2\n",
    "\n",
    "    def insert(self,k):\n",
    "        self.heapList.append(k)\n",
    "        self.currentSize = self.currentSize + 1\n",
    "        self.percUp(self.currentSize)\n",
    "\n",
    "    def percDown(self,i):\n",
    "        while (i * 2) <= self.currentSize:\n",
    "            mc = self.minChild(i)\n",
    "            if self.heapList[i] > self.heapList[mc]:\n",
    "                tmp = self.heapList[i]\n",
    "                self.heapList[i] = self.heapList[mc]\n",
    "                self.heapList[mc] = tmp\n",
    "            i = mc\n",
    "\n",
    "    def minChild(self,i):\n",
    "        if i * 2 + 1 > self.currentSize:\n",
    "            return i * 2\n",
    "        else:\n",
    "            if self.heapList[i*2] < self.heapList[i*2+1]:\n",
    "                return i * 2\n",
    "            else:\n",
    "                return i * 2 + 1\n",
    "\n",
    "    def delMin(self):\n",
    "        retval = self.heapList[1]\n",
    "        self.heapList[1] = self.heapList[self.currentSize]\n",
    "        self.currentSize = self.currentSize - 1\n",
    "        self.heapList.pop()\n",
    "        self.percDown(1)\n",
    "        return retval\n",
    "\n",
    "    def buildHeap(self,alist):\n",
    "        i = len(alist) // 2\n",
    "        self.currentSize = len(alist)\n",
    "        self.heapList = [0] + alist[:]\n",
    "        while (i > 0):\n",
    "            self.percDown(i)\n",
    "            i = i - 1\n",
    "\n",
    "bh = BinHeap()\n",
    "bh.buildHeap([9,5,6,2,3])\n",
    "\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())\n",
    "print(bh.delMin())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.11. Binary Search Trees\n",
    "\n",
    "We have already seen two different ways to get key-value pairs in a collection. Recall that these collections implement the **map** abstract data type. The two implementations of a map ADT we discussed were binary search on a list and hash tables. In this section we will study **binary search trees** as yet another way to map from a key to a value. In this case we are not interested in the exact placement of items in the tree, but we are interested in using the binary tree structure to provide for efficient searching."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.12. Search Tree Operations\n",
    "\n",
    "Before we look at the implementation, let’s review the interface provided by the map ADT. You will notice that this interface is very similar to the Python dictionary.\n",
    "\n",
    "   * `Map()` Create a new, empty map.\n",
    "   * `put(key,val)` Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.\n",
    "   * `get(key)` Given a key, return the value stored in the map or `None` otherwise.\n",
    "   * `del` Delete the key-value pair from the map using a statement of the form `del map[key]`.\n",
    "   * `len()` Return the number of key-value pairs stored in the map.\n",
    "   * `in` Return `True` for a statement of the form `key in map`, if the given key is in the map."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.13. Search Tree Implementation\n",
    "\n",
    "A binary search tree relies on the property that keys that are less than the parent are found in the left subtree, and keys that are greater than the parent are found in the right subtree. We will call this the **bst property**. As we implement the Map interface as described above, the bst property will guide our implementation. Figure 1 illustrates this property of a binary search tree, showing the keys without any associated values. Notice that the property holds for each parent and child. All of the keys in the left subtree are less than the key in the root. All of the keys in the right subtree are greater than the root.\n",
    "\n",
    "![](images/simpleBST.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that you know what a binary search tree is, we will look at how a binary search tree is constructed. The search tree in Figure 1 represents the nodes that exist after we have inserted the following keys in the order shown: $70,31,93,94,14,23,73$. Since 70 was the first key inserted into the tree, it is the root. Next, 31 is less than 70, so it becomes the left child of 70. Next, 93 is greater than 70, so it becomes the right child of 70. Now we have two levels of the tree filled, so the next key is going to be the left or right child of either 31 or 93. Since 94 is greater than 70 and 93, it becomes the right child of 93. Similarly 14 is less than 70 and 31, so it becomes the left child of 31. 23 is also less than 31, so it must be in the left subtree of 31. However, it is greater than 14, so it becomes the right child of 14.\n",
    "\n",
    "To implement the binary search tree, we will use the nodes and references approach similar to the one we used to implement the linked list, and the expression tree. However, because we must be able create and work with a binary search tree that is empty, our implementation will use two classes. The first class we will call `BinarySearchTree`, and the second class we will call `TreeNode`. The `BinarySearchTree` class has a reference to the TreeNode that is the root of the binary search tree. In most cases the external methods defined in the outer class simply check to see if the tree is empty. If there are nodes in the tree, the request is just passed on to a private method defined in the `BinarySearchTree` class that takes the root as a parameter. In the case where the tree is empty or we want to delete the key at the root of the tree, we must take special action. The code for the `BinarySearchTree` class constructor along with a few other miscellaneous functions is shown in Listing 1.\n",
    "\n",
    "**Listing 1**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinarySearchTree:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.size = 0\n",
    "\n",
    "    def length(self):\n",
    "        return self.size\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self.root.__iter__()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `TreeNode` class provides many helper functions that make the work done in the `BinarySearchTree` class methods much easier. The constructor for a `TreeNode`, along with these helper functions, is shown in Listing 2. As you can see in the listing many of these helper functions help to classify a node according to its own position as a child, (left or right) and the kind of children the node has. The `TreeNode` class will also explicitly keep track of the parent as an attribute of each node. You will see why this is important when we discuss the implementation for the `del` operator.\n",
    "\n",
    "Another interesting aspect of the implementation of `TreeNode` in Listing 2 is that we use Python’s optional parameters. Optional parameters make it easy for us to create a `TreeNode `under several different circumstances. Sometimes we will want to construct a new `TreeNode` that already has both a parent and a `child`. With an existing parent and child, we can pass parent and child as parameters. At other times we will just create a `TreeNode` with the key value pair, and we will not pass any parameters for `parent` or `child`. In this case, the default values of the optional parameters are used.\n",
    "\n",
    "**Listing 2**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self,key,val,left=None,right=None,\n",
    "                                       parent=None):\n",
    "        self.key = key\n",
    "        self.payload = val\n",
    "        self.leftChild = left\n",
    "        self.rightChild = right\n",
    "        self.parent = parent\n",
    "\n",
    "    def hasLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    def hasRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    def isLeftChild(self):\n",
    "        return self.parent and self.parent.leftChild == self\n",
    "\n",
    "    def isRightChild(self):\n",
    "        return self.parent and self.parent.rightChild == self\n",
    "\n",
    "    def isRoot(self):\n",
    "        return not self.parent\n",
    "\n",
    "    def isLeaf(self):\n",
    "        return not (self.rightChild or self.leftChild)\n",
    "\n",
    "    def hasAnyChildren(self):\n",
    "        return self.rightChild or self.leftChild\n",
    "\n",
    "    def hasBothChildren(self):\n",
    "        return self.rightChild and self.leftChild\n",
    "\n",
    "    def replaceNodeData(self,key,value,lc,rc):\n",
    "        self.key = key\n",
    "        self.payload = value\n",
    "        self.leftChild = lc\n",
    "        self.rightChild = rc\n",
    "        if self.hasLeftChild():\n",
    "            self.leftChild.parent = self\n",
    "        if self.hasRightChild():\n",
    "            self.rightChild.parent = self"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have the `BinarySearchTree shell` and the `TreeNode` it is time to write the `put` method that will allow us to build our binary search tree. The `put` method is a method of the `BinarySearchTree` class. This method will check to see if the tree already has a root. If there is not a root then `put` will create a new TreeNode and install it as the root of the tree. If a root node is already in place then `put` calls the private, recursive, helper function `_put` to search the tree according to the following algorithm:\n",
    "\n",
    "   * Starting at the root of the tree, search the binary tree comparing the new key to the key in the current node. If the new key is less than the current node, search the left subtree. If the new key is greater than the current node, search the right subtree.\n",
    "   * When there is no left (or right) child to search, we have found the position in the tree where the new node should be installed.\n",
    "   * To add a node to the tree, create a new TreeNode object and insert the object at the point discovered in the previous step.\n",
    "\n",
    "Listing 3 shows the Python code for inserting a new node in the tree. The `_put` function is written recursively following the steps outlined above. Notice that when a new child is inserted into the tree, the `currentNode` is passed to the new tree as the parent.\n",
    "\n",
    "One important problem with our implementation of insert is that duplicate keys are not handled properly. As our tree is implemented a duplicate key will create a new node with the same key value in the right subtree of the node having the original key. The result of this is that the node with the new key will never be found during a search. A better way to handle the insertion of a duplicate key is for the value associated with the new key to replace the old value. We leave fixing this bug as an exercise for you.\n",
    "\n",
    "**Listing 3**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def put(self,key,val):\n",
    "    if self.root:\n",
    "        self._put(key,val,self.root)\n",
    "    else:\n",
    "        self.root = TreeNode(key,val)\n",
    "    self.size = self.size + 1\n",
    "\n",
    "def _put(self,key,val,currentNode):\n",
    "    if key < currentNode.key:\n",
    "        if currentNode.hasLeftChild():\n",
    "               self._put(key,val,currentNode.leftChild)\n",
    "        else:\n",
    "               currentNode.leftChild = TreeNode(key,val,parent=currentNode)\n",
    "    else:\n",
    "        if currentNode.hasRightChild():\n",
    "               self._put(key,val,currentNode.rightChild)\n",
    "        else:\n",
    "               currentNode.rightChild = TreeNode(key,val,parent=currentNode)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the `put` method defined, we can easily overload the `[]` operator for assignment by having the `__setitem__` method call (see Listing 4) the put method. This allows us to write Python statements like `myZipTree['Plymouth'] = 55446`, just like a Python dictionary.\n",
    "\n",
    "**Listing 4**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __setitem__(self,k,v):\n",
    "    self.put(k,v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Figure 2 illustrates the process for inserting a new node into a binary search tree. The lightly shaded nodes indicate the nodes that were visited during the insertion process.\n",
    "\n",
    "![](images/bstput.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once the tree is constructed, the next task is to implement the retrieval of a value for a given key. The `get` method is even easier than the put method because it simply searches the tree recursively until it gets to a non-matching leaf node or finds a matching key. When a matching key is found, the value stored in the payload of the node is returned.\n",
    "\n",
    "Listing 5 shows the code for `get`, `_get` and `__getitem__`. The search code in the `_get` method uses the same logic for choosing the left or right child as the `_put` method. Notice that the `_get` method returns a `TreeNode` to get, this allows `_get` to be used as a flexible helper method for other `BinarySearchTree` methods that may need to make use of other data from the `TreeNode` besides the payload.\n",
    "\n",
    "By implementing the `__getitem__` method we can write a Python statement that looks just like we are accessing a dictionary, when in fact we are using a binary search tree, for example `z = myZipTree['Fargo']`. As you can see, all the `__getitem__` method does is call `get`.\n",
    "\n",
    "**Listing 5**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get(self,key):\n",
    "    if self.root:\n",
    "        res = self._get(key,self.root)\n",
    "        if res:\n",
    "               return res.payload\n",
    "        else:\n",
    "               return None\n",
    "    else:\n",
    "        return None\n",
    "\n",
    "def _get(self,key,currentNode):\n",
    "    if not currentNode:\n",
    "        return None\n",
    "    elif currentNode.key == key:\n",
    "        return currentNode\n",
    "    elif key < currentNode.key:\n",
    "        return self._get(key,currentNode.leftChild)\n",
    "    else:\n",
    "        return self._get(key,currentNode.rightChild)\n",
    "\n",
    "def __getitem__(self,key):\n",
    "    return self.get(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using `get`, we can implement the `in` operation by writing a `__contains__` method for the `BinarySearchTree`. The `__contains__` method will simply call `get` and return `True` if `get` returns a value, or `False` if it returns `None`. The code for `__contains__` is shown in Listing 6.\n",
    "\n",
    "**Listing 6**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __contains__(self,key):\n",
    "    if self._get(key,self.root):\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that `__contains__` overloads the `in` operator and allows us to write statements such as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'myZipTree' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-14-fbf988e144fb>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0;34m'Northfield'\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mmyZipTree\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"oom ya ya\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'myZipTree' is not defined"
     ]
    }
   ],
   "source": [
    "if 'Northfield' in myZipTree:\n",
    "    print(\"oom ya ya\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we turn our attention to the most challenging method in the binary search tree, the deletion of a key (see Listing 7). The first task is to find the node to delete by searching the tree. If the tree has more than one node we search using the `_get` method to find the `TreeNode` that needs to be removed. If the tree only has a single node, that means we are removing the root of the tree, but we still must check to make sure the key of the root matches the key that is to be deleted. In either case if the key is not found the `del` operator raises an error.\n",
    "\n",
    "**Listing 7**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete(self,key):\n",
    "    if self.size > 1:\n",
    "        nodeToRemove = self._get(key,self.root)\n",
    "        if nodeToRemove:\n",
    "            self.remove(nodeToRemove)\n",
    "            self.size = self.size-1\n",
    "        else:\n",
    "            raise KeyError('Error, key not in tree')\n",
    "    elif self.size == 1 and self.root.key == key:\n",
    "        self.root = None\n",
    "        self.size = self.size - 1\n",
    "    else:\n",
    "        raise KeyError('Error, key not in tree')\n",
    "\n",
    "def __delitem__(self,key):\n",
    "    self.delete(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we’ve found the node containing the key we want to delete, there are three cases that we must consider:\n",
    "\n",
    "   * The node to be deleted has no children (see Figure 3).\n",
    "   * The node to be deleted has only one child (see Figure 4).\n",
    "   * The node to be deleted has two children (see Figure 5).\n",
    "\n",
    "The first case is straightforward (see Listing 8). If the current node has no children all we need to do is delete the node and remove the reference to this node in the parent. The code for this case is shown in here.\n",
    "\n",
    "**Listing 8**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if currentNode.isLeaf():\n",
    "    if currentNode == currentNode.parent.leftChild:\n",
    "        currentNode.parent.leftChild = None\n",
    "    else:\n",
    "        currentNode.parent.rightChild = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/bstdel1.png)\n",
    "The second case is only slightly more complicated (see Listing 9). If a node has only a single child, then we can simply promote the child to take the place of its parent. The code for this case is shown in the next listing. As you look at this code you will see that there are six cases to consider. Since the cases are symmetric with respect to either having a left or right child we will just discuss the case where the current node has a left child. The decision proceeds as follows:\n",
    "\n",
    "   1. If the current node is a left child then we only need to update the parent reference of the left child to point to the parent of the current node, and then update the left child reference of the parent to point to the current node’s left child.\n",
    "   2. If the current node is a right child then we only need to update the parent reference of the left child to point to the parent of the current node, and then update the right child reference of the parent to point to the current node’s left child.\n",
    "   3. If the current node has no parent, it must be the root. In this case we will just replace the `key`, `payload`, `leftChild`, and `rightChild` data by calling the `replaceNodeData` method on the root.\n",
    "   \n",
    "**Listing 9**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "else: # this node has one child\n",
    "    if currentNode.hasLeftChild():\n",
    "        if currentNode.isLeftChild():\n",
    "            currentNode.leftChild.parent = currentNode.parent\n",
    "            currentNode.parent.leftChild = currentNode.leftChild\n",
    "        elif currentNode.isRightChild():\n",
    "            currentNode.leftChild.parent = currentNode.parent\n",
    "            currentNode.parent.rightChild = currentNode.leftChild\n",
    "        else:\n",
    "            currentNode.replaceNodeData(currentNode.leftChild.key,\n",
    "                             currentNode.leftChild.payload,\n",
    "                             currentNode.leftChild.leftChild,\n",
    "                             currentNode.leftChild.rightChild)\n",
    "    else:\n",
    "        if currentNode.isLeftChild():\n",
    "            currentNode.rightChild.parent = currentNode.parent\n",
    "            currentNode.parent.leftChild = currentNode.rightChild\n",
    "        elif currentNode.isRightChild():\n",
    "            currentNode.rightChild.parent = currentNode.parent\n",
    "            currentNode.parent.rightChild = currentNode.rightChild\n",
    "        else:\n",
    "            currentNode.replaceNodeData(currentNode.rightChild.key,\n",
    "                             currentNode.rightChild.payload,\n",
    "                             currentNode.rightChild.leftChild,\n",
    "                             currentNode.rightChild.rightChild)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/bstdel2.png)\n",
    "\n",
    "The third case is the most difficult case to handle (see Listing 10). If a node has two children, then it is unlikely that we can simply promote one of them to take the node’s place. We can, however, search the tree for a node that can be used to replace the one scheduled for deletion. What we need is a node that will preserve the binary search tree relationships for both of the existing left and right subtrees. The node that will do this is the node that has the next-largest key in the tree. We call this node the successor, and we will look at a way to find the successor shortly. The successor is guaranteed to have no more than one child, so we know how to remove it using the two cases for deletion that we have already implemented. Once the successor has been removed, we simply put it in the tree in place of the node to be deleted.\n",
    "\n",
    "![](images/bstdel3.png)\n",
    "\n",
    "The code to handle the third case is shown in the next listing. Notice that we make use of the helper methods `findSuccessor` and `findMin` to find the successor. To remove the successor, we make use of the method `spliceOut`. The reason we use spliceOut is that it goes directly to the node we want to splice out and makes the right changes. We could call `delete` recursively, but then we would waste time re-searching for the key node.\n",
    "\n",
    "**Listing 10**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "elif currentNode.hasBothChildren(): #interior\n",
    "        succ = currentNode.findSuccessor()\n",
    "        succ.spliceOut()\n",
    "        currentNode.key = succ.key\n",
    "        currentNode.payload = succ.payload"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code to find the successor is shown below (see Listing 11) and as you can see is a method of the `TreeNode` class. This code makes use of the same properties of binary search trees that cause an inorder traversal to print out the nodes in the tree from smallest to largest. There are three cases to consider when looking for the successor:\n",
    "\n",
    "   1. If the node has a right child, then the successor is the smallest key in the right subtree.\n",
    "   2. If the node has no right child and is the left child of its parent, then the parent is the successor.\n",
    "   3. If the node is the right child of its parent, and itself has no right child, then the successor to this node is the successor of its parent, excluding this node.\n",
    "\n",
    "The first condition is the only one that matters for us when deleting a node from a binary search tree. However, the `findSuccessor` method has other uses that we will explore in the exercises at the end of this chapter.\n",
    "\n",
    "The `findMin` method is called to find the minimum key in a subtree. You should convince yourself that the minimum valued key in any binary search tree is the leftmost child of the tree. Therefore the `findMin` method simply follows the `leftChild` references in each node of the subtree until it reaches a node that does not have a left child.\n",
    "\n",
    "**Listing 11**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findSuccessor(self):\n",
    "    succ = None\n",
    "    if self.hasRightChild():\n",
    "        succ = self.rightChild.findMin()\n",
    "    else:\n",
    "        if self.parent:\n",
    "            if self.isLeftChild():\n",
    "                succ = self.parent\n",
    "            else:\n",
    "                self.parent.rightChild = None\n",
    "                succ = self.parent.findSuccessor()\n",
    "                self.parent.rightChild = self\n",
    "    return succ\n",
    "\n",
    "def findMin(self):\n",
    "    current = self\n",
    "    while current.hasLeftChild():\n",
    "        current = current.leftChild\n",
    "    return current\n",
    "\n",
    "def spliceOut(self):\n",
    "    if self.isLeaf():\n",
    "        if self.isLeftChild():\n",
    "               self.parent.leftChild = None\n",
    "        else:\n",
    "               self.parent.rightChild = None\n",
    "    elif self.hasAnyChildren():\n",
    "        if self.hasLeftChild():\n",
    "            if self.isLeftChild():\n",
    "                self.parent.leftChild = self.leftChild\n",
    "            else:\n",
    "                self.parent.rightChild = self.leftChild\n",
    "            self.leftChild.parent = self.parent\n",
    "        else:\n",
    "            if self.isLeftChild():\n",
    "                self.parent.leftChild = self.rightChild\n",
    "            else:\n",
    "                self.parent.rightChild = self.rightChild\n",
    "            self.rightChild.parent = self.parent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to look at one last interface method for the binary search tree. Suppose that we would like to simply iterate over all the keys in the tree in order. This is definitely something we have done with dictionaries, so why not trees? You already know how to traverse a binary tree in order, using the `inorder` traversal algorithm. However, writing an iterator requires a bit more work, since an iterator should return only one node each time the iterator is called.\n",
    "\n",
    "Python provides us with a very powerful function to use when creating an iterator. The function is called `yield`. `yield` is similar to `return` in that it returns a value to the caller. However, `yield` also takes the additional step of freezing the state of the function so that the next time the function is called it continues executing from the exact point it left off earlier. Functions that create objects that can be iterated are called generator functions.\n",
    "\n",
    "The code for an `inorder` iterator of a binary tree is shown in the next listing. Look at this code carefully; at first glance you might think that the code is not recursive. However, remember that `__iter__` overrides the for x in operation for iteration, so it really is recursive! Because it is recursive over `TreeNode` instances the `__iter__` method is defined in the `TreeNode` class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __iter__(self):\n",
    "    if self:\n",
    "        if self.hasLeftChild():\n",
    "             for elem in self.leftChiLd:\n",
    "                yield elem\n",
    "        yield self.key\n",
    "        if self.hasRightChild():\n",
    "             for elem in self.rightChild:\n",
    "                yield elem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At this point you may want to download the entire file containing the full version of the `BinarySearchTree` and `TreeNode` classes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "yellow\n",
      "at\n"
     ]
    }
   ],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self,key,val,left=None,right=None,parent=None):\n",
    "        self.key = key\n",
    "        self.payload = val\n",
    "        self.leftChild = left\n",
    "        self.rightChild = right\n",
    "        self.parent = parent\n",
    "\n",
    "    def hasLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    def hasRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    def isLeftChild(self):\n",
    "        return self.parent and self.parent.leftChild == self\n",
    "\n",
    "    def isRightChild(self):\n",
    "        return self.parent and self.parent.rightChild == self\n",
    "\n",
    "    def isRoot(self):\n",
    "        return not self.parent\n",
    "\n",
    "    def isLeaf(self):\n",
    "        return not (self.rightChild or self.leftChild)\n",
    "\n",
    "    def hasAnyChildren(self):\n",
    "        return self.rightChild or self.leftChild\n",
    "\n",
    "    def hasBothChildren(self):\n",
    "        return self.rightChild and self.leftChild\n",
    "\n",
    "    def spliceOut(self):\n",
    "        if self.isLeaf():\n",
    "            if self.isLeftChild():\n",
    "                self.parent.leftChild = None\n",
    "            else:\n",
    "                self.parent.rightChild = None\n",
    "        elif self.hasAnyChildren():\n",
    "            if self.hasLeftChild():\n",
    "                if self.isLeftChild():\n",
    "                    self.parent.leftChild = self.leftChild\n",
    "                else:\n",
    "                    self.parent.rightChild = self.leftChild\n",
    "                self.leftChild.parent = self.parent\n",
    "            else:\n",
    "                if self.isLeftChild():\n",
    "                    self.parent.leftChild = self.rightChild\n",
    "                else:\n",
    "                    self.parent.rightChild = self.rightChild\n",
    "                self.rightChild.parent = self.parent\n",
    "\n",
    "    def findSuccessor(self):\n",
    "        succ = None\n",
    "        if self.hasRightChild():\n",
    "            succ = self.rightChild.findMin()\n",
    "        else:\n",
    "            if self.parent:\n",
    "                if self.isLeftChild():\n",
    "                    succ = self.parent\n",
    "                else:\n",
    "                    self.parent.rightChild = None\n",
    "                    succ = self.parent.findSuccessor()\n",
    "                    self.parent.rightChild = self\n",
    "        return succ\n",
    "\n",
    "    def findMin(self):\n",
    "        current = self\n",
    "        while current.hasLeftChild():\n",
    "            current = current.leftChild\n",
    "        return current\n",
    "\n",
    "    def replaceNodeData(self,key,value,lc,rc):\n",
    "        self.key = key\n",
    "        self.payload = value\n",
    "        self.leftChild = lc\n",
    "        self.rightChild = rc\n",
    "        if self.hasLeftChild():\n",
    "            self.leftChild.parent = self\n",
    "        if self.hasRightChild():\n",
    "            self.rightChild.parent = self\n",
    "\n",
    "\n",
    "class BinarySearchTree:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.size = 0\n",
    "\n",
    "    def length(self):\n",
    "        return self.size\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def put(self,key,val):\n",
    "        if self.root:\n",
    "            self._put(key,val,self.root)\n",
    "        else:\n",
    "            self.root = TreeNode(key,val)\n",
    "        self.size = self.size + 1\n",
    "\n",
    "    def _put(self,key,val,currentNode):\n",
    "        if key < currentNode.key:\n",
    "            if currentNode.hasLeftChild():\n",
    "                   self._put(key,val,currentNode.leftChild)\n",
    "            else:\n",
    "                   currentNode.leftChild = TreeNode(key,val,parent=currentNode)\n",
    "        else:\n",
    "            if currentNode.hasRightChild():\n",
    "                   self._put(key,val,currentNode.rightChild)\n",
    "            else:\n",
    "                   currentNode.rightChild = TreeNode(key,val,parent=currentNode)\n",
    "\n",
    "    def __setitem__(self,k,v):\n",
    "        self.put(k,v)\n",
    "\n",
    "    def get(self,key):\n",
    "        if self.root:\n",
    "            res = self._get(key,self.root)\n",
    "            if res:\n",
    "                  return res.payload\n",
    "            else:\n",
    "                  return None\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def _get(self,key,currentNode):\n",
    "        if not currentNode:\n",
    "            return None\n",
    "        elif currentNode.key == key:\n",
    "            return currentNode\n",
    "        elif key < currentNode.key:\n",
    "            return self._get(key,currentNode.leftChild)\n",
    "        else:\n",
    "            return self._get(key,currentNode.rightChild)\n",
    "\n",
    "    def __getitem__(self,key):\n",
    "        return self.get(key)\n",
    "\n",
    "    def __contains__(self,key):\n",
    "        if self._get(key,self.root):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def delete(self,key):\n",
    "        if self.size > 1:\n",
    "            nodeToRemove = self._get(key,self.root)\n",
    "            if nodeToRemove:\n",
    "                self.remove(nodeToRemove)\n",
    "                self.size = self.size-1\n",
    "            else:\n",
    "                raise KeyError('Error, key not in tree')\n",
    "        elif self.size == 1 and self.root.key == key:\n",
    "            self.root = None\n",
    "            self.size = self.size - 1\n",
    "        else:\n",
    "            raise KeyError('Error, key not in tree')\n",
    "\n",
    "    def __delitem__(self,key):\n",
    "         self.delete(key)\n",
    "\n",
    "    def remove(self,currentNode):\n",
    "        if currentNode.isLeaf(): #leaf\n",
    "            if currentNode == currentNode.parent.leftChild:\n",
    "                currentNode.parent.leftChild = None\n",
    "            else:\n",
    "                currentNode.parent.rightChild = None\n",
    "        elif currentNode.hasBothChildren(): #interior\n",
    "            succ = currentNode.findSuccessor()\n",
    "            succ.spliceOut()\n",
    "            currentNode.key = succ.key\n",
    "            currentNode.payload = succ.payload\n",
    "\n",
    "        else: # this node has one child\n",
    "            if currentNode.hasLeftChild():\n",
    "                if currentNode.isLeftChild():\n",
    "                    currentNode.leftChild.parent = currentNode.parent\n",
    "                    currentNode.parent.leftChild = currentNode.leftChild\n",
    "                elif currentNode.isRightChild():\n",
    "                    currentNode.leftChild.parent = currentNode.parent\n",
    "                    currentNode.parent.rightChild = currentNode.leftChild\n",
    "                else:\n",
    "                    currentNode.replaceNodeData(currentNode.leftChild.key,\n",
    "                                    currentNode.leftChild.payload,\n",
    "                                    currentNode.leftChild.leftChild,\n",
    "                                    currentNode.leftChild.rightChild)\n",
    "            else:\n",
    "                if currentNode.isLeftChild():\n",
    "                    currentNode.rightChild.parent = currentNode.parent\n",
    "                    currentNode.parent.leftChild = currentNode.rightChild\n",
    "                elif currentNode.isRightChild():\n",
    "                    currentNode.rightChild.parent = currentNode.parent\n",
    "                    currentNode.parent.rightChild = currentNode.rightChild\n",
    "                else:\n",
    "                    currentNode.replaceNodeData(currentNode.rightChild.key,\n",
    "                                    currentNode.rightChild.payload,\n",
    "                                    currentNode.rightChild.leftChild,\n",
    "                                    currentNode.rightChild.rightChild)\n",
    "\n",
    "mytree = BinarySearchTree()\n",
    "mytree[3]=\"red\"\n",
    "mytree[4]=\"blue\"\n",
    "mytree[6]=\"yellow\"\n",
    "mytree[2]=\"at\"\n",
    "\n",
    "print(mytree[6])\n",
    "print(mytree[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.14. Search Tree Analysis\n",
    "\n",
    "With the implementation of a binary search tree now complete, we will do a quick analysis of the methods we have implemented. Let’s first look at the `put` method. The limiting factor on its performance is the height of the binary tree. Recall from the vocabulary section that the height of a tree is the number of edges between the root and the deepest leaf node. The height is the limiting factor because when we are searching for the appropriate place to insert a node into the tree, we will need to do at most one comparison at each level of the tree.\n",
    "\n",
    "What is the height of a binary tree likely to be? The answer to this question depends on how the keys are added to the tree. If the keys are added in a random order, the height of the tree is going to be around log2n where n is the number of nodes in the tree. This is because if the keys are randomly distributed, about half of them will be less than the root and half will be greater than the root. Remember that in a binary tree there is one node at the root, two nodes in the next level, and four at the next. The number of nodes at any particular level is 2d where d is the depth of the level. The total number of nodes in a perfectly balanced binary tree is $2^{h+1}−1$, where $h$ represents the height of the tree.\n",
    "\n",
    "A perfectly balanced tree has the same number of nodes in the left subtree as the right subtree. In a balanced binary tree, the worst-case performance of `put` is $O(log_2n)$\n",
    ", where n is the number of nodes in the tree. Notice that this is the inverse relationship to the calculation in the previous paragraph. So $log_2n$ gives us the height of the tree, and represents the maximum number of comparisons that `put` will need to do as it searches for the proper place to insert a new node.\n",
    "\n",
    "Unfortunately it is possible to construct a search tree that has height n\n",
    "simply by inserting the keys in sorted order! An example of such a tree is shown in Figure 6. In this case the performance of the `put` method is $O(n)$.\n",
    "\n",
    "![](images/skewedTree.png)\n",
    "\n",
    "Now that you understand that the performance of the `put` method is limited by the height of the tree, you can probably guess that other methods, `get`, `in`, and `del`, are limited as well. Since `get` searches the tree to find the key, in the worst case the tree is searched all the way to the bottom and no key is found. At first glance `del` might seem more complicated, since it may need to search for the successor before the deletion operation can complete. But remember that the worst-case scenario to find the successor is also just the height of the tree which means that you would simply double the work. Since doubling is a constant factor it does not change worst case"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.15. Balanced Binary Search Trees\n",
    "\n",
    "In the previous section we looked at building a binary search tree. As we learned, the performance of the binary search tree can degrade to $O(n)$ for operations like `get` and `put` when the tree becomes unbalanced. In this section we will look at a special kind of binary search tree that automatically makes sure that the tree remains balanced at all times. This tree is called an **AVL tree** and is named for its inventors: G.M. Adelson-Velskii and E.M. Landis.\n",
    "\n",
    "An AVL tree implements the Map abstract data type just like a regular binary search tree, the only difference is in how the tree performs. To implement our AVL tree we need to keep track of a balance factor for each node in the tree. We do this by looking at the heights of the left and right subtrees for each node. More formally, we define the balance factor for a node as the difference between the height of the left subtree and the height of the right subtree.\n",
    "\n",
    "$balanceFactor = height(leftSubTree) - height(rightSubTree)$\n",
    "\n",
    "Using the definition for balance factor given above we say that a subtree is left-heavy if the balance factor is greater than zero. If the balance factor is less than zero then the subtree is right heavy. If the balance factor is zero then the tree is perfectly in balance. For purposes of implementing an AVL tree, and gaining the benefit of having a balanced tree we will define a tree to be in balance if the balance factor is -1, 0, or 1. Once the balance factor of a node in a tree is outside this range we will need to have a procedure to bring the tree back into balance. Figure 1 shows an example of an unbalanced, right-heavy tree and the balance factors of each node.\n",
    "\n",
    "![](images/unbalanced.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.16. AVL Tree Performance\n",
    "\n",
    "Before we proceed any further let’s look at the result of enforcing this new balance factor requirement. Our claim is that by ensuring that a tree always has a balance factor of -1, 0, or 1 we can get better Big-O performance of key operations. Let us start by thinking about how this balance condition changes the worst-case tree. There are two possibilities to consider, a left-heavy tree and a right heavy tree. If we consider trees of heights 0, 1, 2, and 3, Figure 2 illustrates the most unbalanced left-heavy tree possible under the new rules.\n",
    "\n",
    "![](images/worstAVL.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looking at the total number of nodes in the tree we see that for a tree of height 0 there is 1 node, for a tree of height 1 there is $1+1=2$ nodes, for a tree of height 2 there are $1+1+2=4$ and for a tree of height 3 there are $1+2+4=7$. More generally the pattern we see for the number of nodes in a tree of height h ($N_h$) is:\n",
    "\n",
    "<center>$N_h = 1 + N_{h-1} + N_{h-2}$</center>\n",
    "\n",
    "This recurrence may look familiar to you because it is very similar to the Fibonacci sequence. We can use this fact to derive a formula for the height of an AVL tree given the number of nodes in the tree. Recall that for the Fibonacci sequence the ith\n",
    "Fibonacci number is given by:\n",
    "\n",
    "\\begin{split}F_0 = 0 \\\\\n",
    "F_1 = 1 \\\\\n",
    "F_i = F_{i-1} + F_{i-2}  \\text{ for all } i \\ge 2\\end{split}\n",
    "\n",
    "An important mathematical result is that as the numbers of the Fibonacci sequence get larger and larger the ratio of $F_i/F_{i−1}$ becomes closer and closer to approximating the golden ratio $Φ$ which is defined as $\\Phi = \\frac{1 + \\sqrt{5}}{2}$. You can consult a math text if you want to see a derivation of the previous equation. We will simply use this equation to approximate $F_i$ as $F_i =\n",
    "\\Phi^i/\\sqrt{5}$. If we make use of this approximation we can rewrite the equation for $N_h$ as:\n",
    "\n",
    "<center>$N_h = F_{h+1} - 1, h \\ge 1$</center>\n",
    "\n",
    "By replacing the Fibonacci reference with its golden ratio approximation we get:\n",
    "\n",
    "<center>$N_h = \\frac{\\Phi^{h+2}}{\\sqrt{5}} - 1$</center>\n",
    "\n",
    "If we rearrange the terms, and take the base 2 log of both sides and then solve for h we get the following derivation:\n",
    "\n",
    "\\begin{split}\\log{N_h+1} = (h+2)\\log{\\Phi} - \\frac{1}{2} \\log{5} \\\\\n",
    "h = \\frac{\\log{N_h+1} - 2 \\log{\\Phi} + \\frac{1}{2} \\log{5}}{\\log{\\Phi}} \\\\\n",
    "h = 1.44 \\log{N_h}\\end{split}\n",
    "\n",
    "This derivation shows us that at any time the height of our AVL tree is equal to a constant(1.44) times the log of the number of nodes in the tree. This is great news for searching our AVL tree because it limits the search to $O(logN)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.17. AVL Tree Implementation\n",
    "\n",
    "Now that we have demonstrated that keeping an AVL tree in balance is going to be a big performance improvement, let us look at how we will augment the procedure to insert a new key into the tree. Since all new keys are inserted into the tree as leaf nodes and we know that the balance factor for a new leaf is zero, there are no new requirements for the node that was just inserted. But once the new leaf is added we must update the balance factor of its parent. How this new leaf affects the parent’s balance factor depends on whether the leaf node is a left child or a right child. If the new node is a right child the balance factor of the parent will be reduced by one. If the new node is a left child then the balance factor of the parent will be increased by one. This relation can be applied recursively to the grandparent of the new node, and possibly to every ancestor all the way up to the root of the tree. Since this is a recursive procedure let us examine the two base cases for updating balance factors:\n",
    "\n",
    "* The recursive call has reached the root of the tree.\n",
    "* he balance factor of the parent has been adjusted to zero. You should convince yourself that once a subtree has a balance factor of zero, then the balance of its ancestor nodes does not change.\n",
    "\n",
    "We will implement the AVL tree as a subclass of `BinarySearchTree`. To begin, we will override the `_put` method and write a new `updateBalance` helper method. These methods are shown in Listing 1. You will notice that the definition for `_put` is exactly the same as in simple binary search trees except for the additions of the calls to `updateBalance` on lines 7 and 13.\n",
    "\n",
    "**Listing 1**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _put(self,key,val,currentNode):\n",
    "    if key < currentNode.key:\n",
    "        if currentNode.hasLeftChild():\n",
    "                self._put(key,val,currentNode.leftChild)\n",
    "        else:\n",
    "                currentNode.leftChild = TreeNode(key,val,parent=currentNode)\n",
    "                self.updateBalance(currentNode.leftChild)\n",
    "    else:\n",
    "        if currentNode.hasRightChild():\n",
    "                self._put(key,val,currentNode.rightChild)\n",
    "        else:\n",
    "                currentNode.rightChild = TreeNode(key,val,parent=currentNode)\n",
    "                self.updateBalance(currentNode.rightChild)\n",
    "\n",
    "def updateBalance(self,node):\n",
    "    if node.balanceFactor > 1 or node.balanceFactor < -1:\n",
    "        self.rebalance(node)\n",
    "        return\n",
    "    if node.parent != None:\n",
    "        if node.isLeftChild():\n",
    "                node.parent.balanceFactor += 1\n",
    "        elif node.isRightChild():\n",
    "                node.parent.balanceFactor -= 1\n",
    "\n",
    "        if node.parent.balanceFactor != 0:\n",
    "                self.updateBalance(node.parent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The new `updateBalance` method is where most of the work is done. This implements the recursive procedure we just described. The `updateBalance` method first checks to see if the current node is out of balance enough to require rebalancing (line 16). If that is the case then the rebalancing is done and no further updating to parents is required. If the current node does not require rebalancing then the balance factor of the parent is adjusted. If the balance factor of the parent is non-zero then the algorithm continues to work its way up the tree toward the root by recursively calling `updateBalance` on the parent.\n",
    "\n",
    "When a rebalancing of the tree is necessary, how do we do it? Efficient rebalancing is the key to making the AVL Tree work well without sacrificing performance. In order to bring an AVL Tree back into balance we will perform one or more **rotations** on the tree.\n",
    "\n",
    "To understand what a rotation is let us look at a very simple example. Consider the tree in the left half of Figure 3. This tree is out of balance with a balance factor of -2. To bring this tree into balance we will use a left rotation around the subtree rooted at node A.\n",
    "\n",
    "![](images/simpleunbalanced.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To perform a left rotation we essentially do the following:\n",
    "\n",
    "   * Promote the right child (B) to be the root of the subtree.\n",
    "   * Move the old root (A) to be the left child of the new root.\n",
    "   * If new root (B) already had a left child then make it the right child of the new left child (A). Note: Since the new root (B) was the right child of A the right child of A is guaranteed to be empty at this point. This allows us to add a new node as the right child without any further consideration.\n",
    "   \n",
    "While this procedure is fairly easy in concept, the details of the code are a bit tricky since we need to move things around in just the right order so that all properties of a Binary Search Tree are preserved. Furthermore we need to make sure to update all of the parent pointers appropriately."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let’s look at a slightly more complicated tree to illustrate the right rotation. The left side of Figure 4 shows a tree that is left-heavy and with a balance factor of 2 at the root. To perform a right rotation we essentially do the following:\n",
    "\n",
    "* Promote the left child (C) to be the root of the subtree.\n",
    "* Move the old root (E) to be the right child of the new root.\n",
    "* If the new root(C) already had a right child (D) then make it the left child of the new right child (E). Note: Since the new root (C) was the left child of E, the left child of E is guaranteed to be empty at this point. This allows us to add a new node as the left child without any further consideration.\n",
    "\n",
    "![](images/rightrotate1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that you have seen the rotations and have the basic idea of how a rotation works let us look at the code. Listing 2 shows the code for both the right and the left rotations. In line 2 we create a temporary variable to keep track of the new root of the subtree. As we said before the new root is the right child of the previous root. Now that a reference to the right child has been stored in this temporary variable we replace the right child of the old root with the left child of the new.\n",
    "\n",
    "The next step is to adjust the parent pointers of the two nodes. If `newRoot` has a left child then the new parent of the left child becomes the old root. The parent of the new root is set to the parent of the old root. If the old root was the root of the entire tree then we must set the root of the tree to point to this new root. Otherwise, if the old root is a left child then we change the parent of the left child to point to the new root; otherwise we change the parent of the right child to point to the new root. (lines 10-13). Finally we set the parent of the old root to be the new root. This is a lot of complicated bookkeeping, so we encourage you to trace through this function while looking at Figure 3. The `rotateRight` method is symmetrical to rotateLeft so we will leave it to you to study the code for `rotateRight`.\n",
    "\n",
    "**Listing 2**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotateLeft(self,rotRoot):\n",
    "    newRoot = rotRoot.rightChild\n",
    "    rotRoot.rightChild = newRoot.leftChild\n",
    "    if newRoot.leftChild != None:\n",
    "        newRoot.leftChild.parent = rotRoot\n",
    "    newRoot.parent = rotRoot.parent\n",
    "    if rotRoot.isRoot():\n",
    "        self.root = newRoot\n",
    "    else:\n",
    "        if rotRoot.isLeftChild():\n",
    "                rotRoot.parent.leftChild = newRoot\n",
    "        else:\n",
    "            rotRoot.parent.rightChild = newRoot\n",
    "    newRoot.leftChild = rotRoot\n",
    "    rotRoot.parent = newRoot\n",
    "    rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)\n",
    "    newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, lines 16-17 require some explanation. In these two lines we update the balance factors of the old and the new root. Since all the other moves are moving entire subtrees around the balance factors of all other nodes are unaffected by the rotation. But how can we update the balance factors without completely recalculating the heights of the new subtrees? The following derivation should convince you that these lines are correct.\n",
    "\n",
    "![](images/bfderive.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Figure 5 shows a left rotation. B and D are the pivotal nodes and A, C, E are their subtrees. Let $h_x$ denote the height of a particular subtree rooted at node $x$. By definition we know the following:\n",
    "\n",
    "\\begin{split}newBal(B) = h_A - h_C \\\\\n",
    "oldBal(B) = h_A - h_D\\end{split}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But we know that the old height of D can also be given by $1+max(h_C,h_E)$, that is, the height of D is one more than the maximum height of its two children. Remember that $h_c$ and $h_E$ hav not changed. So, let us substitute that in to the second equation, which gives us\n",
    "\n",
    "<center>$oldBal(B) = h_A - (1 + max(h_C,h_E))$</center>\n",
    "\n",
    "and then subtract the two equations. The following steps do the subtraction and use some algebra to simplify the equation for $newBal(B)$\n",
    "\n",
    "\\begin{split}newBal(B) - oldBal(B) = h_A - h_C - (h_A - (1 + max(h_C,h_E))) \\\\\n",
    "newBal(B) - oldBal(B) = h_A - h_C - h_A + (1 + max(h_C,h_E)) \\\\\n",
    "newBal(B) - oldBal(B) = h_A  - h_A + 1 + max(h_C,h_E) - h_C  \\\\\n",
    "newBal(B) - oldBal(B) =  1 + max(h_C,h_E) - h_C\\end{split}\n",
    "\n",
    "Next we will move $oldBal(B)$ to the right hand side of the equation and make use of the fact that $max(a,b)−c=max(a−c,b−c)$.\n",
    "\n",
    "<center>$newBal(B)=oldBal(B)+1+max(hC−hC,hE−hC)$</center>\n",
    "\n",
    "But, $h_E−h_C$ is the same as $−oldBal(D)$. So we can use another identity that says $max(−a,−b)=−min(a,b)$. So we can finish our derivation of $newBal(B)$ with the following steps:\n",
    "\n",
    "<center>$newBal(B)=oldBal(B)+1+max(0,−oldBal(D))newBal(B)=oldBal(B)+1−min(0,oldBal(D))$</center>\n",
    "\n",
    "Now we have all of the parts in terms that we readily know. If we remember that B is `rotRoot` and D is `newRoot` then we can see this corresponds exactly to the statement on line 16, or:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(0,newRoot.balanceFactor)\n",
    "```\n",
    "\n",
    "A similar derivation gives us the equation for the updated node D, as well as the balance factors after a right rotation. We leave these as exercises for you.\n",
    "\n",
    "Now you might think that we are done. We know how to do our left and right rotations, and we know when we should do a left or right rotation, but take a look at Figure 6. Since node A has a balance factor of -2 we should do a left rotation. But, what happens when we do the left rotation around A?\n",
    "\n",
    "![](images/hardunbalanced.png)\n",
    "\n",
    "Figure 7 shows us that after the left rotation we are now out of balance the other way. If we do a right rotation to correct the situation we are right back where we started.\n",
    "\n",
    "![](images/badrotate.png)\n",
    "\n",
    "To correct this problem we must use the following set of rules:\n",
    "\n",
    "   * If a subtree needs a left rotation to bring it into balance, first check the balance factor of the right child. If the right child is left heavy then do a right rotation on right child, followed by the original left rotation.\n",
    "   * If a subtree needs a right rotation to bring it into balance, first check the balance factor of the left child. If the left child is right heavy then do a left rotation on the left child, followed by the original right rotation.\n",
    "\n",
    "Figure 8 shows how these rules solve the dilemma we encountered in Figure 6 and Figure 7. Starting with a right rotation around node C puts the tree in a position where the left rotation around A brings the entire subtree back into balance.\n",
    "\n",
    "![](images/rotatelr.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code that implements these rules can be found in our `rebalance` method, which is shown in Listing 3. Rule number 1 from above is implemented by the `if` statement starting on line 2. Rule number 2 is implemented by the `elif` statement starting on line 8.\n",
    "\n",
    "**Listing 3**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rebalance(self,node):\n",
    "    if node.balanceFactor < 0:\n",
    "        if node.rightChild.balanceFactor > 0:\n",
    "            self.rotateRight(node.rightChild)\n",
    "            self.rotateLeft(node)\n",
    "        else:\n",
    "            self.rotateLeft(node)\n",
    "    elif node.balanceFactor > 0:\n",
    "        if node.leftChild.balanceFactor < 0:\n",
    "            self.rotateLeft(node.leftChild)\n",
    "            self.rotateRight(node)\n",
    "        else:\n",
    "            self.rotateRight(node)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The discussion questions provide you the opportunity to rebalance a tree that requires a left rotation followed by a right. In addition the discussion questions provide you with the opportunity to rebalance some trees that are a little more complex than the tree in Figure 8.\n",
    "\n",
    "By keeping the tree in balance at all times, we can ensure that the `get` method will run in order $O(log_2(n))$\n",
    "time. But the question is at what cost to our `put` method? Let us break this down into the operations performed by put. Since a new node is inserted as a leaf, updating the balance factors of all the parents will require a maximum of $log_2(n)$ operations, one for each level of the tree. If a subtree is found to be out of balance a maximum of two rotations are required to bring the tree back into balance. But, each of the rotations works in $O(1)$ time, so even our `put` operation remains $O(log_2(n))$.\n",
    "\n",
    "At this point we have implemented a functional AVL-Tree, unless you need the ability to delete a node. We leave the deletion of the node and subsequent updating and rebalancing as an exercise for you."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.18. Summary of Map ADT Implementations\n",
    "\n",
    "Over the past two chapters we have looked at several data structures that can be used to implement the map abstract data type. A binary Search on a list, a hash table, a binary search tree, and a balanced binary search tree. To conclude this section, let’s summarize the performance of each data structure for the key operations defined by the map ADT (see Table 1).\n",
    "\n",
    "| operation | Sorted List | Hash Table | Binary Search Tree | AVL Tree |\n",
    "|:---------:|:-----------:|:----------:|:------------------:|:--------:|\n",
    "| put       | O(n)        | O(1)       | O(n)               | O(log2n) |\n",
    "| get       | O(log2n)    | O(1)       | O(n)               | O(log2n) |\n",
    "| in        | O(log2n)    | O(1)       | O(n)               | O(log2n) |\n",
    "| del       | O(n)        | O(1)       | O(n)               | O(log2n) |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.19. Summary\n",
    "\n",
    "In this chapter we have looked at the tree data structure. The tree data structure enables us to write many interesting algorithms. In this chapter we have looked at algorithms that use trees to do the following:\n",
    "\n",
    "   * A binary tree for parsing and evaluating expressions.\n",
    "   * A binary tree for implementing the map ADT.\n",
    "   * A balanced binary tree (AVL tree) for implementing the map ADT.\n",
    "   * A binary tree to implement a min heap.\n",
    "   * A min heap used to implement a priority queue."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.20. Key Terms\n",
    "\n",
    "| AVL tree    | binary heap         | binary search tree   |\n",
    "|-------------|---------------------|----------------------|\n",
    "| binary tree | child / children    | complete binary tree |\n",
    "| edge        | heap order property | height               |\n",
    "| inorder     | leaf node           | level                |\n",
    "| map         | min/max heap        | node                 |\n",
    "| parent      | path                | postorder            |\n",
    "| preorder    | priority queue      | root                 |\n",
    "| rotation    | sibling             | successor            |\n",
    "| subtree     | tree                |                      |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}