{ "cells": [ { "cell_type": "markdown", "metadata": { "id": "15JSQmv0xSLG" }, "source": [ "# Trees - A fast introduction\n", "\n", "A tree is an abstract model of a hierarchical structure. It consists of nodes with a parent-child relationship. Its name comes from the fact that when drawn, it resembles an upside-down tree: the root of the tree is at the top and the leaves are at the bottom.\n", "\n", "A tree is a recursive data structure; each node of the tree contains a label value and a list of branches, each of which are also trees. The label can be any data type, while the branches are represented as a list of trees. The lecture slides provide a good overview of tree terminology and a visual to help demonstrate.\n", "\n", "## Definitions\n", "\n", "* `Node`\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", "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", "The root of the tree is the only node in the tree that has no incoming edges. \n", "\n", "* `Path`\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", "The set of nodes c 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", "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", "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", "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", "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. For example, the level of the Felis node in Figure 1 is five. By definition, the level of the root node is zero.\n", "\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." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "id": "qiJgZPzWy3VM" }, "outputs": [], "source": [ "\n", "def tree(root_label, branches=[]):\n", " ''' This is a simple tree implementation that allows for an arbitrary number of\n", " children for any node'''\n", " for branch in branches:\n", " assert is_tree(branch), 'branches must be trees'\n", " return [root_label] + list(branches)\n", "def label(tree):\n", " return tree[0]\n", "def branches(tree):\n", " return tree[1:]\n", "def is_tree(tree):\n", " if type(tree) != list or len(tree) < 1:\n", " return False\n", " for branch in branches(tree):\n", " if not is_tree(branch):\n", " return False\n", " return True\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "id": "OVAJA6SbzeBG" }, "outputs": [], "source": [ "t = tree(1, [tree(2), tree(3, [tree(4), tree(5)])])" ] }, { "cell_type": "markdown", "metadata": { "id": "Wn5aTBAzziPb" }, "source": [ "Below is some lifted code to visualize the above tree. Credit to Allen Downey." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "id": "vyOHFZR5x0vs" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Requirement already satisfied: EoN in /opt/homebrew/lib/python3.10/site-packages (1.1)\n", "Requirement already satisfied: scipy in /opt/homebrew/lib/python3.10/site-packages (from EoN) (1.10.1)\n", "Requirement already satisfied: numpy in /opt/homebrew/lib/python3.10/site-packages (from EoN) (1.24.2)\n", "Requirement already satisfied: matplotlib in /opt/homebrew/lib/python3.10/site-packages (from EoN) (3.6.2)\n", "Requirement already satisfied: networkx in /opt/homebrew/lib/python3.10/site-packages (from EoN) (3.0)\n", "Requirement already satisfied: pyparsing>=2.2.1 in /opt/homebrew/lib/python3.10/site-packages (from matplotlib->EoN) (3.0.9)\n", "Requirement already satisfied: kiwisolver>=1.0.1 in /opt/homebrew/lib/python3.10/site-packages (from matplotlib->EoN) (1.4.4)\n", "Requirement already satisfied: contourpy>=1.0.1 in /opt/homebrew/lib/python3.10/site-packages (from matplotlib->EoN) (1.0.6)\n", "Requirement already satisfied: pillow>=6.2.0 in /opt/homebrew/lib/python3.10/site-packages (from matplotlib->EoN) (9.2.0)\n", "Requirement already satisfied: fonttools>=4.22.0 in /opt/homebrew/lib/python3.10/site-packages (from matplotlib->EoN) (4.38.0)\n", "Requirement already satisfied: packaging>=20.0 in /opt/homebrew/lib/python3.10/site-packages (from matplotlib->EoN) (21.3)\n", "Requirement already satisfied: cycler>=0.10 in /opt/homebrew/lib/python3.10/site-packages (from matplotlib->EoN) (0.11.0)\n", "Requirement already satisfied: python-dateutil>=2.7 in /opt/homebrew/lib/python3.10/site-packages (from matplotlib->EoN) (2.8.2)\n", "Requirement already satisfied: six>=1.5 in /opt/homebrew/lib/python3.10/site-packages (from python-dateutil>=2.7->matplotlib->EoN) (1.16.0)\n", "Requirement already satisfied: networkx in /opt/homebrew/lib/python3.10/site-packages (3.0)\n" ] } ], "source": [ "try:\n", " import EoN\n", "except ImportError:\n", " !pip install EoN\n", "\n", "\n", "try:\n", "\timport networkx as nx\n", "except ImportError:\n", " !pip install networkx\n", "\n", "def add_edges(parent, G):\n", " \"\"\"Make a NetworkX graph that represents the tree.\"\"\"\n", " if parent is None:\n", " return\n", " \n", " for child in branches(parent):\n", " if child:\n", " G.add_edge(parent[0], child[0])\n", " add_edges(child, G)\n", "def get_labels(parent, labels):\n", " if parent is None:\n", " return\n", " \n", " if parent[0] == '\\0':\n", " labels[parent] = parent.count\n", " else:\n", " labels[parent] = parent.letter\n", " \n", " get_labels(parent.left, labels)\n", " get_labels(parent.right, labels)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "id": "7pAGS6bcx1WE" }, "outputs": [ { "ename": "NameError", "evalue": "name 'nx' is not defined", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)", "Cell \u001b[0;32mIn[6], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m G \u001b[38;5;241m=\u001b[39m \u001b[43mnx\u001b[49m\u001b[38;5;241m.\u001b[39mDiGraph()\n\u001b[1;32m 2\u001b[0m add_edges(t, G)\n", "\u001b[0;31mNameError\u001b[0m: name 'nx' is not defined" ] } ], "source": [ "G = nx.DiGraph()\n", "add_edges(t, G)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 319 }, "id": "6YO21tUGyYyC", "outputId": "669ddc4e-9ccd-470c-8fc6-6d0c93cc8847" }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAAsTAAALEwEAmpwYAAAmhUlEQVR4nO3dy1OUWYI28CdvXJOL3ORW3ASFklsJQgFCJqCIE10d1RGzn5hFx7eazaz6H5jVrCZi9lPLnon+OvqLjmkQC0lAEhVKMEUpUQQ1C0EgTcgE8vq+36JaSwtRUDLPe3l+OyGTfMI4vA958rznGGRZlkFERKQTRtEBiIiI4onFR0REusLiIyIiXWHxERGRrrD4iIhIV1h8RESkKyw+IiLSFRYfERHpCouPiIh0hcVHRES6wuIjIiJdYfEREZGusPiIiEhXWHxERKQrLD4iItIVFh8REekKi4+IiHSFxUdERLrC4iMiIl1h8RERka6w+IiISFdYfEREpCtm0QGIjlMgHMWTdT82/CEEo1EkmkzIsSagIteKJItJdDwiUgAWH2nCpj+I2ede3HV7EZFkWExGmI0GRCQZkagEs9GAhi8y0VCciWxroui4RCSQQZZlWXQIos+xsOrDX10rMBoMyLYmwGzaP4MfiUrY9IcgyTK+qS/E6fw0AUmJSAlYfKRqC6s+/HnGjbz0pENNZQbCUaz7gvhdYxHLj0inWHykWpv+IL5zLuNEasKb0nM/WcCLp4vwb3txsrgMXza17XteIByFdyeEf2ov47QnkQ5xVSep1uxzL4wGwzvv9BKSklB2phaFpZUHPi/JYoLBYIDrJ28cUhKR0rD4SJUC4Sjuur3Itia88/W8whLkFn4Bc0LCAc/8WbY1AbPPvAiEo7GMSUQKxOIjVXqy7kdEkt+7kOUwzCYjIpKMJ+v+Y05GRErH4iNV2vCHYPnE0nvNbDLCsxM6pkREpBYsPlKlYDQKs9HwWT/DZDQgEOFUJ5HesPhIlRJNJkSkz1uQHJVkJJm5mwuR3nDnFlKlHGsCwlFp39clSQJkGZBlyLIMKRoFDAYYje+/qT0r9cOLYIhIe1h8pEoVudaftySLSu8scHn68D6Wfrz35t9rz5dRXl2H8pq6d57/ehuzilxr3DITkTLwBnZSreH5NbjcWziZkXTk565tBdBYkoHuMydjkIyIlIyf8ZF6eZ7i8eLike/Fc96agufVK9QXZcYmFxEpGouPVCcajeL69evwra/g/1xpxroveOjyC4SjyCkuR6bvCX568jDGSYlIiTjVSaoSCAQwNDSE5ORkdHd3w2w2H/p0hg1/EJCB39QXotBqwODgIE6ePImOjo73Ln4hIm1i8ZFqbG9vY2BgAGVlZWhpaYHB8Mt9fJv+IFw/eTH7zPtmRxeT0YDoW+fxNZZkor7ol/P4QqEQhoeHIcsyLl68iISPbHNGRNrA4iNVWF1dxbVr19Dc3IyampoDH/f6BHbPTgiBSBRJZhOyUg8+gV2SJDidTqyurqK/vx9WK1d5Emkdi48U7/Hjx3A6nejp6UFxcXFMXsPlcuHevXu4fPkycnJyYvIaRKQMLD5StJmZGczPz6O/vx9ZWVkxfa2lpSWMj4/DZrOhtLQ0pq9FROLwBnZSJEmSMD4+js3NTXz77bdISUmJ+WuWl5cjNTUVQ0ND8Pl8qK2tjflrElH88R0fKU4oFMLQ0BAsFgt6e3thNsf37zOfz4eBgQEUFxejra3tnUU0RKR+LD5SFKWUztvl29PTA4vFIiQHER0/Fh8pxsuXLzE0NITGxkZFTDO+Pd3a398fl+lWIoo9Fh8pgpIXlsRzgQ0RxR6Lj4RTw60E8bilgojig8VHwkiShImJCaytrani5vHD3kRPRMrG4iMhXm8XBgC9vb2q2S7sQ9umEZE6sPgo7vx+v6o3iH7fRtlEpB4sPoqrjY0NXL16FXV1daivrxcd55NFo1GMjo5ie3sbly9fRnJysuhIRHRILD6Km2fPnsHhcKCzsxPl5eWi4xyL6elpPHr0CFeuXEFmZqboOER0CCw+iou5uTnMzs6ir68PeXl5ouMcq4WFBdy6dQu9vb0oLCwUHYeIPoLFRzElyzImJyfhdrtx5coVpKWliY4UEysrKxgeHkZraytOnz4tOg4RfQCLj2ImEolgeHgY4XAYly5dQmJiouhIMeX1ejEwMICqqio0NzeLjkNEB2DxUUzs7u5icHAQWVlZ6OrqUt3KzU+1t7eHq1evIj09HTabDSbT/sNviUgsFh8dO4/Hg8HBQdTU1OCrr74SHSfuIpEIHA4Hdnd30dfXh6SkJNGRiOgtLD46Vm63G9evX0d7ezsqKytFxxFGlmVMTU1haWkJ/f39yMjIEB2JiP6OxUfHZn5+HtPT07h06RLy8/NFx1GEH3/8EVNTU/w/IVIQFh99NlmWcfv2bSwvL/PdzXvwXTCRsrD46LPw86zD0fvnnkRKwuKjT8YVjEej15WuRErD4qNPwnvWPs3b9zb29fWp5lQKIi1h8dGRcZeSz6OX3WyIlIrFR0fCfSmPj5b3LyVSMhYfHRpPIjh+WjyxgkjpWHz0UTx7Lra0ckYhkVqw+OiDeNp4fKj9VHoiNWHx0YG2t7cxMDCAsrIytLS0wGAwiI6kaaFQCMPDw5BlGRcvXuSKT6IYYfHRe62uruLatWtobm5GTU2N6Di6IUkSnE4nVldX0d/fD6vVKjoSkeaw+Gifx48fw+l0oqenB8XFxaLj6JLL5cK9e/dw+fJl5OTkiI5DpCksPnrHzMwM5ufn0d/fj6ysLNFxdG1paQnj4+Ow2WwoLS0VHYdIM7hSgQD8PMU2Pj6Ozc1NfPvtt0hJSREdSffKy8uRmpqKoaEh+Hw+1NbWio5EpAl8x0cIhUIYGhqCxWJBb28vV24qjM/nw8DAAIqLi9HW1sZFRkSficWnc7yoqsPbf5z09PTAYrGIjkSkWiw+HXv58iWGhobQ2NjIaTQVeHs6ur+/n9PRRJ+IxadTXDihXlyARPR5WHw6xKXy6sdbTog+HYtPRyRJwsTEBNbW1nhztAZwkwGiT8Pi04nX22EBQG9vL7fD0ghuK0d0dCw+HeAGyNrGjcSJjobFp3E88kYfeHQU0eGx+DSMh5zqDw8LJvo4Fp9Gzc3NYXZ2Fn19fcjLyxMdh+JoYWEBt27dQm9vLwoLC0XHIVIcFp/GyLKMyclJuN1uXLlyBWlpaaIjkQArKysYHh5Ga2srTp8+LToOkaKw+DQkEolgeHgY4XAYly5dQmJiouhIJJDX68XAwACqqqrQ3NwsOg6RYrD4NGJ3dxeDg4PIyspCV1cXV24SAGBvbw9Xr15Feno6bDYbTCaT6EhEwrH4NMDj8WBwcBA1NTX46quvRMchhYlEInA4HNjd3UVfXx+SkpJERyISisWncm63G9evX0d7ezsqKytFxyGFkmUZt2/fxvLyMvr7+5GRkSE6EpEwLD4Vm5+fx/T0NC5duoT8/HzRcUgFOGaIWHyqxL/e6XNwloD0jsWnMvy8ho4DPxcmPWPxqQhX6NFx4kpg0isWn0rwniyKhbfv/ezr6+OpHaQLLD4V4C4cFEvc7Yf0hsWncNx3keKF+7uSXrD4FIw77VO88UQP0gMWnwLxbDUS6fUZjrW1tWhoaBAdh+jYsfgU5vVp2ikpKbDb7TxNm4Tw+/0YHBzEyZMn0dHRwRWfpCksPgXZ3t7GwMAAysrK0NLSAoPBIDoS6Vg4HMb3338PWZZx8eJFrvgkzWDxKcTq6iquXbuG5uZm1NTUiI5DBACQJAlOpxOrq6vo7++H1WoVHYnos7H4FODx48dwOp3o6elBcXGx6DhE+7hcLty7dw+XL19GTk6O6DhEn4XFJ9jMzAzm5+fR39+PrKws0XGIDrS0tITx8XHYbDaUlpaKjkP0ybhyQhBJkjA+Po7NzU18++23SElJER2J6IPKy8uRmpqKoaEh+Hw+1NbWio5E9En4jk+AUCiEoaEhWCwW9Pb2cuUmqYrP58PAwACKi4vR1tbGRVikOiy+OONFg7Tg7T/eenp6YLFYREciOjQWXxy9fPkSQ0NDaGxs5DQRqd7b0/X9/f2crifVYPHFCRcGkFZxgRapDYsvDrgUnLRucXERExMTvCWHVIHFF0OSJGFiYgJra2u8+Zc0j5swkFqw+GIkFApheHgYANDb28vtnkgXuO0eqQGLLwa4wS/p2euN1pOTk9Hd3c3bdUhxWHzH7PWRLnV1daivrxcdh0gIHq1FSsbiO0ZPnz7F6OgoD/Ek+rvXhyn39/fjxIkTouMQAWDxHZu5uTnMzs6ir68PeXl5ouMQKcbCwgJu3bqF3t5eFBYWio5DxOL7XLIsY3JyEm63G1euXEFaWproSESKs7KyguHhYbS2tuL06dOi45DOsfg+QyQSwfDwMMLhMPr6+rhyk+gDvF4vBgcHUVlZiebmZtFxSMdYfJ9od3cXg4ODyMrKQldXF1duEh3C3t4erl69ivT0dNhsNphMJtGRSIdYfJ/A4/FgcHAQNTU1+Oqrr0THIVKVSCQCh8OB3d1d9PX1ISkpSXQk0hkW3xG53W5cv34d7e3tqKysFB2HSJVkWcbU1BSWlpbQ39+PjIwM0ZFIR1h8RzA/P4/p6WlcunQJ+fn5ouMQqd6PP/6Iqakp/k5RXLH4DkGWZdy+fRvLy8v865TomHEWheKNxfcRkUgEIyMj2Nvb4+cRRDHy+nPz6upqnDt3TnQc0jgW3wdwBRpR/HClNMULi+8AXq8XAwMDqKqq4j1HRHESiURw/fp1hEIhXLp0CYmJiaIjkQax+N6Du0wQiSPLMm7evInnz59zNySKCRbfr3BfQSJluH//PmZmZrj/LR07Ft9bXu8kf+XKFWRmZoqOQ6R7z549g8PhwIULF1BRUSE6DmkEiw88O4xIyV6fcVlbW4uGhgbRcUgDdF98r0+LTklJgd1u52nRRAq0s7ODgYEBnDx5Eh0dHVzxSZ9F18W3tbWFwcFBlJWVoaWlBQaDQXQkIjpAOBzG999/D1mWcfHiRZ6GQp9Mt8W3urqKa9euobm5GTU1NaLjENEhSJIEp9OJ1dVV9Pf3w2q1io5EKqTL4nv8+DGcTid6enpQXFwsOg4RHZHL5cK9e/dw+fJl5OTkiI5DKqO74puZmcH8/Dz6+/uRlZUlOg4RfaKlpSWMj4/DZrOhtLRUdBxSEd2s5JAkCWNjY/B4PPj222+RkpIiOhIRfYby8nKkpqZiaGgIPp8PtbW1oiORSujiHV8oFMLQ0BAsFgt6e3u5cpNIQ3w+HwYHB1FUVIS2tjYuUqOP0mTxBYNBWCwWGI1G+Hw+DAwMoLi4mL8URBoVCoVw7do1mM1m9PT0wGKxIBwOw2Aw8A9d2keTxfdf//VfyM3Nxfnz53Ht2jU0NjZyGoRI4yRJwvj4ODY3N9HT04P/+Z//walTp9Db2ys6GimM5opvbW0N//Ef/4HNzU3k5eXh97//PUpKSkTHIqI4uXPnDr777jvIsozc3Fz84Q9/4D1/9A7VzAEEwlE8Wfdjwx9CMBpFosmEHGsCKnKtSLL8ck7e9PQ0Njc3EQgEsLW1hZ2dHYGpiSjePB4PgsEggsEgZFnGwsLCvhmfw15PSJsUX3yb/iBmn3tx1+1FRJJhMRlhNhoQkWREohLMRgMavshEQ3EmkgwR/PGPf4Tf70dVVRUSEhLw8OFD3qBOpBPhcBiLi4vIycnBzs4OFhYW8N///d9viu8o15NsK88C1CpFT3UurPrwV9cKjAYDsq0JMJv2788XiUrY9IcgyTIqE7xw/L8/4sqVK6iqqkJBQQGSkpIEJCcikXw+H1ZWVuByuTA2NoZ/+7d/w+qu4UjXk2/qC3E6n2cBapFii29h1Yc/z7iRl550qKmHQDiKdV8Qv2ss4mAlonfwekJvU2TxbfqD+M65jBOpCW8GqRSN4uHdKXjWVxEJhZCcasWps43IPvnLYbGBcBTenRD+qb2M0xREBOD91xMAuD89gVfra4hGIkhISkZpVQ0KyyrffJ/XE+1S5Gd8s8+9MBoM7wxSWZaRlJyKcxcuIiklFZtrK5i7fQMtPf+A5NSfN6pNsphgMBjg+smL7jMnRcUnIgV53/UEAMpO16Lmq69hNJmw49vCnfFhpGVmIS3z560MeT3RLsUdahUIR3HX7UW29d3lxyazGeU1dUhOtcJgMCAnvwhJKanwbXneeVy2NQGzz7wIhKPxjE1ECnTQ9QQAUtMzYDT9UoYGA7C343/nMbyeaJPi3vE9WfcjIsnv/eD5baFAAHs7PqSmZbzzdbPJiIgk48m6H18WZhzwbCLSg49dTx7OTuHFsyeQolGkZZ5A1smCd77P64k2Ka74NvwhWD5SepIk4f70BPK/qNhXfMDPg9WzE4pVRCJSiY9dT840nsfphmZsedbxan0NRuP+hS+8nmiP4qY6g9EozMaD99OUZRkPfnDCYDTidEPzex9jMhoQiHBqgkjvPnY9AQCDwYDM7DwE9/bw09Kjfd/n9UR7FFd8iSYTItLBC03n79xEKBhEXUsnjMb3x49KMpLM3H2BSO8+dj15mwwZezu+fV/n9UR7FFd8OdYEhKPSe7/348xt7Pq3Uf91F0wf2HE9EpWQlcq9+Yj07qDrSSgQwJr7KSKRMGRZxubaC6w9X8aJ3Px9j+X1RHsU9xlfRa715y2EotI7H0gHdnewsvwYRpMRN/725zdfr/6qFflflL359+tthypyrfGMTUQKdND1BAbgp6VH+HH2NiDLSEpJxen6JuQWFL/zfF5PtEmRN7APz6/B5d7CyYyjbze2thVAY0kG77shIgC8ntB+ipvqBIDGLzIhyfKR750JhKOQZRn1RZmxCUZEqsPrCf2aIosv25qIb+oLse4LHnqwvt5b7zf1hdxeiIjeeH09WfH4sfpy46OP9/l88Gz5eD3RMEUWHwCczk/D7xqL8GonhLWtACIHLHiJRCWsbu3BuxPihrJE9F6n89OQH3iGF698H72evPDu4oe5H/FNbR6vJxqlyM/43rbpD8L1kxezz7xvdmAwGQ2IvnV+VmNJJuqLeH4WEb3fgwcP8PDhQ1y42I+5le2PXk98Tx8gK8WCCxcuiI5OMaD44nvt9YnJnp0QApEokswmZKXyxGQi+rDt7W385S9/wW9/+1tkZmYC+Pj1JBQK4U9/+hO6urpQXFz84Rcg1VFN8RERHZUsy/jrX/+KsrIy1NfXH+m5brcbY2Nj+Md//EckJPA+Pi1R7Gd8RESfa25uDgBQV1d35OcWFxejpKQETqfzuGORYCw+ItIkr9eLmZkZ2O12GAwf3q/zIK2trVhdXcXTp0+POR2JxOIjIs2RJAkOhwNNTU1IT0//5J9jsVhgs9kwPj6OQCBwjAlJJBYfEWmOy+WCxWLBl19++dk/q6CgAKdOncLExMQxJCMlYPERkaZ4PB64XC7YbLZPnuL8tfPnz2NzcxNPnjw5lp9HYrH4iEgzJEnCyMgIWltbYbUe38bSZrMZdrsdExMT2NvbO7afS2Kw+IhIM+7cuYPU1FScOXPm2H92Xl4ezpw5g7GxsWP/2RRfLD4i0oT19XU8ePAAXV1dMXuNpqYm+Hw+LCwsxOw1KPZYfESketFoFA6HA+3t7UhJSYnZ65hMJtjtdty8eRM7Ozsxex2KLRYfEane9PQ0MjMzUVlZGfPXysnJQW1tLUZHR2P+WhQbLD4iUrW1tTU8evQorhtKNzY2IhAIYH5+Pm6vSceHxUdEqhWJROBwONDR0YHk5OS4va7RaER3dzempqbg8/ni9rp0PFh8RKRat2/fRm5uLsrLy+P+2idOnEBDQwMcDge417+6sPiISJVWVlawtLSEjo4OYRnq6+shSRLu378vLAMdHYuPiFQnHA5jdHQUnZ2dSEwUdwC1wWCA3W7HnTt3sLW1JSwHHQ2Lj4hUZ3JyEkVFRSgpKREdBRkZGTh37hynPFWExUdEqvL8+XO43W58/fXXoqO8cfbsWZhMJrhcLtFR6BBYfESkGsFgEGNjY7DZbIo6Fd1gMMBms+Hu3bvweDyi49BHsPiISDWcTifKyspQVFQkOso+aWlpaGlpgcPhgCRJouPQB7D4iEgVlpeXsba2htbWVtFRDlRdXY3k5GTMzs6KjkIfwOIjIsULBAK4ceMG7HY7zGaz6Dgf1NXVhbm5OWxsbIiOQgdg8RGR4t24cQOVlZXIz88XHeWjUlNT0dbWBofDgWg0KjoOvQeLj4gUbXFxER6PB+fPnxcd5dCqqqqQnp6OH374QXQUeg8WHxEp1u7uLpxOJ7q7u2EymUTHOZLOzk48fPgQL1++FB2FfoXFR0SKNTY2hurqauTm5oqOcmTJycno6OjAyMgIIpGI6Dj0FhYfESnSwsIC/H4/mpqaREf5ZBUVFcjJycHU1JToKPQWFh8RKY7f78fNmzfR3d0No1Hdl6mOjg4sLi7ixYsXoqPQ36l7RBGRJo2NjaGurg7Z2dmio3y2pKQkdHZ2wuFwIBwOi45DYPERkcI8ePAAwWAQDQ0NoqMcm9LSUhQUFODWrVuioxBYfESkINvb25ientbEFOevtbe349mzZ3C73aKj6J62RhYRqZYsyxgdHUVjYyMyMzNFxzl2CQkJ6OrqwtjYGEKhkOg4usbiIyJFmJubgyzLqKurEx0lZoqLi1FSUgKn0yk6iq6x+IhIOK/Xi5mZGdjtdhgMBtFxYqq1tRWrq6t4+vSp6Ci6xeIjIqEkSYLD4UBTUxPS09NFx4k5i8UCm82G8fFxBAIB0XF0icVHREK5XC5YLBZ8+eWXoqPETUFBAU6dOoWJiQnRUXSJxUdEwng8HrhcLthsNs1Pcf7a+fPnsbm5iSdPnoiOojssPiIS4vUUZ0tLC6xWq+g4cWc2m2G32zExMYG9vT3RcXSFxUdEQty5cwcpKSmorq4WHUWYvLw8nDlzBuPj46Kj6AqLj4jibmNjAw8ePEBXV5foKMI1NTVhe3sbjx49Eh1FN1h8RBRX0WgUIyMjaG9vR0pKiug4wplMJtjtdkxOTmJnZ0d0HF1g8RFRXE1PTyMzMxOVlZWioyhGTk4OamtrMTo6KjqKLrD4iChu1tbWsLCwgAsXLoiOojiNjY0IBAKYn58XHUXzWHxEFBeRSAQOhwMXLlxAcnKy6DiKYzQa0d3djampKfh8PtFxNI3FR0Rxcfv2beTm5qK8vFx0FMU6ceIEGhoaMDo6ClmWRcfRLBYfEcXcysoKlpaW0NHRITqK4tXX1yMajeL+/fuio2gWi4+IYiocDmN0dBSdnZ1ITEwUHUfxDAYD7HY77ty5g62tLdFxNInFR0QxNTk5icLCQpSUlIiOohoZGRk4d+4cHA4HpzxjgMVHRDHz/PlzuN1utLW1iY6iOmfPnoXJZILL5RIdRXNYfEQUE8FgEGNjY7DZbEhISBAdR3UMBgNsNhvu3r2LV69eiY6jKSw+IooJp9OJsrIyFBUViY6iWmlpaWhpacHIyAgkSRIdRzNYfER07JaXl7G2tobW1lbRUVSvuroaycnJmJ2dFR1FM1h8RHSsAoEAbty4AbvdDrPZLDqOJnR1dWFubg4bGxuio2gCi4+IjtWNGzdQWVmJ/Px80VE0IzU1FW1tbXA4HIhGo6LjqB6Lj4iOzeLiIjweD5qbm0VH0Zyqqiqkp6fjhx9+EB1F9Vh8RHQsdnd34XQ6OcUZQ52dnXj48CFevnwpOoqqsfiI6FiMjY2huroaeXl5oqNoVnJyMjo6OjAyMoJIJCI6jmqx+Ijosy0sLMDv96OpqUl0FM2rqKhATk4OpqamREdRLRYfEX0Wv9+Pmzdvoru7G0YjLynx0NHRgcXFRbx48UJ0FFXiKCWizzI2Noa6ujpkZ2eLjqIbSUlJ6OzshMPhQDgcFh1HdVh8RPTJHjx4gGAwiIaGBtFRdKe0tBQFBQW4deuW6Ciqw+Ijok+yvb2N6elpTnEK1N7ejmfPnsHtdouOoiocrUR0ZLIsY3R0FI2NjcjMzBQdR7cSEhLQ1dWFsbExhEIh0XFUg8VHREc2NzcHWZZRV1cnOoruFRcXo6SkBE6nU3QU1WDxEdGReL1ezMzMwG63w2AwiI5DAFpbW7G6uoqnT5+KjqIKLD4iOjRJkuBwONDU1IT09HTRcejvLBYLbDYbxsfHEQgERMdRPBYfER2ay+WC2WzGl19+KToK/UpBQQFOnTqFiYkJ0VEUj8VHRIfi8Xjgcrk4xalg58+fx+bmJp48eSI6iqKx+Ijoo15Pcba0tMBqtYqOQwcwm82w2+2YmJjA3t6e6DiKxeIjoo+6c+cOUlJSUF1dLToKfUReXh7OnDmD8fFx0VEUi8VHRB+0sbGBBw8eoKurS3QUOqSmpiZsb2/j0aNHoqMoEouPiA4UjUYxMjKC9vZ2pKSkiI5Dh2QymWC32zE5OYmdnR3RcRSHxUdEB5qenkZmZiYqKytFR6EjysnJQW1tLUZHR0VHURwWHxG919raGhYWFnDhwgXRUegTNTY2IhAIYH5+XnQURWHxEdE+kUgEDocDFy5cQHJysug49ImMRiO6u7sxNTUFn88nOo5isPiIaJ/bt28jNzcX5eXloqPQZzpx4gQaGhowOjoKWZZFx1EEFh8RvWNlZQVLS0vo6OgQHYWOSX19PaLRKO7fvy86iiKw+IjojXA4jNHRUXR2diIxMVF0HDomBoMBdrsdd+7cwdbWlug4wrH4iOiNyclJFBUVoaSkRHQUOmYZGRk4d+4cHA6H7qc8WXxEBAB4/vw53G43vv76a9FRKEbOnj0Lk8kEl8slOopQLD4iQjAYxNjYGGw2GxISEkTHoRgxGAyw2Wy4e/cuPB6P6DjCsPiICE6nE2VlZSgqKhIdhWIsLS0NLS0tcDgckCRJdBwhWHxEOre8vIy1tTW0traKjkJxUl1djeTkZMzOzoqOIgSLj0jHAoEAbty4AbvdDrPZLDoOxVFXVxfm5uawsbEhOkrcsfiIdOzGjRuorKxEfn6+6CgUZ6mpqWhra4PD4UA0GhUdJ65YfEQ6tbi4CI/Hg/Pnz4uOQoJUVVUhPT0dP/zwg+goccXiI9Kh3d1dOJ1OdHd3w2QyiY5DAnV2duLhw4d4+fKl6Chxw+Ij0qGxsTFUV1cjNzdXdBQSLDk5GR0dHRgZGUEkEhEdJy5YfEQ6s7CwAL/fj6amJtFRSCEqKiqQk5ODqakp0VHigsVHpCN+vx83b95Ed3c3jEb++tMvOjo6sLi4iBcvXoiOEnMc+UQ6MjY2hrq6OmRnZ4uOQgqTlJSEzs5OOBwOhMNh0XFiisVHpBMPHjxAMBhEQ0OD6CikUKWlpSgoKMCtW7dER4kpFh+RDmxvb2N6eppTnPRR7e3tePbsGdxut+goMcPfACKNk2UZo6OjaGxsRGZmpug4pHAJCQno6urC2NgYQqGQ6DgxweIj0ri5uTnIsoy6ujrRUUgliouLUVJSAqfTKTpKTLD4iDRod3cXAOD1ejEzMwO73Q6DwSA4FalJa2srVldX8fTpUwC/jCktMMh6P4qXSGNkWca///u/o6qqCqFQCLW1tTh79qzoWKRCL168wNDQEIqKijA5OYl/+Zd/0cR0ObdjJ9KYnZ0dbG1t4W9/+xsikQiam5tFRyKVMplMmJubw9WrV1FaWoqtrS1NFB+nOok0Znt7G8FgEJFIBNnZ2fjuu+90tQ8jHY9QKITvvvsOwWAQqamp2Nrawvb2tuhYx4LFR6QxXq8XCwsLMJvNqKiowO9//3vk5eWJjkUqk5CQgH/+539Ga2srkpOTsbi4iJWVFdGxjgU/4yNSmUA4iifrfmz4QwhGo0g0mZBjTUBFrhVJFhP+9Kc/4X//93/xr//6rzh79izv26PPtry8jP/8z/9ETk4O/vCHPwD4+DhUMhYfkUps+oOYfe7FXbcXEUmGxWSE2WhARJIRiUowGw1o+CITp7MTkZOWhKSkJNGRSUOi0Sh8Ph+i5uRDjcOG4kxkWxNFx34vFh+RCiys+vBX1wqMBgOyrQkwm/a/i4tEJWz6Q5BkGd/UF+J0fpqApKRlWhmHLD4ihVtY9eHPM27kpScdagopEI5i3RfE7xqLFHnRIXXS0jhk8REp2KY/iO+cyziRmvDei82ufxu3r/8NuYVf4Gxzx5uvB8JReHdC+Kf2MsVON5F6HDQO74x/j+1XGwB+3hwhMTkFbZe+efN9pY5D3sdHpGCzz70wGgwH/oW9cHcaaZn7jxhKsphgMBjg+smL7jMnYx2TNO5D4/B0fTMKyyrf+zyljkMu9yJSqEA4irtuL7KtCe/9/pr7KcyWBGTl5r/3+9nWBMw+8yIQjsYyJmncx8bhxyhxHLL4iBTqybofEUl+/wKCcAhP5l2orDt34PPNJiMikown6/5YxiSN+9A4BIDFB3cx/rf/i+nRIbxaX9v3fSWOQ051EinUhj8EywEXmyfzLhSUViApOeWDP8NsMsKzo82jZSg+PjQOT51tRGp6BowGI9Z+egrXzVGc776CFOu7i1mUNg75jo9IoYLRKMzG/Scq+LZe4dX6Gkoqaz76M0xGAwIR5UwxkfocNA4BICMrB2azBUaTCQUlFcjIysHm2v7dXZQ2DvmOj0ihEk0mRKT9i65fra9hb8ePicG/AACikTAAGVMjAzjffeWdx0YlGUlmZe+iQcp20Dh8rwOOvlLaOGTxESlUjjUB4ai07+tFZZU4WVz65t/PHs0jsLuDM43n9z02EpWQlfppixKIgIPHYSQcwpZnEydy8gCDAS9/egbvxkucrm/a/1iFjUMWH5FCVeRaf94KKiq9s7DAZDbDZP7lV/fnqSYjEhLf3aLs9fZRFbnWuGUm7TloHEqShCfzd7Hr2wYMBqSmpaOutQsp1vR3nq/Eccgb2IkUbHh+DS73Fk5mHH3fzbWtABpLMhR1/xSpk9bGIRe3EClY4xeZkGT5yPdABcJRyLKM+qLM2AQjXdHaOGTxESlYtjUR39QXYt0XPPRF5/Ueib+pL1TUNlGkXlobh5zqJFKBw+6Kv+EPAjLwG4Xuik/qppVxyOIjUolNfxCun7yYfeZ9s5OGyWhA9K1z0BpLMlFfpNxz0Ej9tDAOWXxEKvP65GvPTgiBSBRJZhOyUtVx8jVph5rHIYuPiIh0hYtbiIhIV1h8RESkKyw+IiLSFRYfERHpCouPiIh0hcVHRES6wuIjIiJdYfEREZGusPiIiEhXWHxERKQrLD4iItIVFh8REekKi4+IiHSFxUdERLrC4iMiIl1h8RERka6w+IiISFdYfEREpCssPiIi0hUWHxER6QqLj4iIdOX/A9clE1X5IKntAAAAAElFTkSuQmCC", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from EoN import hierarchy_pos\n", "\n", "def draw_tree(tree):\n", " G = nx.DiGraph()\n", " add_edges(tree, G)\n", " pos = hierarchy_pos(G)\n", " labels = {1:1,2:2,3:3,4:4,5:5}\n", " # get_labels(tree, labels)\n", " nx.draw(G, pos, labels=labels, alpha=0.4)\n", "\n", "draw_tree(t)" ] }, { "cell_type": "markdown", "metadata": { "id": "WMUbIIbN4XAu" }, "source": [ "## Tree traversal \n", "This is the question of how to visit each of the nodes in a tree **exactly once.**\n", "1. Visit current node and **process node** check if node is a leaf or some other stopping condition. \n", "2. Iterate across branches and recurse down. \n", " Often you can use `for ` loop or `list` comprehensions for branch iterations and recursion to go down.\n", "3. Combination of recursive call returns are used to determine the final result of your probelm. ***ex: find sum of all labels in a tree -- it is not sufficient to just use recursive call, but must also process the label values***. \n", "\n", "The above functions are okay, but we can place all of the abstraction into a class. This allows for easy passage of data and storage. It will be a proper *ADT* in the eyes of *the Greater Will*.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "wJjuOEHY11yU" }, "outputs": [], "source": [ "class Tree: \n", " def __init__(s, label, branches= []):\n", " s.label = label\n", " s.branches = branches\n", " def is_leaf(s):\n", " return not s.branches\n", " def __repr__(self):\n", " return f\"[ {self.label}, {', '.join([ b.__repr__() for b in self.branches ])} END ]\"\n" ] }, { "cell_type": "markdown", "metadata": { "id": "bNrbEpGE6kiF" }, "source": [ "Following are several examples which you need to solve in class. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "hRFRKYn26jz_" }, "outputs": [], "source": [ "def count_leaves(t):\n", " '''Write a function that counts the number of leaves in a given Tree t'''\n", " if t.is_leaf():\n", " return 1\n", " else:\n", " c = 0\n", " for n in t.branches:\n", " c += count_leaves(n)\n", " return c\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "rGC1q4LV13NT", "outputId": "b1311681-fa7a-440f-f12c-184233686ed1" }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t = Tree(1, [Tree(2), Tree(3, [Tree(4), Tree(5)])])\n", "count_leaves(t) == 3" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "YMbFu3zw2F3r", "outputId": "24ac5e26-87f4-4294-ab16-ab469091caa1" }, "outputs": [ { "data": { "text/plain": [ "[1, 2, [3]]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def list_of_leaves(t):\n", " '''Returns a list of leaves of a tree '''\n", " if t.is_leaf():\n", " return [t.label]\n", " else:\n", " return sum([ list_of_leaves(b) for b in t.branches ], [])\n", "#HINT:\n", "sum([ [1], [2, [3]]],[])" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "FjKnywx-9VBF", "outputId": "02391553-29a9-4f1d-e9d1-5e7557a96765" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 4, 5]\n" ] }, { "data": { "text/plain": [ "True" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print(list_of_leaves(t))\n", "list_of_leaves(t) == [2,4,5]" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "BvZbzWH49_pl" }, "outputs": [], "source": [ "def fib_tree(n):\n", " if n == 0 or n == 1:\n", " return Tree(n)\n", " s = Tree(n, [fib_tree(n-1), fib_tree(n-2)])\n", " s.label = sum([b.label for b in s.branches])\n", " return s" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "vjYVr2v1_1e0", "outputId": "09fb48fa-632c-4c44-898b-55643b173e1b" }, "outputs": [ { "data": { "text/plain": [ "[ 5, [ 3, [ 2, [ 1, [ 1, END ], [ 0, END ] END ], [ 1, END ] END ], [ 1, [ 1, END ], [ 0, END ] END ] END ], [ 2, [ 1, [ 1, END ], [ 0, END ] END ], [ 1, END ] END ] END ]" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fibt = fib_tree(5)\n", "fibt\n", "# Fix the labeling system that is hardcoded above to dynamically given level\n", "# labels to this tree so it can be plotted - get_labels(t)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "HlA744R9_4P0" }, "outputs": [], "source": [ "def counting_paths(t, total): # reduce total by current tree.label each time\n", " '''Count the # of paths from root to any node in the tree for which the labels\n", " sum up to the total'''\n", " if t.label == total: \n", " return 1\n", " else:\n", " return sum([ counting_paths(b, total - t.label) for b in t.branches])" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "MiYhj6CZxWcW", "outputId": "276a9307-33dc-45c3-cb35-46d6d37d13be" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "2\n", "2\n", "3\n", "1\n", "0\n", "0\n" ] } ], "source": [ "fibt = fib_tree(5)\n", "c = counting_paths(fibt, 12)\n", "assert c == 1\n", "print(c)\n", "fibt = fib_tree(5)\n", "c = counting_paths(fibt, 11)\n", "assert c == 2\n", "print(c)\n", "c = counting_paths(fibt, 9)\n", "assert c == 2\n", "print(c)\n", "fibt = fib_tree(5)\n", "c = counting_paths(fibt, 8)\n", "assert c == 3\n", "print(c)\n", "c = counting_paths(fibt, 5)\n", "assert c == 1\n", "print(c)\n", "c = counting_paths(fibt, 4)\n", "assert c == 0\n", "print(c)\n", "c = counting_paths(fibt, 400)\n", "assert c == 0\n", "print(c)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "TtRqJUivASO1" }, "outputs": [], "source": [ "def tripler(t):\n", " ''' Triple the value of the labels of each node in the tree'''\n", " t.label *= 3\n", " if t.is_leaf():\n", " return\n", " else:\n", " [ tripler(b) for b in t.branches ]" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "LuUh4r4zBWQ9", "outputId": "819b7853-8021-4f8e-a7d4-37f91196e45d" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 5, [ 3, [ 2, [ 1, [ 1, END ], [ 0, END ] END ], [ 1, END ] END ], [ 1, [ 1, END ], [ 0, END ] END ] END ], [ 2, [ 1, [ 1, END ], [ 0, END ] END ], [ 1, END ] END ] END ]\n", "[ 15, [ 9, [ 6, [ 3, [ 3, END ], [ 0, END ] END ], [ 3, END ] END ], [ 3, [ 3, END ], [ 0, END ] END ] END ], [ 6, [ 3, [ 3, END ], [ 0, END ] END ], [ 3, END ] END ] END ]\n" ] } ], "source": [ "fibt = fib_tree(5)\n", "print(fibt)\n", "tripler(fibt)\n", "print(fibt)" ] } ], "metadata": { "colab": { "provenance": [] }, "kernelspec": { "display_name": "Python 3.11.2 64-bit", "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.11.2" }, "vscode": { "interpreter": { "hash": "b0fa6594d8f4cbf19f97940f81e996739fb7646882a419484c72d19e05852a7e" } } }, "nbformat": 4, "nbformat_minor": 0 }