# python-data-structures

In [1]:
from IPython.display import HTML

Table 1: Common Functions for Big-O
f(n) Name
1$1$ Constant
logn$\log n$ Logarithmic
n$n$ Linear
nlogn$n\log n$ Log Linear
n2$n^{2}$ Quadratic
n3$n^{3}$ Cubic
2n$2^{n}$ Exponential
Table 2: Big-O Efficiency of Python List Operators
Operation Big-O Efficiency
index [] O(1)
index assignment O(1)
append O(1)
pop() O(1)
pop(i) O(n)
insert(i,item) O(n)
del operator O(n)
iteration O(n)
contains (in) O(n)
get slice [x:y] O(k)
del slice O(n)
set slice O(n+k)
reverse O(n)
concatenate O(k)
sort O(n log n)
multiply O(nk)
Table 3: Big-O Efficiency of Python Dictionary Operations
operation Big-O Efficiency
copy O(n)
get item O(1)
set item O(1)
delete item O(1)
contains (in) O(1)
iteration O(n)

### The Stack Abstract Data Type¶

Table 1: Sample Stack Operations
Stack Operation Stack Contents Return Value
s.isEmpty() [] True
s.push(4) [4]
s.push('dog') [4,'dog']
s.peek() [4,'dog'] 'dog'
s.push(True) [4,'dog',True]
s.size() [4,'dog',True] 3
s.isEmpty() [4,'dog',True] False
s.push(8.4) [4,'dog',True,8.4]
s.pop() [4,'dog',True] 8.4
s.pop() [4,'dog'] True
s.size() [4,'dog'] 2

### Implementing a Stack in Python¶

In [2]:
class Stack:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

def push(self, item):
self.items.append(item)

def pop(self):
return self.items.pop()

def peek(self):
return self.items[len(self.items)-1]

def size(self):
return len(self.items)

def show(self):
return [self.pop() for x in range(self.size())]

In [3]:
def revstring(mystr):
t = Stack()
[t.push(x) for x in mystr]
return ''.join(t.show())

revstring('apple')

Out[3]:
'elppa'

### Simple Balanced Parentheses¶

In [4]:
from pythonds.basic.stack import Stack

def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol == "(":
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
s.pop()

index = index + 1

if balanced and s.isEmpty():
return True
else:
return False

print(parChecker('((()))'))
print(parChecker('(()'))

True
False


### Balanced Symbols (A General Case)¶

In [5]:
from pythonds.basic.stack import Stack

def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in "([{":
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matches(top,symbol):
balanced = False
index = index + 1
if balanced and s.isEmpty():
return True
else:
return False

def matches(open,close):
opens = "([{"
closers = ")]}"
return opens.index(open) == closers.index(close)

print(parChecker('{{([][])}()}'))
print(parChecker('[{()]'))

True
False


### Converting Decimal Numbers to Binary Numbers¶

In [6]:
from pythonds.basic.stack import Stack

def baseConverter(decNumber,base):
digits = "0123456789ABCDEF"

remstack = Stack()

while decNumber > 0:
rem = decNumber % base
remstack.push(rem)
decNumber = decNumber // base

newString = ""
while not remstack.isEmpty():
newString = newString + digits[remstack.pop()]

return newString

print(baseConverter(25,2))
print(baseConverter(25,16))

11001
19


### Infix, Prefix and Postfix Expressions¶

1. Create an empty stack called opstack for keeping operators. Create an empty list for output.
2. Convert the input infix string to a list by using the string method split.
3. Scan the token list from left to right.
• If the token is an operand, append it to the end of the output list.
• If the token is a left parenthesis, push it on the opstack.
• If the token is a right parenthesis, pop the opstack until the corresponding left parenthesis is removed. Append each operator to the end of the output list.
• If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that have higher or equal precedence and append them to the output list.
4. When the input expression has been completely processed, check the opstack. Any operators still on the stack can be removed and appended to the end of the output list.
In [7]:
from pythonds.basic.stack import Stack

def infixToPostfix(infixexpr):
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
opStack = Stack()
postfixList = []
tokenList = infixexpr.split()

for token in tokenList:
if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
postfixList.append(token)
elif token == '(':
opStack.push(token)
elif token == ')':
topToken = opStack.pop()
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)

while not opStack.isEmpty():
postfixList.append(opStack.pop())
return " ".join(postfixList)

print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

A B * C D * +
A B + C * D E - F G + * -


### Postfix Evaluation¶

1. Create an empty stack called operandStack.
2. Convert the string to a list by using the string method split.
3. Scan the token list from left to right.
• If the token is an operand, convert it from a string to an integer and push the value onto the operandStack.
• If the token is an operator, *, /, +, or -, it will need two operands. Pop the operandStack twice. The first pop is the second operand and the second pop is the first operand. Perform the arithmetic operation. Push the result back on the operandStack.
4. When the input expression has been completely processed, the result is on the stack. Pop the operandStack and return the value.
In [8]:
from pythonds.basic.stack import Stack

def postfixEval(postfixExpr):
operandStack = Stack()
tokenList = postfixExpr.split()

for token in tokenList:
if token in "0123456789":
operandStack.push(int(token))
else:
operand2 = operandStack.pop()
operand1 = operandStack.pop()
result = doMath(token,operand1,operand2)
operandStack.push(result)
return operandStack.pop()

def doMath(op, op1, op2):
if op == "*":
return op1 * op2
elif op == "/":
return op1 / op2
elif op == "+":
return op1 + op2
else:
return op1 - op2

print(postfixEval('7 8 + 3 2 + /'))

3.0


### The Queue Abstract Data Type¶

Table 1: Example Queue Operations
Queue Operation Queue Contents Return Value
q.isEmpty() [] True
q.enqueue(4) [4]
q.enqueue('dog') ['dog',4]
q.enqueue(True) [True,'dog',4]
q.size() [True,'dog',4] 3
q.isEmpty() [True,'dog',4] False
q.enqueue(8.4) [8.4,True,'dog',4]
q.dequeue() [8.4,True,'dog'] 4
q.dequeue() [8.4,True] 'dog'
q.size() [8.4,True] 2

### Implementing a Queue in Python¶

In [9]:
class Queue:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

