AVL树（平衡二叉树）
#节点类。AVL树相对一般二叉搜索树，节点增加树高属性，便于判断是否平衡，从而决定是否进行调整等。 class Node: def __init__(self, data = -1, height = 1, left = None, right = None): self.data = data self.left = left self.right = right self.height = height def __str__(self): return str(self.data)
class AVLTree: def __init__(self, root=None): self.root = root # 增加一些公有私有机制 def find(self, data): if self.root == None: return None return self.__find(self.root, data) def __find(self, root, data): if root == None: return None if root.data == data: return root elif root.data < data: return self.__find(root.right, data) else: return self.__find(root.left, data) def height(self): if self.root == None: return 0 return self.root.height def __update(self, root): root.height = 1 if root.left != None: root.height = max(root.height, root.left.height + 1) if root.right != None: root.height = max(root.height, root.right.height + 1) def __left_rotate(self, root): tmp = root.right root.right = tmp.left tmp.left = root self.__update(root) self.__update(tmp) return tmp def __right_rotate(self, root): tmp = root.left root.left = tmp.right tmp.right = root self.__update(root) self.__update(tmp) return tmp def get_pre(self, root): tmp = root.left while tmp.right != None: tmp = tmp.right return tmp def insert(self, data): self.root = self.__insert(self.root, data) def __insert(self, root, data): if root == None: return Node(data) if root.data == data: return root if root.data < data: root.right = self.__insert(root.right, data) else: root.left = self.__insert(root.left, data) self.__update(root) return self.__maintain(root) def delete(self, data): self.root = self.__delete(self.root, data) def __delete(self, root, data): if root == None: return root if root.data < data: root.right = self.__delete(root.right, data) elif root.data > data: root.left = self.__delete(root.left, data) else: if root.left == None or root.right == None: tmp = root.left if root.left != None else root.right del root return tmp tmp = self.get_pre(root) root.data = tmp.data root.left = self.__delete(root.left, tmp.data) self.__update(root) return self.__maintain(root) def __maintain(self, root): left_h = root.left.height if root.left != None else 0 right_h = root.right.height if root.right != None else 0 if abs(left_h - right_h) <= 1: return root if left_h > right_h: lright_h = root.left.right.height if root.left.right != None else 0 lleft_h = root.left.left.height if root.left.left != None else 0 if lright_h > lleft_h: root.left = self.__left_rotate(root.left) root = self.__right_rotate(root) else: rleft_h = root.right.left.height if root.right.left != None else 0 rright_h = root.right.right.height if root.right.right != None else 0 if rleft_h > rright_h: root.right = self.__right_rotate(root.right) root = self.__left_rotate(root) return root def inorder(self, root): if root is None: return [] res = [root.data] left_res = self.inorder(root.left) right_res = self.inorder(root.right) return left_res + res + right_res
测试代码：
t = AVLTree() def printf(): res = t.inorder(t.root) for i in res: print("{0}:({1}, {2})".format(t.find(i), t.find(i).left, t.find(i).right)) print("root =", t.root, "h =", t.height()) print() for i in range(1, 10): t.insert(i) printf()
总结
这里的写法有点臃肿，主要是对于不存在的节点None，取不到height属性。所以对此需要if特判，取得默认None情况的height为0值。
然后就是平衡二叉树，基操就是进行旋转，回溯过程中，哪个地方不平衡了就立即调整，其它都同正常的BST。
还有一点就是写法问题，这次是用了_+name的形式书写方法名，化作私有方法，简而言之就是进行了多一层的封装，对外接口更加方便。对比上一个BST，我将节点的增删改查等方法以静态方法的形式，封装在Node类中，应该是各有优势吧。（不是
下一篇进攻红黑树，对问题一的写法会有一个优化。话说就是这脑瘫的写法，搞得我debug半个钟。（节点树高的维护出错了，原因是__update() 方法中没加赋值那条语句）
