Ternary Search Tree Data Structure Implements using Python

ternary-search-tree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, char):\n",
    "        self.char = char\n",
    "        self.left = self.middle = self.right = None\n",
    "        self.value = None\n",
    "        \n",
    "class TernarySearchTree(object):\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return 'TernarySearchTree()'\n",
    "        \n",
    "    def put(self, key, value):\n",
    "        self.root = self.recursive(key, value)(self.root, 0)\n",
    "        \n",
    "    def get(self, key):\n",
    "        node = self.recursive(key)(self.root, 0)\n",
    "        if node:\n",
    "            return node.value\n",
    "        return -1\n",
    "        \n",
    "    def recursive(self, key, value=None):\n",
    "        \n",
    "        def putter(node, index): \n",
    "            char = key[index]\n",
    "            \n",
    "            if node is None:\n",
    "                node = Node(char)         \n",
    "            if char < node.char:\n",
    "                node.left = putter(node.left, index)\n",
    "            elif char > node.char:\n",
    "                node.right = putter(node.right, index)\n",
    "            elif index < len(key) - 1:\n",
    "                node.middle = putter(node.middle, index+1)\n",
    "            else:\n",
    "                node.value = value\n",
    "                            \n",
    "            return node\n",
    "        \n",
    "        def getter(node, index):\n",
    "            char = key[index]\n",
    "            \n",
    "            if node is None:\n",
    "                return None\n",
    "            \n",
    "            if char < node.char:\n",
    "                return getter(node.left, index)\n",
    "            elif char > node.char:\n",
    "                return getter(node.right, index)\n",
    "            elif index < len(key) - 1:\n",
    "                return getter(node.middle, index+1)\n",
    "            else:\n",
    "                return node\n",
    "        \n",
    "        if value:\n",
    "            return putter\n",
    "        else:\n",
    "            return getter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "tst = TernarySearchTree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "tst.put('apple', 1)\n",
    "tst.put('admin', 2)\n",
    "tst.put('cute', 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tst.get('cute')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tst.get('orange')"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}