class RadixTree(object):
	tree = {"ab":{"c":"エビゾー", "e": "阿部総理", "": "fuck"}}
	def __init__(self):
		pass
	def add(self, path, answer, parent=None):
		if parent == None:
			parent = self.tree
		for branch in parent.keys():
			if path[:len(branch)] == branch and isinstance(parent[branch], dict):
					ans = parent[branch]
					if (len(path) - len(branch)) == 0:
						ans[path[len(branch):]] = answer
						return ans
					else:
						parent[path[len(branch):]] = self.add(path[len(branch):], answer, parent=ans)
						return parent
		parent[path] = answer
		return parent

	def search(self, path, branches=None):
		if branches == None:
			branches = self.tree
		for branch in branches.keys():
			if path[:len(branch)] == branch:
				if isinstance(branches[branch], str):
					if branch == path:
						return branches[branch]
					else:
						continue
				return self.search(path[len(branch):],branches[branch])




e = RadixTree()
e.search("abc")
e.add("ebizo", "えびぞう")