def enqueue(self, item):
self.items.insert(0,item)

def dequeue(self):
return self.items.pop()

def size(self):
return len(self.items)

def show(self):
return map(lambda x: self.dequeue(), range(self.size()))

In [10]:
q = Queue()
q.enqueue('hello')
q.enqueue('dog')
q.enqueue(3)
q.dequeue()
q.show()

Out[10]:
<map at 0x7f83a45b56d8>

### Simulation: Hot Potato¶

In [11]:
from pythonds.basic.queue import Queue

def hotPotato(namelist, num):
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name)

while simqueue.size() > 1:
for i in range(num):
simqueue.enqueue(simqueue.dequeue())
simqueue.dequeue()
return simqueue.dequeue()


Susan

In [12]:
HTML('<iframe width="800" height="500" frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=class+Queue%3A%0A++++def+__init__(self)%3A%0A++++++++self.items+%3D+%5B%5D%0A%0A++++def+isEmpty(self)%3A%0A++++++++return+self.items+%3D%3D+%5B%5D%0A%0A++++def+enqueue(self,+item)%3A%0A++++++++self.items.insert(0,item)%0A%0A++++def+dequeue(self)%3A%0A++++++++return+self.items.pop()%0A%0A++++def+size(self)%3A%0A++++++++return+len(self.items)%0A++++%0A++++def+show(self)%3A%0A++++++++return+map(lambda+x%3A+self.dequeue(),+range(self.size()))%0A%0Adef+hotPotato(namelist,+num)%3A%0A++++simqueue+%3D+Queue()%0A++++for+name+in+namelist%3A%0A++++++++simqueue.enqueue(name)%0A%0A++++while+simqueue.size()+%3E+1%3A%0A++++++++for+i+in+range(num)%3A%0A++++++++++++simqueue.enqueue(simqueue.dequeue())%0A%0A++++++++simqueue.dequeue()%0A%0A++++return+simqueue.dequeue()%0A%0Aprint(hotPotato(%5B%22Bill%22,%22David%22,%22Susan%22,%22Jane%22,%22Kent%22,%22Brad%22%5D,7))%0A&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=0&codeDivWidth=350&codeDivHeight=400"> </iframe>')

Out[12]:

1. Create a queue of print tasks. Each task will be given a timestamp upon its arrival. The queue is empty to start.
2. For each second (currentSecond):
• Does a new print task get created? If so, add it to the queue with the currentSecond as the timestamp.
• If the printer is not busy and if a task is waiting,
• Remove the next task from the print queue and assign it to the printer.
• Subtract the timestamp from the currentSecond to compute the waiting time for that task.
• Append the waiting time for that task to a list for later processing.
• Based on the number of pages in the print task, figure out how much time will be required.
• The printer now does one second of printing if necessary. It also subtracts one second from the time required for that task.
• If the task has been completed, in other words the time required has reached zero, the printer is no longer busy.
3. After the simulation is complete, compute the average waiting time from the list of waiting times generated.
In [13]:
import random

class Printer:
def __init__(self, ppm):
self.pagerate = ppm
self.timeRemaining = 0

def tick(self):
self.timeRemaining = self.timeRemaining - 1
if self.timeRemaining <= 0:

def busy(self):
return True
else:
return False

def __init__(self,time):
self.timestamp = time
self.pages = random.randrange(1,21)

def getStamp(self):
return self.timestamp

def getPages(self):
return self.pages

def waitTime(self, currenttime):
return currenttime - self.timestamp

def simulation(numSeconds, pagesPerMinute):

labprinter = Printer(pagesPerMinute)
printQueue = Queue()
waitingtimes = []

for currentSecond in range(numSeconds):

if (not labprinter.busy()) and (not printQueue.isEmpty()):

labprinter.tick()

averageWait=sum(waitingtimes)/len(waitingtimes)
print("Average Wait %6.2f secs %3d tasks remaining."%(averageWait,printQueue.size()))

num = random.randrange(1,181)
if num == 180:
return True
else:
return False

for i in range(10):
simulation(3600,5)

Average Wait  31.79 secs   0 tasks remaining.
Average Wait  63.80 secs   0 tasks remaining.
Average Wait  29.67 secs   0 tasks remaining.
Average Wait 161.00 secs   0 tasks remaining.
Average Wait 903.00 secs  11 tasks remaining.
Average Wait 338.50 secs   2 tasks remaining.
Average Wait  82.90 secs   0 tasks remaining.
Average Wait 164.33 secs   1 tasks remaining.
Average Wait  98.30 secs   1 tasks remaining.
Average Wait  50.20 secs   1 tasks remaining.


### The Deque Abstract Data Type¶

Table 1: Examples of Deque Operations
Deque Operation Deque Contents Return Value
d.isEmpty() [] True
d.addRear(4) [4]
d.addRear('dog') ['dog',4,]
d.addFront('cat') ['dog',4,'cat']
d.addFront(True) ['dog',4,'cat',True]
d.size() ['dog',4,'cat',True] 4
d.isEmpty() ['dog',4,'cat',True] False
d.addRear(8.4) [8.4,'dog',4,'cat',True]
d.removeRear() ['dog',4,'cat',True] 8.4
d.removeFront() ['dog',4,'cat'] True

### Implementing a Deque in Python¶

In [14]:
class Deque:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

self.items.append(item)

self.items.insert(0,item)

def removeFront(self):
return self.items.pop()

def removeRear(self):
return self.items.pop(0)

def size(self):
return len(self.items)

def show(self):
return map(lambda x: self.dequeue(), range(self.size()))

In [15]:
d=Deque()
print(d.isEmpty())
print(d.size())
print(d.isEmpty())
print(d.removeRear())

True
4
False
8.4


### Palindrome-Checker(回文检查)¶

In [16]:
def palchecker(aString):
chardeque = Deque()

for ch in aString:

stillEqual = True

while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False

return stillEqual

print(palchecker("lsdkjfskf"))

False
True


### The Unordered List Abstract Data Type¶

