AVL算法小疑惑

为了简洁明晰,找了一个AVL树python的实现,贴上代码:

  
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

疑问就是:当第一个破坏了平衡失衡点不是根结点的时候,无论在何种情况如何旋转,都没有考虑到其父结点的指针指向问题,这样查找应该是会出问题的,是我没看懂还是什么?我翻看过C语言的实现方式,定义结构体的时候也没有父结点这回事,请问如何实现才能保证查找准确,这个代码是否有问题?

评论 (1)链接2014-05-09 
  • 0 支持
    没人会的吗? – LeonWong 2014-05-12
德问是一个专业的编程问答社区,请 登录注册 后再提交答案