BST的性质
BST的形状为
- 每个BST中的节点x,存在一个key,一个指向父节点的parent指针,同时还有一个左子树和右子树
root的parent不存在
- 左子树值y与父节点x满足 key(y) <= key(x),右子树z满足 key(x) <=key(z)
插入实现机制
假设元素的插入顺序为30,40,17,20,14 刚开始的时候没有元素,插入新的元素
然后插入第二个元素40,它比30要大,置为它的右节点
插入第三个元素17,比30要小,置为它的左节点
然后是20,比30小,找到做子树,左子树的节点值为17,再次比较
最后一次元素再次插入,得到最终的BST结构
代码语言:javascript复制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
复制代码
它的耗时为O(lgn)
找到后继节点
后继节点即从值上来讲,找到比要找的元素要大最接近的值,根据BST的性质,它肯定在右子树上,所以如果存在存在右子树,就是右子树上的最小值,否则回溯到父节点,直到父节点不存在,或者遇到第一个不存在右节点关系的父子节点即得到后继值
代码语言:javascript复制17的后继是20,即17的右子树的节点;
20的后继是30,由于20没有右子树,会先回溯到17,然后17是它的父节点的左子树,那么它就是后继节点;
40的后继不存在;
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
复制代码
最小值则一直递归到左子树没有节点即可
代码语言:javascript复制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
复制代码
删除节点
节点删除之后,必须要维持原有的BST性质
- 删除节点13,它一个子节点都没有,直接删除即可
- 删除节点16,只有右节点,直接有右节点替代即可
- 删除5,它既有左子树又有右子树,需要找到后继补上
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
复制代码
指针变换关系为
代码语言:javascript复制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
复制代码
代码详情