Ternary-search-trees
class Node(object):
def __init__(self, character):
self.character = character
self.leftNode = None
self.middleNode = None
self.rightNode = None
self.value = 0
class TST(object):
def __init__(self):
self.rootNode = None
def put(self, key, value):
self.rootNode = self.putItem(self.rootNode, key, value, 0)
def putItem(self, node, key, value, index):
c = key[index]
if node is None:
node = Node(c)
if c < node.character:
node.leftNode = self.putItem(node.leftNode, key, value, index)
elif c > node.character:
node.rightNode = self.putItem(node.rightNode, key, value, index)
elif index < len(key) - 1:
node.middleNode = self.putItem(node.middleNode, key, value,
index + 1)
else:
node.value = value
return node;
def get(self, key):
node = self.getItem(self.rootNode, key, 0)
if node is None:
return -1
return node.value
def getItem(self, node, key, index):
if node is None:
return None
c = key[index]
if c < node.character:
return self.getItem(node.leftNode, key, index)
elif c > node.character:
return self.getItem(node.rightNode, key, index)
elif index < len(key) - 1:
return self.getItem(node.middleNode, key, index + 1)
else:
return node
if __name__ == "__main__":
tst = TST()
tst.put("apple", 100)
tst.put("orange", 200)
print(tst.get("orange"))
Last updated