• List() creates a new list that is empty. It needs no parameters and returns an empty list.
• add(item) adds a new item to the list. It needs the item and returns nothing. Assume the item is not already in the list.
• remove(item) removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.
• search(item) searches for the item in the list. It needs the item and returns a boolean value.
• isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items in the list. It needs no parameters and returns an integer.
• append(item) adds a new item to the end of the list making it the last item in the collection. It needs the item and returns nothing. Assume the item is not already in the list.
• index(item) returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.
• insert(pos,item) adds a new item to the list at position pos. It needs the item and returns nothing. Assume the item is not already in the list and there are enough existing items to have position pos.
• pop() removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.
• pop(pos) removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.

### Implementing an Unordered List: Linked Lists¶

In [17]:
class Node:
"""
The basic building block for the linked list implementation
is the node. Each node object must hold at least two pieces
of information. First, the node must contain the list item
itself. We will call this the data field of the node.
"""
def __init__(self,initdata):
self.data = initdata
self.next = None

def getData(self):
return self.data

def getNext(self):
return self.next

def setData(self,newdata):
self.data = newdata

def setNext(self,newnext):
self.next = newnext

class UnorderedList:
"""
The unordered list will be built from a collection of nodes,
each linked to the next by explicit references. As long as we
know where to find the first node (containing the first item),
each item after that can be found by successively following
"""
def __init__(self):

def isEmpty(self):

temp = Node(item)

def size(self):
count = 0
while current != None:
count = count + 1
current = current.getNext()

return count

def search(self,item):
found = False
if current.getData() == item:
found = True
else:
current = current.getNext()

return found

def remove(self,item):
previous = None
found = False
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()

if previous == None:
else:
previous.setNext(current.getNext())

In [18]:
mylist = UnorderedList()

print(mylist.size())
print(mylist.search(93))
print(mylist.search(100))

print(mylist.search(100))
print(mylist.size())

mylist.remove(54)
print(mylist.size())
mylist.remove(93)
print(mylist.size())
mylist.remove(31)
print(mylist.size())
print(mylist.search(93))

6
True
False
True
7
6
5
4
False


### The Ordered List Abstract Data Type¶

The structure of an ordered list is a collection of items where each item holds a relative position that is based upon some underlying characteristic of the item. The ordering is typically either ascending or descending and we assume that list items have a meaningful comparison operation that is already defined. Many of the ordered list operations are the same as those of the unordered list.

• OrderedList() creates a new ordered list that is empty. It needs no parameters and returns an empty list.
• add(item) adds a new item to the list making sure that the order is preserved. It needs the item and returns nothing. Assume the item is not already in the list.
• remove(item) removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.
• search(item) searches for the item in the list. It needs the item and returns a boolean value.
• isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items in the list. It needs no parameters and returns an integer.
• index(item) returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.
• pop() removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.
• pop(pos) removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.

### Implementing an Ordered List¶

In [19]:
class OrderedList:
def __init__(self):

def search(self,item):
found = False
stop = False
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()

return found

previous = None
stop = False
while current != None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()

temp = Node(item)
if previous == None:
else:
temp.setNext(current)
previous.setNext(temp)

def isEmpty(self):

def size(self):
count = 0
while current != None:
count = count + 1
current = current.getNext()

return count

In [20]:
mylist = OrderedList()

print(mylist.size())
print(mylist.search(93))
print(mylist.search(100))

6
True
False


### The Three Laws of Recursion¶

1. A recursive algorithm must have a base case.
2. A recursive algorithm must change its state and move toward the base case.
3. A recursive algorithm must call itself, recursively.
In [21]:
def listsum(numList):
theSum = 0
for i in numList:
theSum = theSum + i
return theSum

print(listsum([1,3,5,7,9]))

25

In [22]:
def listsum(numList):
if len(numList) == 1:
return numList[0]
else:
return numList[0] + listsum(numList[1:])

print(listsum([1,3,5,7,9]))

25


### Converting an Integer to a String in Any Base¶

In [23]:
def toStr(n,base):
convertString = "0123456789ABCDEF"
if n < base:
return convertString[n]
else:

print(toStr(1453,16))

5AD

In [24]:
def reverse(s):
"""
a function that takes a string as a parameter and returns
a new string that is the reverse of the old string.
"""
if s == '': return s
else: return reverse(s[1:]) + s[0]

In [25]:
print(reverse("follow"))
print(reverse("a +"))

wollof
+ a

In [26]:
import string

def removeWhite(s):
exclude = set(string.punctuation+' ')
s = ''.join(ch for ch in s if ch not in exclude)
return s

def isPal(s):
"""
Write a function that takes a string as a parameter and
returns True if the string is a palindrome, False otherwise.
"""
s = removeWhite(s)
return len(s) < 2 or s[0] == s[-1] and isPal(s[1:-1])

In [27]:
print(isPal(removeWhite("x")))
print(isPal(removeWhite("hello")))
print(isPal(removeWhite("")))
print(isPal(removeWhite("hannah")))

True
True
False
True
True
True


### Stack Frames: Implementing Recursion¶

In [28]:
rStack = Stack()

def toStr(n,base):
convertString = "0123456789ABCDEF"
while n > 0:
if n < base:
rStack.push(convertString[n])
else:
rStack.push(convertString[n % base])
n = n // base
res = ""
while not rStack.isEmpty():
res = res + str(rStack.pop())
return res

print(toStr(1453,16))

5AD

In [29]:
HTML('<iframe width="1000" height="500" frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=class+Stack%3A%0A++++def+__init__(self)%3A%0A++++++++self.items+%3D+%5B%5D%0A%0A++++def+isEmpty(self)%3A%0A++++++++return+self.items+%3D%3D+%5B%5D%0A%0A++++def+push(self,+item)%3A%0A++++++++self.items.append(item)%0A%0A++++def+pop(self)%3A%0A++++++++return+self.items.pop()%0A%0A++++def+peek(self)%3A%0A++++++++return+self.items%5Blen(self.items)-1%5D%0A%0A++++def+size(self)%3A%0A++++++++return+len(self.items)%0A++++%0ArStack+%3D+Stack()%0A%0Adef+toStr(n,base)%3A%0A++++convertString+%3D+%220123456789ABCDEF%22%0A++++while+n+%3E+0%3A%0A++++++++if+n+%3C+base%3A%0A++++++++++++rStack.push(convertString%5Bn%5D)%0A++++++++else%3A%0A++++++++++++rStack.push(convertString%5Bn+%25+base%5D)%0A++++++++n+%3D+n+//+base%0A++++res+%3D+%22%22%0A++++while+not+rStack.isEmpty()%3A%0A++++++++res+%3D+res+%2B+str(rStack.pop())%0A++++return+res%0A%0Aprint(toStr(1453,16))&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=29&codeDivWidth=350&codeDivHeight=400"> </iframe>')

