## 数据结构入门，讨论一个AVL树问题

wang_liran 发布于 2014/05/09 15:37

```class Node(object):
def __init__(self,key):
self.key=key
self.left=None
self.right=None
self.height=0
class AVLTree(object):
def __init__(self):
self.root=None
def find(self,key):
if self.root is None:
return None
else:
return self._find(key,self.root)
def _find(self,key,node):
if node is None:
return None
elif key<node.key:
return self._find(key,self.left)
elif key>node.key:
return self._find(key,self.right)
else:
return node
def findMin(self):
if self.root is None:
return None
else:
return self._findMin(self.root)
def _findMin(self,node):
if node.left:
return self._findMin(node.left)
else:
return node
def findMax(self):
if self.root is None:
return None
else:
return self._findMax(self.root)
def _findMax(self,node):
if node.right:
return self._findMax(node.right)
else:
return node
def height(self,node):
if node is None:
return -1
else:
return node.height

def singleLeftRotate(self,node):
k1=node.left
node.left=k1.right
k1.right=node
node.height=max(self.height(node.right),self.height(node.left))+1
k1.height=max(self.height(k1.left),node.height)+1
return k1
def singleRightRotate(self,node):
k1=node.right
node.right=k1.left
k1.left=node
node.height=max(self.height(node.right),self.height(node.left))+1
k1.height=max(self.height(k1.right),node.height)+1
return k1
def doubleLeftRotate(self,node):
node.left=self.singleRightRotate(node.left)
return self.singleLeftRotate(node)
def doubleRightRotate(self,node):
node.right=self.singleLeftRotate(node.right)
return self.singleRightRotate(node)
def put(self,key):
if not self.root:
self.root=Node(key)
else:
self.root=self._put(key,self.root)
def _put(self,key,node):
if node is None:
node=Node(key)
elif key<node.key:
node.left=self._put(key,node.left)
if (self.height(node.left)-self.height(node.right))==2:
if key<node.left.key:
node=self.singleLeftRotate(node)
else:
node=self.doubleLeftRotate(node)

elif key>node.key:
node.right=self._put(key,node.right)
if (self.height(node.right)-self.height(node.left))==2:
if key<node.right.key:
node=self.doubleRightRotate(node)
else:
node=self.singleRightRotate(node)

node.height=max(self.height(node.right),self.height(node.left))+1
return node

def delete(self,key):
self.root=self.remove(key,self.root)
def remove(self,key,node):
if node is None:
raise KeyError,'Error,key not in tree'
elif key<node.key:
node.left=self.remove(key,node.left)
if (self.height(node.right)-self.height(node.left))==2:
if self.height(node.right.right)>=self.height(node.right.left):
node=self.singleRightRotate(node)
else:
node=self.doubleRightRotate(node)
node.height=max(self.height(node.left),self.height(node.right))+1

elif key>node.key:
node.right=self.remove(key,node.right)
if (self.height(node.left)-self.height(node.right))==2:
if self.height(node.left.left)>=self.height(node.left.right):
node=self.singleLeftRotate(node)
else:
node=self.doubleLeftRotate(node)
node.height=max(self.height(node.left),self.height(node.right))+1

elif node.left and node.right:
if node.left.height<=node.right.height:
minNode=self._findMin(node.right)
node.key=minNode.key
node.right=self.remove(node.key,node.right)
else:
maxNode=self._findMax(node.left)
node.key=maxNode.key
node.left=self.remove(node.key,node.left)
node.height=max(self.height(node.left),self.height(node.right))+1
else:
if node.right:
node=node.right
else:
node=node.left

return node
```

0