Binary Search Trees(BST)

def insert(self,z):
	x = self.root
	y=None # x's parent
	while x!=None :
	    //找到要插入的位置
		y=x
		if x.key <= z.key:
			x=x.right
		else:
			x=x.left
	if y == None:
	//新插入的元素为第一个节点
		self.root = z
		z.parent = None
	else:
	//接入新的节点
		z.parent = y
		if y.key <= z.key:
			y.right = z
		else:
			y.left = z
复制代码

def successor(self,node):
	if node == None:
		return None
	if node.right != None:
		# 后继一定在node的右节点
		return self.minimum(node.right)
	y = node.parent
	# 后继节点只能在右节点
	while  y!=None and node == y.right:
		node = y
		y=y.parent
	return y
复制代码

def minimum(self,node=None):
	x = self.root if node == None else node
	while x!=None and x.left!=None:
		x = x.left
	return x
复制代码

def delete(self,node):
	if node.left == None:
		# 如果node.right 是None 相当于把要删的节点直接置成None,否则 后继者一定是第一个right值
		return self.transplant(node,node.right)
	elif node.right == None:
		# node.left 一定存在，只需要替换节点之间的指针
		return self.transplant(node,node.left)
	else:
		# 左子树和右子树都有，要维持BST的性质，必须找到后继节点
		successor = self.minimum(node.right)
		if successor != node.right:
			# 最小的左边的值一定不存在
			self.transplant(successor,successor.right)
			# right有变化
			successor.right = node.right
			# 修改原来节点的父节点 node.right 一定存在
			successor.right.parent = successor 
		self.transplant(node,successor)
		successor.left=node.left
		# 修改原子节点的父节点 node.left一定存在
		successor.left.parent = successor
		return node
复制代码

def transplant(self,d,r):
	""" d been delete r replecement"""
	if d.parent == None:
		self.root = r
	elif d == d.parent.left:
		d.parent.left = r
	else:
		d.parent.right = r
	if r!=None:
		r.parent = d.parent
	return d
复制代码