Out[29]:

### Tower of Hanoi¶

The number of moves required to correctly move a tower of $n$ disks is $2^n-1$.Here is a high-level outline of how to move a tower from the starting pole, to the goal pole, using an intermediate pole:

1. Move a tower of height-1 to an intermediate pole, using the final pole. 用C把高度height-1的塔从A移动到B
2. Move the remaining disk to the final pole. 把A剩下的碟子移动到C
3. Move the tower of height-1 from the intermediate pole to the final pole using the original pole. 用A把高度height-1的塔从B移动到C
In [30]:
def moveTower(height,fromPole, toPole, withPole):
if height >= 1:
moveTower(height-1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole)
moveTower(height-1,withPole,toPole,fromPole)

def moveDisk(fp,tp):
print("moving disk from",fp,"to",tp)

moveTower(3,"A","B","C")

moving disk from A to B
moving disk from A to C
moving disk from B to C
moving disk from A to B
moving disk from C to A
moving disk from C to B
moving disk from A to B

In [31]:
HTML('<iframe width="1000" height="500" frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=def+moveTower(height,fromPole,+toPole,+withPole)%3A%0A++++if+height+%3E%3D+1%3A%0A++++++++moveTower(height-1,fromPole,withPole,toPole)%0A++++++++moveDisk(fromPole,toPole)%0A++++++++moveTower(height-1,withPole,toPole,fromPole)%0A%0Adef+moveDisk(fp,tp)%3A%0A++++print+%22moving+disk+from%22,fp,%22to%22,tp%0A%0AmoveTower(3,%22A%22,%22B%22,%22C%22)&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=80&codeDivWidth=350&codeDivHeight=400"> </iframe>')

Out[31]:
In [32]:
def moveTower(height,fromPole, toPole, withPole):
print("moveTower:", height,fromPole, toPole, withPole)
if height >= 1:
moveTower(height-1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole)
moveTower(height-1,withPole,toPole,fromPole)

def moveDisk(fp,tp):
if fromPole[1]:
disk = fromPole[1].pop()
print("moving " + str(disk) + " from " + fromPole[0] + " to " + toPole[0])
toPole[1].append(disk)

fromPole = ("A", [3,2,1])
toPole = ("C", [])
withPole = ("B", [])

moveTower(len(fromPole[1]), fromPole, toPole, withPole)
print(fromPole, withPole, toPole)

moveTower: 3 ('A', [3, 2, 1]) ('C', []) ('B', [])
moveTower: 2 ('A', [3, 2, 1]) ('B', []) ('C', [])
moveTower: 1 ('A', [3, 2, 1]) ('C', []) ('B', [])
moveTower: 0 ('A', [3, 2, 1]) ('B', []) ('C', [])
moving 1 from A to C
moveTower: 0 ('B', []) ('C', [1]) ('A', [3, 2])
moving 2 from A to C
moveTower: 1 ('C', [1, 2]) ('B', []) ('A', [3])
moveTower: 0 ('C', [1, 2]) ('A', [3]) ('B', [])
moving 3 from A to C
moveTower: 0 ('A', []) ('B', []) ('C', [1, 2, 3])
moveTower: 2 ('B', []) ('C', [1, 2, 3]) ('A', [])
moveTower: 1 ('B', []) ('A', []) ('C', [1, 2, 3])
moveTower: 0 ('B', []) ('C', [1, 2, 3]) ('A', [])
moveTower: 0 ('C', [1, 2, 3]) ('A', []) ('B', [])
moveTower: 1 ('A', []) ('C', [1, 2, 3]) ('B', [])
moveTower: 0 ('A', []) ('B', []) ('C', [1, 2, 3])
moveTower: 0 ('B', []) ('C', [1, 2, 3]) ('A', [])
('A', []) ('B', []) ('C', [1, 2, 3])


### Exploring a Maze¶

In [33]:
import turtle
from __future__ import division

PART_OF_PATH = 'O'
TRIED = '.'
OBSTACLE = '+'

class Maze:
def __init__(self,mazeFileName):
rowsInMaze = 0
columnsInMaze = 0
self.mazelist = []
mazeFile = open(mazeFileName,'r')
rowsInMaze = 0
for line in mazeFile:
rowList = []
col = 0
for ch in line[:-1]:
rowList.append(ch)
if ch == 'S':
self.startRow = rowsInMaze
self.startCol = col
col = col + 1
rowsInMaze = rowsInMaze + 1
self.mazelist.append(rowList)
columnsInMaze = len(rowList)

self.rowsInMaze = rowsInMaze
self.columnsInMaze = columnsInMaze
self.xTranslate = -columnsInMaze/2
self.yTranslate = rowsInMaze/2
self.t = turtle.Turtle()
self.t.shape('turtle')
self.wn = turtle.Screen()
self.wn.setworldcoordinates(-(columnsInMaze-1)/2-.5,-(rowsInMaze-1)/2-.5,(columnsInMaze-1)/2+.5,(rowsInMaze-1)/2+.5)

def drawMaze(self):
self.t.speed(10)
for y in range(self.rowsInMaze):
for x in range(self.columnsInMaze):
if self.mazelist[y][x] == OBSTACLE:
self.drawCenteredBox(x+self.xTranslate,-y+self.yTranslate,'orange')
self.t.color('black')
self.t.fillcolor('blue')

def drawCenteredBox(self,x,y,color):
self.t.up()
self.t.goto(x-.5,y-.5)
self.t.color(color)
self.t.fillcolor(color)
self.t.down()
self.t.begin_fill()
for i in range(4):
self.t.forward(1)
self.t.right(90)
self.t.end_fill()

def moveTurtle(self,x,y):
self.t.up()
self.t.goto(x+self.xTranslate,-y+self.yTranslate)

self.t.dot(10,color)

