AVL树：解决BST可能导致的长链问题

1  
\  
 2 
  \ 
   3
需要进行一次左旋
  2  
 / \ 
1   3
复制代码

1  
 \ 
  3 
 / 
2
先右旋
1  
 \  
  2 
  \ 
   3
再左旋
  2  
 / \ 
1   3
复制代码

   3 
  / 
 2  
/  
1 
右旋
  2  
 / \ 
1  3
复制代码

 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)
复制代码