建立AVL树
class AVLNode(object):
def __init__(self,data):
self.data = data
self.lchild = None
self.rchild = None
self.parent = None
self.bf = 0 class AVLTree(object)
def __init__(self,li=None)
self.root = None
if li:
for val in li:
self.insert(self.root,val) def insert(self,node,val):
if not node:
node = AVLNode(val)
elif val < node.data:
node.lchild = self.insert(node.lchild,val)
node.lchild.parent = node
elif val > node.data:
node.rchild = self.insert(node.rchild,val)
node.rchild.parent = node
return node
左旋转、右旋转
def rorate_left(self,p,c):
s2 = c.lchild
p.rchild = s2
if s2:
s2.parent = p
c.lchild = p
p.parent = c
p.bf = 0
c.bf = 0
return c def rorate_right(self,p,c):
s2 = c.rchild
p.lchild = s2
if s2:
s2.parent
c.rchild = p
p.parent = c
p.bf = 0
c.bf = 0
return c
右→左旋转、左→右旋转
def rotate_right_left(self,p,c):
g = c.lchild #右旋
s3 = g.rchild #1.把右孩子拿出来
c.lchild = s3 #2.右孩子交给 C
if s3:
s3.parent = c
g.rchild = c #3.链接右孩子
c.parent = g #4.链接父结点 #左旋
s2 = g.lchild
p.rchild = s2
if s2:
s2.parent = p
g.lchild = p
p.parent = g #更新bf
if g.bf > 0: #插入到s3 #是指刚插入节点的g的平衡值
p.bf = -1
c.bf = 0
elif g.bf < 0: #插入到s2
p.bf = 0
c.bf = 1
else: #插入的是G本身
p.bf = 0
c.bf = 0
g.bf = 0
return g def rotate_left_right(self,p,c):
g = c.rchild #左旋
s2 = g.lchild
c.rchild = s2
if s2:
s2.parent = c
g.lchild = c
c.parent = g #右旋
s3 = g.rchild
p.lchild = s3
if s3:
s3.parent = p
g.rchild = p
p.parent = g #更新bf
if g.bf < 0: #插入到s2
p.bf = 1
c.bf = 0
elif g.bf > 0: #插入到s3
p.bf = 0
c.bf = -1
else: #插入的是G本身
p.bf = 0
c.bf = 0
g.bf = 0
return g
插入
def insert_no_rec(self,val):
#1.插入
p = self.root
if not p:
self.root = AVLNode(val)
return
while True:
if val < p.data:
if p.lchild: #左孩子存在
p = p.lchild
else: #左孩子不存在
p.lchild = AVLNode(val)
p.lchild.parent = p
node = p.lchild #node 存储的就是插入的节点
break
else val > p.data:
if p.rchild:
p = p.rchild
else:
p.rchild = AVLNode(val)
p.rchild.parent = p
node = p.rchild
break
else: #等于 #同样的元素不多次插入
#avl尽量不允许两个相同的数插入
return #2.更新balance factor
while node.parent: #node.parent 不为空时
if node.parent.lchild == node: #传递节点是在左子树,左子树更沉了
#第一乱循环,更新node.parent的bf -= 1
if node.parent.bf < 0: #原来node.parent.bf == -1 (更新后会变成-2)
# 做旋转
# 看node哪边沉
head = node.parent.parent #为了链接旋转之后的子树
tmp = node.parent #旋转前的子树的根
if node.bf > 0:
n = self.rotate_left_right(node.parent,node)
else:
n = self.rorate_right(node.parent,node)
elif node.parent.bf > 0: #原来node.parent.bf == 1 (更新后变成0)
node.parent.bf = 0 #平衡,即可以不需要确认父亲节点
break
else: #原来node.parent.bf = 0,更新之后变成-1
node.parent.bf = -1
node = node.parent
continue
else: #传递节点是在右子树,右子树更沉了
if node.parent.bf > 0:
head = node.parent.parent
tmp = node.parent
if node.bf < 0:
n = self.rotate_right_left(node.parent,node)
else:
n = self.rorate_left(node.parent,node)
elif node.parent.bf < 0:
node.parent.bf = 0
break
else:
node.parent.bf = 1
node = node.parent
continue #3.链接旋转后的子树(只有做了旋转之后才会到这一步)
n.parent = head
if head: #head不是空
if tmp == head.lchild:
head.lchild = n
else:
head.rchild = n
break
else:
self.root = n
break