def updatePosition(self,row,col,val=None):
if val:
self.mazelist[row][col] = val
self.moveTurtle(col,row)

if val == PART_OF_PATH:
color = 'green'
elif val == OBSTACLE:
color = 'red'
elif val == TRIED:
color = 'black'
color = 'red'
else:
color = None

if color:

def isExit(self,row,col):
return (row == 0 or
row == self.rowsInMaze-1 or
col == 0 or
col == self.columnsInMaze-1 )

def __getitem__(self,idx):
return self.mazelist[idx]

def searchFrom(maze, startRow, startColumn):
# try each of four directions from this point until we find a way out.
# base Case return values:
#  1. We have run into an obstacle, return false
maze.updatePosition(startRow, startColumn)
if maze[startRow][startColumn] == OBSTACLE :
return False
#  2. We have found a square that has already been explored
if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn] == DEAD_END:
return False
# 3. We have found an outside edge not occupied by an obstacle
if maze.isExit(startRow,startColumn):
maze.updatePosition(startRow, startColumn, PART_OF_PATH)
return True
maze.updatePosition(startRow, startColumn, TRIED)
# Otherwise, use logical short circuiting to try each direction
# in turn (if needed)
found = searchFrom(maze, startRow-1, startColumn) or \
searchFrom(maze, startRow+1, startColumn) or \
searchFrom(maze, startRow, startColumn-1) or \
searchFrom(maze, startRow, startColumn+1)
if found:
maze.updatePosition(startRow, startColumn, PART_OF_PATH)
else:
return found

# myMaze = Maze('maze2.txt')
# myMaze.drawMaze()
# myMaze.updatePosition(myMaze.startRow,myMaze.startCol)

# searchFrom(myMaze, myMaze.startRow, myMaze.startCol)


### Dynamic Programming¶

In [34]:
def recDC(coinValueList,change,knownResults):
minCoins = change
if change in coinValueList:
knownResults[change] = 1
return 1
elif knownResults[change] > 0:
return knownResults[change]
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recDC(coinValueList, change-i,
knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[change] = minCoins
return minCoins

print(recDC([1,5,10,25],63,[0]*64))

6

In [35]:
def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
for cents in range(change+1):
coinCount = cents
newCoin = 1
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents-j] + 1 < coinCount:
coinCount = minCoins[cents-j]+1
newCoin = j
minCoins[cents] = coinCount
coinsUsed[cents] = newCoin
return minCoins[change]

def printCoins(coinsUsed,change):
coin = change
while coin > 0:
thisCoin = coinsUsed[coin]
print(thisCoin)
coin = coin - thisCoin

def main():
amnt = 63
clist = [1,5,10,21,25]
coinsUsed = [0]*(amnt+1)
coinCount = [0]*(amnt+1)

print("Making change for",amnt,"requires")
print(dpMakeChange(clist,amnt,coinCount,coinsUsed),"coins")
print("They are:")
printCoins(coinsUsed,amnt)
print("The used list is as follows:")
print(coinsUsed)

main()

Making change for 63 requires
3 coins
They are:
21
21
21
The used list is as follows:
[1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]

1. All recursive algorithms must have a base case.
2. A recursive algorithm must change its state and make progress toward the base case.
3. A recursive algorithm must call itself (recursively).
4. Recursion can take the place of iteration in some cases.
5. Recursive algorithms often map very naturally to a formal expression of the problem you are trying to solve.
6. Recursion is not always the answer. Sometimes a recursive solution may be more computationally expensive than an alternative algorithm
Table 1: Comparisons Used in a Sequential Search of an Unordered List
Case Best Case Worst Case Average Case
item is present 1$1$ n$n$ n2$\frac{n}{2}$
item is not present n$n$ n$n$ n$n$
In [36]:
def sequentialSearch(alist, item):
pos = 0
found = False

if alist[pos] == item:
found = True
else:
pos = pos + 1

return found

testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))

False
True

Table 2: Comparisons Used in Sequential Search of an Ordered List
Best Case Worst Case Average Case
item is present 1$1$ n$n$ n2$\frac{n}{2}$
item not present 1$1$ n$n$ n2$\frac{n}{2}$
In [37]:
def orderedSequentialSearch(alist, item):
pos = 0
found = False
stop = False
if alist[pos] == item:
found = True
else:
if alist[pos] > item:
stop = True
else:
pos = pos+1

return found

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(orderedSequentialSearch(testlist, 3))
print(orderedSequentialSearch(testlist, 13))

False
True

Table 3: Tabular Analysis for a Binary Search
Comparisons Approximate Number of Items Left
1 n2$\frac {n}{2}$
2 n4$\frac {n}{4}$
3 n8$\frac {n}{8}$
...
i n2i$\frac {n}{2^i}$

#### Binary Search of an Ordered List¶

In [38]:
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False

midpoint = (first + last) // 2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1

return found

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))

False
True


#### A Binary Search--Recursive Version¶

In [39]:
def binarySearch(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist) // 2
if alist[midpoint] == item:
return True
else:
if item < alist[midpoint]:
return binarySearch(alist[:midpoint], item)
else:
return binarySearch(alist[midpoint + 1:], item)

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))

False
True


### Hashing¶

• Map() Create a new, empty map. It returns an empty map collection.
• 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.
• get(key) Given a key, return the value stored in the map or None otherwise.
• del Delete the key-value pair from the map using a statement of the form del map[key].
• len() Return the number of key-value pairs stored in the map.
• in Return True for a statement of the form key in map, if the given key is in the map, False otherwise.
In [40]:
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size

def put(self,key,data):
hashvalue = self.hashfunction(key,len(self.slots))

if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
if self.slots[hashvalue] == key:
self.data[hashvalue] = data  #replace
else:
nextslot = self.rehash(hashvalue,len(self.slots))
while self.slots[nextslot] != None and \
self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))

if self.slots[nextslot] == None:
self.slots[nextslot]=key
self.data[nextslot]=data
else:
self.data[nextslot] = data #replace

def hashfunction(self,key,size):
return key%size

def rehash(self,oldhash,size):
return (oldhash+1)%size

def get(self,key):
startslot = self.hashfunction(key,len(self.slots))

