Binary Search Tree - Python
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
class Node(object):
def __init__(self, value = None):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.length = 0
self.root = None
def isEmpty(self):
return self.length == 0
def insert(self, value):
cur = self.root
newNode = Node(value)
depth = 1
if not cur:
self.root = newNode
self.length += 1
return depth
while cur:
if value < cur.value:
if not cur.left:
cur.left = newNode
self.length += 1
return depth
cur = cur.left
depth += 1
elif value > cur.value:
if not cur.right:
cur.right = newNode
self.length += 1
return depth
cur = cur.right
depth += 1
else:
return -1
return depth
def search(self, value):
cur = self.root
while cur:
if value < cur.value:
cur = cur.left
elif value > cur.value:
cur = cur.right
else:
return cur
return False
def remove(self, value):
if not self.root:
return false
cur = self.root
parent = None
while cur:
if value < cur.value:
parent = cur
cur = cur.left
elif value > cur.value:
parent = cur
cur = cur.right
elif cur.value == value:
# No right child
if not cur.right:
if not parent:
this.root = currentNode.left;
else:
if cur.value < parent.value:
parent.left = cur.left
elif cur.value > parent.value:
parent.right = cur.left
elif not cur.right.left:
cur.right.left = cur.left
if not parent:
self.root = cur.right;
else:
if cur.value < parent.value:
parent.left = cur.right
elif cur.value > parent.value:
parent.right = cur.right
else:
lMost = cur.right.left
lMostParent = cur.right
while lMost.left:
lMostParent = lMost
lMost = lMost.left
lMostParent.left = leftmost.right
lMost.left = cur.left
lMost.right = cur.right
if not parent:
self.root = lMost
else:
if currentNode.value < parentNode.value:
parent.left = lMost
elif cur.value > parent.value:
parent.right = lMost
self.length -= 1
return True
myBST = BST()
myBST.insert(4)
myBST.insert(10)
myBST.insert(1)
myBST.insert(3)
myBST.insert(5)
print(myBST.search(3))
print(myBST.search(5))
print(myBST.length)
myBST.remove(10)
print(myBST.length)
print(myBST.search(10))
Python
INFO