removing problem statements

1 files changed, 202 insertions, 7 deletions

diff --git a/Data_Structures_and_Algorithms_in_Java/ch10.ipynb b/Data_Structures_and_Algorithms_in_Java/ch10.ipynb
index cf44793a..86853ad0 100644
--- a/Data_Structures_and_Algorithms_in_Java/ch10.ipynb
+++ b/Data_Structures_and_Algorithms_in_Java/ch10.ipynb
@@ -1,6 +1,7 @@
 {
  "metadata": {
-  "name": "ch10"
+  "name": "",
+  "signature": "sha256:8fd742e3911255005d5cc80d3e792a10aed91d6e12fc125e66cc3c416b974be7"
  },
  "nbformat": 3,
  "nbformat_minor": 0,
@@ -11,27 +12,221 @@
      "cell_type": "heading",
      "level": 1,
      "metadata": {},
-     "source": "Chapter 10 : 2-3-4 Trees and External Storage"
+     "source": [
+      "Chapter 10 : 2-3-4 Trees and External Storage"
+     ]
     },
     {
      "cell_type": "heading",
      "level": 3,
      "metadata": {},
-     "source": "Example 10.1  Page No : 478"
+     "source": [
+      "Example 10.1  Page No : 478"
+     ]
     },
     {
      "cell_type": "code",
      "collapsed": false,
-     "input": "'''\nexample 10.1\ndemonstrates 234 tree\n'''\nclass DataItem:\n    def __init__(self,dd):\n        self.dData = dd\n\n    def displayItem(self):\n        print '/' ,self.dData\n\nclass Node:\n    def __init__(self):\n        self.ORDER = 4\n        self.numItems = 0\n        self.parent = None\n        self.childArray = [None,None,None,None]\n        self.itemArray = [None,None,None]\n\n    def connectChild(self,childNum,child):\n        self.childArray[childNum] = child\n        if(child != None):\n            child.parent = self\n\n    def disconnectChild(self,childNum):\n        tempNode = self.childArray[childNum]\n        self.childArray[childNum] = None\n        return tempNode\n\n    def getChild(self,childNum):\n        return self.childArray[childNum]\n\n    def getParent(self):\n        return self.parent\n\n    def isLeaf(self):\n        if self.childArray[0]==None:\n            return True \n        return False    \n\n    def getNumItems(self):\n        return self.numItems\n\n    def getItem(self,index):         # get DataItem at index\n        return self.itemArray[index] \n\n    def isFull(self):\n        if self.numItems==self.ORDER-1:\n            return True\n        return False\n\n    def findItem(self,key): # return index of # item (within node)\n        for j in range(self.ORDER-1): \n            if(self.itemArray[j] == None):\n                break\n            elif(self.itemArray[j].dData == key):\n                return j\n        return -1\n\n    def insertItem(self,newItem):\n        #assumes node is not full\n        self.numItems += 1 # will add new item\n        newKey = newItem.dData # key of new item\n        j = self.ORDER - 2\n        while j>=0:\n            if(self.itemArray[j] == None):\n                continue\n            else:\n                itsKey = self.itemArray[j].dData\n                if(newKey < itsKey):\n                    self.itemArray[j+1] = self.itemArray[j]\n                else:\n                    self.itemArray[j+1] = newItem\n                    return j+1 # return index to\n            j -= 1\n\n        self.itemArray[0] = newItem # insert new item\n        return 0\n\n    def removeItem(self): # remove largest item\n        temp = self.itemArray[self.numItems-1] # save item\n        self.itemArray[self.numItems-1] = None # disconnect it\n        self.numItems -= 1 # one less item\n        return temp # return item\n\n    def displayNode(self):\n        for j in range(self.numItems):\n            self.itemArray[j].displayItem()\n        print ''\n\nclass Tree234:\n    def __init__(self):\n        self.root = Node() # make root node\n\n    def find(self,key):\n        curNode = self.root\n        childNumber = 0\n        while(True):\n            childNumber=curNode.findItem(key) \n            if(childNumber != -1):\n                return childNumber # found it\n            elif( curNode.isLeaf() ):\n                return -1 # cant find it\n            else: # search deeper\n                curNode = getNextChild(curNode, key)\n\n    def insert(self,dValue):\n        curNode = self.root\n        tempItem = DataItem(dValue)\n        while(True):\n            if( curNode.isFull() ):\n                split(curNode)\n                curNode = curNode.getParent()\n                curNode = getNextChild(curNode, dValue)\n            elif( curNode.isLeaf() ): # if node is leaf,\n                break\n            else:\n                curNode = getNextChild(curNode, dValue)\n        curNode.insertItem(tempItem)\n\n    def split(self,thisNode): # split the node\n        # assumes node is full\n        itemC = thisNode.removeItem()         # remove items from\n        itemB = thisNode.removeItem()         # this node\n        child2 = thisNode.disconnectChild(2) # remove children\n        child3 = thisNode.disconnectChild(3) # from this nodeJava Code for a 2-3-4 Tree\n        newRight = Node() # make new node\n        if(thisNode==self.root):\n            self.root = Node()\n            parent = self.root\n            self.root.connectChild(0, thisNode)\n        else:\n            parent = thisNode.getParent()\n        itemIndex = parent.insertItem(itemB) # item B to parent\n        n = parent.getNumItems()\n        j = n-1\n        while j > itemIndex:\n            temp = parent.disconnectChild(j) # one child\n            parent.connectChild(j+1, temp)\n            j -= 1\n\n        parent.connectChild(itemIndex+1, newRight) # deal with newRight\n        newRight.insertItem(itemC) # item C to newRight\n        newRight.connectChild(0, child2) # connect to 0 and 1\n        newRight.connectChild(1, child3) # on newRight\n\n    def getNextChild(self,theNode,theValue):\n        # assumes node is not empty, not full, not a leaf\n        numItems = theNode.getNumItems()        \n        for j in range(numItems): # for each item in node\n            if( theValue < theNode.getItem(j).dData ):\n                return theNode.getChild(j) # return left child\n        return theNode.getChild(j)\n\n    def displayTree(self):\n        self.recDisplayTree(self.root, 0, 0)\n\n    def recDisplayTree(self,thisNode,level, childNumber):\n        print 'level=' ,level ,' child=',childNumber , ' '\n        thisNode.displayNode()\n        numItems = thisNode.getNumItems()\n        for j in range(numItems+1):\n            nextNode = thisNode.getChild(j)\n            if(nextNode != None):\n                self.recDisplayTree(nextNode, level+1, j)\n            else:\n                return\ntheTree = Tree234()\ntheTree.insert(50)\ntheTree.insert(40)\ntheTree.insert(60)\ntheTree.insert(30)\ntheTree.insert(70)\nwhile(True):\n    print 'Enter first letter of show, '\n    print 'insert, find, or display: ',\n    choice = raw_input()\n    if choice == 's':\n        theTree.displayTree()\n    elif choice == 'i':\n        print 'Enter value to insert: '\n        value = int(raw_input())\n        theTree.insert(value)\n    elif choice == 'f':\n        print 'Enter value to find: ',\n        value = int(raw_input())\n        found = theTree.find(value)\n        if(found != -1):\n            print 'Found: ', value\n        else:\n            print 'Could not find', value \n    else:\n        print 'Invalid entry'\n",
+     "input": [
+      " \n",
+      "class DataItem:\n",
+      "    def __init__(self,dd):\n",
+      "        self.dData = dd\n",
+      "\n",
+      "    def displayItem(self):\n",
+      "        print '/' ,self.dData\n",
+      "\n",
+      "class Node:\n",
+      "    def __init__(self):\n",
+      "        self.ORDER = 4\n",
+      "        self.numItems = 0\n",
+      "        self.parent = None\n",
+      "        self.childArray = [None,None,None,None]\n",
+      "        self.itemArray = [None,None,None]\n",
+      "\n",
+      "    def connectChild(self,childNum,child):\n",
+      "        self.childArray[childNum] = child\n",
+      "        if(child != None):\n",
+      "            child.parent = self\n",
+      "\n",
+      "    def disconnectChild(self,childNum):\n",
+      "        tempNode = self.childArray[childNum]\n",
+      "        self.childArray[childNum] = None\n",
+      "        return tempNode\n",
+      "\n",
+      "    def getChild(self,childNum):\n",
+      "        return self.childArray[childNum]\n",
+      "\n",
+      "    def getParent(self):\n",
+      "        return self.parent\n",
+      "\n",
+      "    def isLeaf(self):\n",
+      "        if self.childArray[0]==None:\n",
+      "            return True \n",
+      "        return False    \n",
+      "\n",
+      "    def getNumItems(self):\n",
+      "        return self.numItems\n",
+      "\n",
+      "    def getItem(self,index):         # get DataItem at index\n",
+      "        return self.itemArray[index] \n",
+      "\n",
+      "    def isFull(self):\n",
+      "        if self.numItems==self.ORDER-1:\n",
+      "            return True\n",
+      "        return False\n",
+      "\n",
+      "    def findItem(self,key): # return index of # item (within node)\n",
+      "        for j in range(self.ORDER-1): \n",
+      "            if(self.itemArray[j] == None):\n",
+      "                break\n",
+      "            elif(self.itemArray[j].dData == key):\n",
+      "                return j\n",
+      "        return -1\n",
+      "\n",
+      "    def insertItem(self,newItem):\n",
+      "        #assumes node is not full\n",
+      "        self.numItems += 1 # will add new item\n",
+      "        newKey = newItem.dData # key of new item\n",
+      "        j = self.ORDER - 2\n",
+      "        while j>=0:\n",
+      "            if(self.itemArray[j] == None):\n",
+      "                continue\n",
+      "            else:\n",
+      "                itsKey = self.itemArray[j].dData\n",
+      "                if(newKey < itsKey):\n",
+      "                    self.itemArray[j+1] = self.itemArray[j]\n",
+      "                else:\n",
+      "                    self.itemArray[j+1] = newItem\n",
+      "                    return j+1 # return index to\n",
+      "            j -= 1\n",
+      "\n",
+      "        self.itemArray[0] = newItem # insert new item\n",
+      "        return 0\n",
+      "\n",
+      "    def removeItem(self): # remove largest item\n",
+      "        temp = self.itemArray[self.numItems-1] # save item\n",
+      "        self.itemArray[self.numItems-1] = None # disconnect it\n",
+      "        self.numItems -= 1 # one less item\n",
+      "        return temp # return item\n",
+      "\n",
+      "    def displayNode(self):\n",
+      "        for j in range(self.numItems):\n",
+      "            self.itemArray[j].displayItem()\n",
+      "        print ''\n",
+      "\n",
+      "class Tree234:\n",
+      "    def __init__(self):\n",
+      "        self.root = Node() # make root node\n",
+      "\n",
+      "    def find(self,key):\n",
+      "        curNode = self.root\n",
+      "        childNumber = 0\n",
+      "        while(True):\n",
+      "            childNumber=curNode.findItem(key) \n",
+      "            if(childNumber != -1):\n",
+      "                return childNumber # found it\n",
+      "            elif( curNode.isLeaf() ):\n",
+      "                return -1 # cant find it\n",
+      "            else: # search deeper\n",
+      "                curNode = getNextChild(curNode, key)\n",
+      "\n",
+      "    def insert(self,dValue):\n",
+      "        curNode = self.root\n",
+      "        tempItem = DataItem(dValue)\n",
+      "        while(True):\n",
+      "            if( curNode.isFull() ):\n",
+      "                split(curNode)\n",
+      "                curNode = curNode.getParent()\n",
+      "                curNode = getNextChild(curNode, dValue)\n",
+      "            elif( curNode.isLeaf() ): # if node is leaf,\n",
+      "                break\n",
+      "            else:\n",
+      "                curNode = getNextChild(curNode, dValue)\n",
+      "        curNode.insertItem(tempItem)\n",
+      "\n",
+      "    def split(self,thisNode): # split the node\n",
+      "        # assumes node is full\n",
+      "        itemC = thisNode.removeItem()         # remove items from\n",
+      "        itemB = thisNode.removeItem()         # this node\n",
+      "        child2 = thisNode.disconnectChild(2) # remove children\n",
+      "        child3 = thisNode.disconnectChild(3) # from this nodeJava Code for a 2-3-4 Tree\n",
+      "        newRight = Node() # make new node\n",
+      "        if(thisNode==self.root):\n",
+      "            self.root = Node()\n",
+      "            parent = self.root\n",
+      "            self.root.connectChild(0, thisNode)\n",
+      "        else:\n",
+      "            parent = thisNode.getParent()\n",
+      "        itemIndex = parent.insertItem(itemB) # item B to parent\n",
+      "        n = parent.getNumItems()\n",
+      "        j = n-1\n",
+      "        while j > itemIndex:\n",
+      "            temp = parent.disconnectChild(j) # one child\n",
+      "            parent.connectChild(j+1, temp)\n",
+      "            j -= 1\n",
+      "\n",
+      "        parent.connectChild(itemIndex+1, newRight) # deal with newRight\n",
+      "        newRight.insertItem(itemC) # item C to newRight\n",
+      "        newRight.connectChild(0, child2) # connect to 0 and 1\n",
+      "        newRight.connectChild(1, child3) # on newRight\n",
+      "\n",
+      "    def getNextChild(self,theNode,theValue):\n",
+      "        # assumes node is not empty, not full, not a leaf\n",
+      "        numItems = theNode.getNumItems()        \n",
+      "        for j in range(numItems): # for each item in node\n",
+      "            if( theValue < theNode.getItem(j).dData ):\n",
+      "                return theNode.getChild(j) # return left child\n",
+      "        return theNode.getChild(j)\n",
+      "\n",
+      "    def displayTree(self):\n",
+      "        self.recDisplayTree(self.root, 0, 0)\n",
+      "\n",
+      "    def recDisplayTree(self,thisNode,level, childNumber):\n",
+      "        print 'level=' ,level ,' child=',childNumber , ' '\n",
+      "        thisNode.displayNode()\n",
+      "        numItems = thisNode.getNumItems()\n",
+      "        for j in range(numItems+1):\n",
+      "            nextNode = thisNode.getChild(j)\n",
+      "            if(nextNode != None):\n",
+      "                self.recDisplayTree(nextNode, level+1, j)\n",
+      "            else:\n",
+      "                return\n",
+      "theTree = Tree234()\n",
+      "theTree.insert(50)\n",
+      "theTree.insert(40)\n",
+      "theTree.insert(60)\n",
+      "theTree.insert(30)\n",
+      "theTree.insert(70)\n",
+      "while(True):\n",
+      "    print 'Enter first letter of show, '\n",
+      "    print 'insert, find, or display: ',\n",
+      "    choice = raw_input()\n",
+      "    if choice == 's':\n",
+      "        theTree.displayTree()\n",
+      "    elif choice == 'i':\n",
+      "        print 'Enter value to insert: '\n",
+      "        value = int(raw_input())\n",
+      "        theTree.insert(value)\n",
+      "    elif choice == 'f':\n",
+      "        print 'Enter value to find: ',\n",
+      "        value = int(raw_input())\n",
+      "        found = theTree.find(value)\n",
+      "        if(found != -1):\n",
+      "            print 'Found: ', value\n",
+      "        else:\n",
+      "            print 'Could not find', value \n",
+      "    else:\n",
+      "        print 'Invalid entry'\n"
+     ],
      "language": "python",
      "metadata": {},
-     "outputs": [],
-     "prompt_number": "*"
+     "outputs": []
     },
     {
      "cell_type": "code",
      "collapsed": false,
-     "input": "",
+     "input": [],
      "language": "python",
      "metadata": {},
      "outputs": []