data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and  \
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position=self.rehash(position,len(self.slots))
if position == startslot:
stop = True
return data

def __getitem__(self,key):
return self.get(key)

def __setitem__(self,key,data):
self.put(key,data)

In [41]:
H=HashTable()
H[54]="cat"
H[26]="dog"
H[93]="lion"
H[17]="tiger"
H[77]="bird"
H[31]="cow"
H[44]="goat"
H[55]="pig"
H[20]="chicken"
print(H.slots)
print(H.data)

print(H[20])

print(H[17])
H[20]='duck'
print(H[20])
print(H[99])

[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
chicken
tiger
duck
None


### The Bubble Sort¶

In [42]:
def bubbleSort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

[17, 20, 26, 31, 44, 54, 55, 77, 93]


#### The Short Bubble Sort¶

A bubble sort can be modified to stop early if it finds that the list has become sorted. This means that for lists that require just a few passes, a bubble sort may have an advantage in that it will recognize the sorted list and stop.

In [43]:
def shortBubbleSort(alist):
exchanges = True
passnum = len(alist)-1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if alist[i]>alist[i+1]:
exchanges = True
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
passnum = passnum-1

alist=[20,30,40,90,50,60,70,80,100,110]
shortBubbleSort(alist)
print(alist)

[20, 30, 40, 50, 60, 70, 80, 90, 100, 110]


### The Selection Sort¶

Selection sort improves upon bubble sort by making fewer swaps

In [44]:
def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
if alist[location]>alist[positionOfMax]:
positionOfMax = location

temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

[17, 20, 26, 31, 44, 54, 55, 77, 93]


### The Insertion Sort¶

Insertion sort works at the start of the list. Each pass produces a longer sorted list

In [45]:
def insertionSort(alist):
for index in range(1,len(alist)):

currentvalue = alist[index]
position = index

while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1

alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

[17, 20, 26, 31, 44, 54, 55, 77, 93]


### The Shell Sort¶

In [46]:
def shellSort(alist):
sublistcount = len(alist) // 2
while sublistcount > 0:

for startposition in range(sublistcount):
gapInsertionSort(alist,startposition,sublistcount)

print("After increments of size",sublistcount, "The list is", alist)

sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):
for i in range(start+gap,len(alist),gap):

currentvalue = alist[i]
position = i

while position>=gap and alist[position-gap]>currentvalue:
alist[position]=alist[position-gap]
position = position-gap

alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)

After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]
After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]
After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]


### The Merge Sort¶

Merge sort will continue to recursively move toward the beginning of the list until it hits a base case.

In [47]:
def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]

mergeSort(lefthalf)
mergeSort(righthalf)

i=0
j=0
k=0
while i<len(lefthalf) and j<len(righthalf):
if lefthalf[i]<righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1

while i<len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1

while j<len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Splitting  [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting  [54, 26, 93, 17]
Splitting  [54, 26]
Splitting  [54]
Merging  [54]
Splitting  [26]
Merging  [26]
Merging  [26, 54]
Splitting  [93, 17]
Splitting  [93]
Merging  [93]
Splitting  [17]
Merging  [17]
Merging  [17, 93]
Merging  [17, 26, 54, 93]
Splitting  [77, 31, 44, 55, 20]
Splitting  [77, 31]
Splitting  [77]
Merging  [77]
Splitting  [31]
Merging  [31]
Merging  [31, 77]
Splitting  [44, 55, 20]
Splitting  [44]
Merging  [44]
Splitting  [55, 20]
Splitting  [55]
Merging  [55]
Splitting  [20]
Merging  [20]
Merging  [20, 55]
Merging  [20, 44, 55]
Merging  [20, 31, 44, 55, 77]
Merging  [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]


### The Quick Sort¶

To choose the pivot value, we will consider the first, the middle, and the last element in the list. In our example, those are 54, 77, and 20. Now pick the median value, in our case 54, and use it for the pivot value (of course, that was the pivot value we used originally). The idea is that in the case where the the first item in the list does not belong toward the middle of the list, the median of three will choose a better “middle” value. This will be particularly useful when the original list is somewhat sorted to begin with.

In [48]:
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
if first<last:

splitpoint = partition(alist,first,last)

quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
pivotvalue = alist[first]

leftmark = first+1
rightmark = last

done = False
while not done:

while leftmark <= rightmark and \
alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and \
rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp

temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp

return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

[17, 20, 26, 31, 44, 54, 55, 77, 93]

1. A sequential search is $O(n)$ for ordered and unordered lists.
2. A binary search of an ordered list is $O(logn)$ in the worst case.
3. Hash tables can provide constant time searching.
4. A bubble sort, a selection sort, and an insertion sort are $O(n^2)$ algorithms.
5. A shell sort improves on the insertion sort by sorting incremental sublists. It falls between $O(n)$ and $O(n^2)$.
6. A merge sort is $O(nlogn)$, but requires additional space for the merging process.
7. A quick sort is $O(nlogn)$, but may degrade to $O(n^2)$ if the split points are not near the middle of the list. It does not require additional space.

### Trees and Tree Algorithms¶

1. 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:
• One node of the tree is designated as the root node.
• 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.
• A unique path traverses from the root to each node.
• If each node in the tree has a maximum of two children, we say that the tree is a binary tree.
2. 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.

### List of Lists Representation¶

In [49]:
myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]
print(myTree)
print('left subtree = ', myTree[1])
print('root = ', myTree[0])
print('right subtree = ', myTree[2])

['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]
left subtree =  ['b', ['d', [], []], ['e', [], []]]
root =  a
right subtree =  ['c', ['f', [], []], []]


#### A Python Session to Illustrate Basic Tree Functions¶

In [50]:
def BinaryTree(r):
return [r, [], []]

def insertLeft(root,newBranch):
t = root.pop(1)
if len(t) > 1:
root.insert(1,[newBranch,t,[]])
else:
root.insert(1,[newBranch, [], []])
return root

def insertRight(root,newBranch):
t = root.pop(2)
if len(t) > 1:
root.insert(2,[newBranch,[],t])
else:
root.insert(2,[newBranch,[],[]])
return root

def getRootVal(root):
return root[0]

def setRootVal(root,newVal):
root[0] = newVal

def getLeftChild(root):
return root[1]

def getRightChild(root):
return root[2]

r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertRight(r,6)
insertRight(r,7)
l = getLeftChild(r)
print(l)

setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))

