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

BST存在的问题

BST的性质有可能导致所有的数据都插在了同一个链路上，导致没有一个节点有左子树，都是右子树，像是一个链表，失去了它的lgn的性质

AVL的性质

AVL是作者的名字缩写

每个左子树的高度与右子树的高度差值不大于1

如果是AVL BST需要只需要在BST的基础上加上AVL的性质，AVL本身需要去维护高度

一个AVL树，除去根节点这层，至少包含的左右两部分为:一边是高度为h-1,另一边是高度为h-2

AVL树 BST的插入

插入过程中，一旦出现层级超过1的情况，需要进行旋转，而对应出现2层的高度差别，只会出现如下4种

• 情况1：

代码语言：javascript复制

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

• 情况2

代码语言：javascript复制

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

• 情况3

代码语言：javascript复制

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

• 情况4

代码语言：javascript复制

 3 
/  
1  
  
 2
对1进行左旋
   3 
  / 
 2  
/  
1
再右旋
  2  
 /  
1  3
复制代码

保持平衡的算法为

代码语言：javascript复制

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

左旋

代码语言：javascript复制

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

右旋

代码语言：javascript复制

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

代码详情

链表

0 人点赞