class node python_请问我的python AVL树这样号写对不对，,class Node(o

拼搏现实的明天。 2023-01-09 14:14 5阅读 0赞

请问我的python AVL树这样号写对不对，,class Node(oclass Node(object): def \_\_init\_\_(self,key): self.key=key self.left=None self.right=None self.height=0class 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 keynode.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 keynode.key: node.right=self.\_put(key,node.right) if (self.height(node.right)-self.height(node.left))==2: if key=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语言的实现方式，定义结构体的时候也没有父结点这回事，请问如何实现才能保证查找准确，这个代码是否有问题？

编橙之家文章，