[5, [4, [], []], []]
[3, [9, [4, [], []], []], [7, [], [6, [], []]]]
[3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]
[6, [], []]

In [51]:
x = BinaryTree('a')
insertLeft(x,'b')
insertRight(x,'c')
insertRight(getRightChild(x),'d')
insertLeft(getRightChild(getRightChild(x)),'e')
print(x)

['a', ['b', [], []], ['c', [], ['d', ['e', [], []], []]]]


### Nodes and References¶

In [52]:
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None

def insertLeft(self,newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRight(self,newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

def getRightChild(self):
return self.rightChild

def getLeftChild(self):
return self.leftChild

def setRootVal(self,obj):
self.key = obj

def getRootVal(self):
return self.key

In [53]:
r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
r.insertLeft('b')
print(r.getLeftChild())
print(r.getLeftChild().getRootVal())
r.insertRight('c')
print(r.getRightChild())
print(r.getRightChild().getRootVal())
r.getRightChild().setRootVal('hello')
print(r.getRightChild().getRootVal())

a
None
<__main__.BinaryTree object at 0x7f83a44e9c88>
b
<__main__.BinaryTree object at 0x7f83a44e5898>
c
hello


### Parse Tree¶

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.
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.
3. If the current token is a number, set the root value of the current node to the number and return to the parent.
4. If the current token is a ')', go to the parent of the current node.
In [54]:
from pythonds.basic.stack import Stack
from pythonds.trees.binaryTree import BinaryTree
def buildParseTree(fpexp):
fplist = fpexp.split()
pStack = Stack()
eTree = BinaryTree('')
pStack.push(eTree)
currentTree = eTree
for i in fplist:
if i == '(':
currentTree.insertLeft('')
pStack.push(currentTree)
currentTree = currentTree.getLeftChild()
elif i not in ['+', '-', '*', '/', ')']:
currentTree.setRootVal(int(i))
parent = pStack.pop()
currentTree = parent
elif i in ['+', '-', '*', '/']:
currentTree.setRootVal(i)
currentTree.insertRight('')
pStack.push(currentTree)
currentTree = currentTree.getRightChild()
elif i == ')':
currentTree = pStack.pop()
else:
raise ValueError
return eTree
pt = buildParseTree("( ( 10 + 5 ) * 3 )")
pt.postorder()  #defined and explained in the next section

3
7
9
(((4)+(5))*(7))
63
2
10
5
+
3
*

In [55]:
import operator
def evaluate(parseTree):
opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}

leftC = parseTree.getLeftChild()
rightC = parseTree.getRightChild()

if leftC and rightC:
fn = opers[parseTree.getRootVal()]
return fn(evaluate(leftC),evaluate(rightC))
else:
return parseTree.getRootVal()

evaluate(pt)

Out[55]:
45

### Tree Traversals¶

1. preorder. 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.
2. inorder. 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.
3. postorder. 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.
In [56]:
def preorder(tree):
if tree:
print(tree.getRootVal())
preorder(tree.getLeftChild())
preorder(tree.getRightChild())

preorder(pt)

*
+
10
5
3

In [57]:
def preorder(self):
print(self.key)
if self.leftChild:
self.left.preorder()
if self.rightChild:
self.right.preorder()

In [58]:
def postorder(tree):
if tree != None:
postorder(tree.getLeftChild())
postorder(tree.getRightChild())
print(tree.getRootVal())

postorder(pt)

10
5
+
3
*

In [59]:
def postordereval(tree):
opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
res1 = None
res2 = None
if tree:
res1 = postordereval(tree.getLeftChild())
res2 = postordereval(tree.getRightChild())
if res1 and res2:
return opers[tree.getRootVal()](res1,res2)
else:
return tree.getRootVal()

postordereval(pt)

Out[59]:
45
In [60]:
def inorder(tree):
if tree != None:
inorder(tree.getLeftChild())
print(tree.getRootVal())
inorder(tree.getRightChild())

inorder(pt)

10
+
5
*
3

In [61]:
def printexp(tree):
sVal = ""
if tree:
sVal = '(' + printexp(tree.getLeftChild())
sVal = sVal + str(tree.getRootVal())
sVal = sVal + printexp(tree.getRightChild())+')'
return sVal

printexp(pt)

Out[61]:
'(((10)+(5))*(3))'

### Priority Queues with Binary Heaps¶

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.

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)$.

### Binary Heap Operations¶

• BinaryHeap() creates a new, empty, binary heap.
• insert(k) adds a new item to the heap.
• findMin() returns the item with the minimum key value, leaving item in the heap.
• delMin() returns the item with the minimum key value, removing the item from the heap.
• isEmpty() returns true if the heap is empty, false otherwise.
• size() returns the number of items in the heap.
• buildHeap(list) builds a new heap from a list of keys.
In [62]:
from pythonds.trees.binheap import BinHeap

bh = BinHeap()
bh.insert(5)
bh.insert(7)
bh.insert(3)
bh.insert(11)

print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

3
5
7
11


### Binary Heap Implementation¶

In [63]:
class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0

def percUp(self,i):
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
tmp = self.heapList[i // 2]
self.heapList[i // 2] = self.heapList[i]
self.heapList[i] = tmp
i = i // 2

def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)

def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc

def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i*2] < self.heapList[i*2+1]:
return i * 2
else:
return i * 2 + 1

def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval

def buildHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while (i > 0):
self.percDown(i)
i = i - 1

bh = BinHeap()
bh.buildHeap([9,5,6,2,3])

print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

2
3
5
6
9


### Binary Search Tree Operations¶

• Map() Create a new, empty map.
• 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.
• get(key) Given a key, return the value stored in the map or None otherwise.
• del Delete the key-value pair from the map using a statement of the form del map[key].
• len() Return the number of key-value pairs stored in the map.
• in Return True for a statement of the form key in map, if the given key is in the map.
In [64]:
class TreeNode:
def __init__(self,key,val,left=None,right=None,parent=None):
self.key = key
self.leftChild = left
self.rightChild = right
self.parent = parent

