## AVL树添加及自旋python实现

Python 实现 自旋 添加 avl

``````from collections import deque
from dataStructures.tree.biTree.bst import BiTreeNode, BST
class AVLNode(BiTreeNode):
def __init__(self, data):
BiTreeNode.__init__(self, data)
self.bf = 0 #存平衡因子
class AVLTree(BST):
def __init__(self, li=None):
BST.__init__(self, li)
def rotate_left(self, p, c):
#c是当前node，p是node.parent
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 rotate_right(self, p, c):
s2 = c.rchild
p.lchild = s2
if s2:
s2.parent = p
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
c.lchild = s3
if s3:
s3.parent = c
g.rchild = c
c.parent = g
s2 = g.lchild
p.rchild = s2
if s2:
s2.parent = p
g.lchild = p
p.parent = g
# 更新bf（右边-左边）
# （1）插入s3
if g.bf > 0:
p.bf = -1
c.bf = 0
# （2）插入s2
elif g.bf < 0:
p.bf = 0
c.bf = 1
else: # 插入的是g
p.bf = 0
c.bf = 0
# 插入的是g（意味着s1、s2、s3、s4为空）
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:
p.bf = 0
c.bf = 0
return g
def insert_no_rec(self, val):
# 1. 和BST一样，插入
p = self.root
if not p: # 空树
self.root = AVLNode(val)
return
while True:
if val < p.data:
if p.lchild:
p = p.lchild # node存储就是插入的结点
else: # 左孩子不存在
p.lchild = AVLNode(val)
p.lchild.parent = p
node = p.lchild # node 存储的就是插入的节点
break
elif val > p.data:
if p.rchild:
p = p.rchild
else:
p.rchild = AVLNode(val)
p.rchild.parent = p
node = p.rchild
break
else: # val == p.data
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哪边沉
g = node.parent.parent # 为了连接旋转之后的子树
x = node.parent # 旋转前的子树的根
#从当前node.bf判断是左边插入还是右边
if node.bf > 0:
n = self.rotate_left_right(node.parent, node) # n为旋转之后子树的头节点
else:
n = self.rotate_right(node.parent, node)
# 记得：把n和g连起来
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: # 传递是从右子树来的，右子树更沉了
#更新node.parent.bf += 1
if node.parent.bf > 0: # 原来node.parent.bf == 1, 更新后变成2
# 做旋转
# 看node哪边沉
g = node.parent.parent # 为了连接旋转之后的子树
x = node.parent # 旋转前的子树的根
#由此判断是父节点的左子树还是右子树
if node.bf < 0: # node.bf = -1
#右左结构
n = self.rotate_right_left(node.parent, node)
else: # node.bf = 1
#右右结构
n = self.rotate_left(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
# 链接旋转后的子树
n.parent = g
if g: # g不是空
#判断原来是在左孩子还是右孩子
if x == g.lchild:
g.lchild = n
else:
g.rchild = n
break
else:
self.root = n
break
def level_order(self, root):
queue = deque()
queue.append(root)
while len(queue) > 0:
node = queue.popleft()
print(node.data, end=',')
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
tree = AVLTree([10,5,0])
``````

https://www.cnblogs.com/szq95716/p/13973569.html