BST存在的问题
BST的性质有可能导致所有的数据都插在了同一个链路上，导致没有一个节点有左子树，都是右子树，像是一个链表，失去了它的lgn的性质
AVL的性质
AVL是作者的名字缩写
每个左子树的高度与右子树的高度差值不大于1
如果是AVL+BST需要只需要在BST的基础上加上AVL的性质，AVL本身需要去维护高度
另为在一个高度为h的AVL中节点的最少的数量，有
一个AVL树，除去根节点这层，至少包含的左右两部分为:一边是高度为h-1,另一边是高度为h-2
从上式可得：，即h<2lgn,因而得到AVL的高度肯定是lgn
AVL树+BST的插入
插入过程中，一旦出现层级超过1的情况，需要进行旋转，而对应出现2层的高度差别，只会出现如下4种
- 情况1：
1
\
2
\
3
需要进行一次左旋
2
/ \
1 3
- 情况2
1
\
3
/
2
先右旋
1
\
2
\
3
再左旋
2
/ \
1 3
- 情况3
3
/
2
/
1
右旋
2
/ \
1 3
- 情况4
3
/
1
\
2
对1进行左旋
3
/
2
/
1
再右旋
2
/ \
1 3
保持平衡的算法为
def _reblance(self,node):
while node is not None:
self._update_height(node)
if self._height(node.left) - self._height(node.right) >=2:
//左子树要高
nodeL = node.left
if self._height(nodeL.left) < self._height(nodeL.right):
//情况4
self._left_roate(nodeL)
//情况3+情况4
self._right_roate(node)
elif self._height(node.right) - self._height(node.left) >=2:
//右子树要高
nodeR = node.right
if self._height(nodeR.left) > self._height(nodeR.right):
//情况2
self._right_roate(nodeR)
//情况1+情况2
self._left_roate(node)
node = node.parent
左旋
def _left_roate(self,node):
'''当前节点的右节点高度-左节点高度>=2
从上到下，按照父子一对一对处理
'''
pivot = node.right
pivot.parent = node.parent
if node == self.root:
self.root = pivot
else:
if node.parent.left is node:
pivot.parent.left = pivot
else:
pivot.parent.right = pivot
tempNode = pivot.left
pivot.left = node
node.parent = pivot
node.right = tempNode
if tempNode is not None:
tempNode.parent = node
self._update_height(pivot)
self._update_height(node)
右旋
def _right_roate(self,node):
'''当前节点的左节点高度-右节点高度>=2
右旋表示左边节点高
'''
pivot=node.left
pivot.parent = node.parent
if node == self.root:
self.root=pivot
else:
if node.parent.left is node:
pivot.parent.left = pivot
else:
pivot.parent.right = pivot
node.parent = pivot
tempNode = pivot.right
pivot.right = node
node.left = tempNode
if tempNode is not None:
tempNode.parent = node
self._update_height(pivot)
self._update_height(node)
