class Node:
'''represents a new node in the BST'''
def __init__(self,key):
self.key=key
self.disconnect()
def disconnect(self):
self.left=None;
self.right=None;
self.parent=None;
def __str__(self):
return 'node with kay %s'%self.key
class BST:
def __init__(self):
self.root=None
def insert(self,t):
'''inserts a new element into the tree'''
self.find_place(self.root,t)
def find_place(self,node,key):
"""finds the right place of the element recursively"""
if node is None:
node=Node(key)
print node
else:
if node.key > key:
find_place(node.left,key)
else:
find_place(node.right,key)
def test():
'''function to test if the BST is working correctly'''
i wrote the above code to implement a binary search tree but the insert method is not working as expected , it fails to add even the root element . i can't undestand the cause.
-
See stackoverflow.com/questions/3058665/…gimel– gimel2010年06月20日 07:48:31 +00:00Commented Jun 20, 2010 at 7:48
2 Answers 2
You're not actually adding any nodes to the tree!
Its easiest to manage the adding of the root node explicitly, as you see I did below in the insert.
A find_place function would, presumably from the name, return the parent node and also whether it's the left or right slot for the key? I've made an explicit _do_insert function below that both walks and does the insert.
From then on, you need to walk the tree, each time seeing if you recurse down a branch or whether you've reached an empty slot, where you add the new node.
It might be natural to refactor your code to put responsibility for walking the tree (and doing adds, removes and such) into the Node class.
In the code below, I ignore adding a key that is already in the tree, I just silently exit:
def insert(self,t):
'''inserts a new element into the tree'''
if self.root is None:
self.root = Node(t)
else:
self._do_insert(self.root,t)
def _do_insert(self,parent,t):
if t > parent.key:
if parent.left is None:
parent.left = Node(t)
else:
self._do_insert(parent.left,t)
elif t < parent.key:
if parent.right is None:
parent.right = Node(t)
else:
self._do_insert(parent.right,t)
else:
# raise a KeyError or something appropriate?
pass
Comments
Here is another BST with Python, using a sorting key
LEFT = 0 RIGHT = 1 VALUE = 2 SORT_KEY = -1
class BinarySearchTree(object):
def __init__(self, sort_key=None):
self._root = []
self._sort_key = sort_key
self._len = 0
def insert(self, val): if self._sort_key is None: sort_key = val // if no sort key, sort key is value else: sort_key = self._sort_key(val)
node = self._root
while node:
if sort_key < node[_SORT_KEY]:
node = node[LEFT]
else:
node = node[RIGHT]
if sort_key is val:
node[:] = [[], [], val]
else:
node[:] = [[], [], val, sort_key]
self._len += 1
def minimum(self):
return self._extreme_node(LEFT)[VALUE]
def maximum(self):
return self._extreme_node(RIGHT)[VALUE]
def find(self, sort_key):
return self._find(sort_key)[VALUE]
def _extreme_node(self, side):
if not self._root:
raise IndexError('Empty')
node = self._root
while node[side]:
node = node[side]
return node
def _find(self, sort_key):
node = self._root
while node:
node_key = node[SORT_KEY]
if sort_key < node_key:
node = node[LEFT]
elif sort_key > node_key:
node = node[RIGHT]
else:
return node
raise KeyError("%r not found" % sort_key)
Sort key is replaced by value if any.
Comments
Explore related questions
See similar questions with these tags.