def hasLeftChild(self):
return self.leftChild

def hasRightChild(self):
return self.rightChild

def isLeftChild(self):
return self.parent and self.parent.leftChild == self

def isRightChild(self):
return self.parent and self.parent.rightChild == self

def isRoot(self):
return not self.parent

def isLeaf(self):
return not (self.rightChild or self.leftChild)

def hasAnyChildren(self):
return self.rightChild or self.leftChild

def hasBothChildren(self):
return self.rightChild and self.leftChild

def replaceNodeData(self,key,value,lc,rc):
self.key = key
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self

class BinarySearchTree:

def __init__(self):
self.root = None
self.size = 0

def length(self):
return self.size

def __len__(self):
return self.size

def put(self,key,val):
if self.root:
self._put(key,val,self.root)
else:
self.root = TreeNode(key,val)
self.size = self.size + 1

def _put(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,parent=currentNode)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,parent=currentNode)

def __setitem__(self,k,v):
self.put(k,v)

def get(self,key):
if self.root:
res = self._get(key,self.root)
if res:
else:
return None
else:
return None

def _get(self,key,currentNode):
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._get(key,currentNode.leftChild)
else:
return self._get(key,currentNode.rightChild)

def __getitem__(self,key):
return self.get(key)

def __contains__(self,key):
if self._get(key,self.root):
return True
else:
return False

def delete(self,key):
if self.size > 1:
nodeToRemove = self._get(key,self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size = self.size-1
else:
raise KeyError('Error, key not in tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = self.size - 1
else:
raise KeyError('Error, key not in tree')

def __delitem__(self,key):
self.delete(key)

def spliceOut(self):
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
else:
self.parent.rightChild = None
elif self.hasAnyChildren():
if self.hasLeftChild():
if self.isLeftChild():
self.parent.leftChild = self.leftChild
else:
self.parent.rightChild = self.leftChild
self.leftChild.parent = self.parent
else:
if self.isLeftChild():
self.parent.leftChild = self.rightChild
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent

def findSuccessor(self):
succ = None
if self.hasRightChild():
succ = self.rightChild.findMin()
else:
if self.parent:
if self.isLeftChild():
succ = self.parent
else:
self.parent.rightChild = None
succ = self.parent.findSuccessor()
self.parent.rightChild = self
return succ

def findMin(self):
current = self
while current.hasLeftChild():
current = current.leftChild
return current

def remove(self,currentNode):
if currentNode.isLeaf(): #leaf
if currentNode == currentNode.parent.leftChild:
currentNode.parent.leftChild = None
else:
currentNode.parent.rightChild = None
elif currentNode.hasBothChildren(): #interior
succ = currentNode.findSuccessor()
succ.spliceOut()
currentNode.key = succ.key

else: # this node has one child
if currentNode.hasLeftChild():
if currentNode.isLeftChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.leftChild
elif currentNode.isRightChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.leftChild
else:
currentNode.replaceNodeData(currentNode.leftChild.key,
currentNode.leftChild.leftChild,
currentNode.leftChild.rightChild)
else:
if currentNode.isLeftChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.rightChild
elif currentNode.isRightChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.rightChild
else:
currentNode.replaceNodeData(currentNode.rightChild.key,
currentNode.rightChild.leftChild,
currentNode.rightChild.rightChild)

mytree = BinarySearchTree()
mytree[3]="red"
mytree[4]="blue"
mytree[6]="yellow"
mytree[2]="at"

print(mytree[6])
print(mytree[2])

yellow
at


### Balanced Binary Search Trees¶

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.

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.

$$balanceFactor=height(leftSubTree)−height(rightSubTree)$$

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.

In [65]:
def _put(self, key, val, currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key, val, currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key, val, parent=currentNode)
self.updateBalance(currentNode.leftChild)
else:
if currentNode.hasRightChild():
self._put(key, val, currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key, val, parent=currentNode)
self.updateBalance(currentNode.rightChild)

def updateBalance(self, node):
if node.balanceFactor > 1 or node.balanceFactor < -1:
self.rebalance(node)
return
if node.parent != None:
if node.isLeftChild():
node.parent.balanceFactor += 1
elif node.isRightChild():
node.parent.balanceFactor -= 1

if node.parent.balanceFactor != 0:
self.updateBalance(node.parent)

def rotateLeft(self, rotRoot):
newRoot = rotRoot.rightChild
rotRoot.rightChild = newRoot.leftChild
if newRoot.leftChild != None:
newRoot.leftChild.parent = rotRoot
newRoot.parent = rotRoot.parent
if rotRoot.isRoot():
self.root = newRoot
else:
if rotRoot.isLeftChild():
rotRoot.parent.leftChild = newRoot
else:
rotRoot.parent.rightChild = newRoot
newRoot.leftChild = rotRoot
rotRoot.parent = newRoot
rotRoot.balanceFactor = rotRoot.balanceFactor + \
1 - min(newRoot.balanceFactor, 0)
newRoot.balanceFactor = newRoot.balanceFactor + \
1 + max(rotRoot.balanceFactor, 0)

def rebalance(self, node):
if node.balanceFactor < 0:
if node.rightChild.balanceFactor > 0:
self.rotateRight(node.rightChild)
self.rotateLeft(node)
else:
self.rotateLeft(node)
elif node.balanceFactor > 0:
if node.leftChild.balanceFactor < 0:
self.rotateLeft(node.leftChild)
self.rotateRight(node)
else:
self.rotateRight(node)


### Summary of Map ADT Implementations¶

Table 1: Comparing the Performance of Different Map Implementations
operation Sorted List Hash Table Binary Search Tree AVL Tree
put O(n)$O(n)$ O(1)$O(1)$ O(n)$O(n)$ O(log2n)$O(\log_2{n})$
get O(log2n)$O(\log_2{n})$ O(1)$O(1)$ O(n)$O(n)$ O(log2n)$O(\log_2{n})$
in O(log2n)$O(\log_2{n})$ O(1)$O(1)$ O(n)$O(n)$ O(log2n)$O(\log_2{n})$
del O(n))$O(n))$ O(1)$O(1)$ O(n)$O(n)$ O(log2n)$O(\log_2{n})$