Python递归实现平衡树数据结构

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.key = key

class AVLTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if not node:
            return Node(key)
        elif key < node.key:
            node.left = self._insert(node.left, key)
        else:
            node.right = self._insert(node.right, key)

        node = self._balance(node)
        return node

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, node, key):
        if not node:
            return node
        elif key < node.key:
            node.left = self._delete(node.left,key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            if not node.left and not node.right:
                node = None
            elif not node.left:
                node = node.right
            elif not node.right:
                node = node.left
            else:
                temp = self._findMin(node.right)
                node.key = temp.key
                node.right = self._delete(node.right, temp.key)

        if not node:
            return node

        node = self._balance(node)
        return node

    def _findMin(self, node):
        while node.left:
            node = node.left
        return node

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if not node:
            return False
        elif node.key == key:
            return True
        elif key < node.key:
            return self._search(node.left, key)
        else:
            return self._search(node.right, key)

    def inorder(self):
        self._inorder(self.root)
        print()

    def _inorder(self, node):
        if node:
            self._inorder(node.left)
            print(node.key, end=' ')
            self._inorder(node.right)

    def _height(self, node):
        if not node:
            return 0
        return max(self._height(node.left), self._height(node.right)) + 1

    def _balanceFactor(self, node):
        return self._height(node.left) - self._height(node.right)

    def _rotateRight(self, node):
        newRoot = node.left
        node.left = newRoot.right
        newRoot.right = node
        return newRoot

    def _rotateLeft(self, node):
        newRoot = node.right
        node.right = newRoot.left
        newRoot.left = node
        return newRoot

    def _balance(self, node):
        if not node:
            return node

        if self._balanceFactor(node) > 1:
            if self._balanceFactor(node.left) < 0:
                node.left = self._rotateLeft(node.left)
            node = self._rotateRight(node)
        elif self._balanceFactor(node) < -1:
            if self._balanceFactor(node.right) > 0:
                node.right = self._rotateRight(node.right)
            node = self._rotateLeft(node)

        return node

if __name__ == '__main__':
    tree = AVLTree()
    keys = ["pidancode.com", "皮蛋编程", "Hello", "World", "Python", "Google", "AI", "Algorithm"]
    for key in keys:
        tree.insert(key)

    print("Inorder traversal of the constructed AVL tree is:")
    tree.inorder()

    key = "Python"
    tree.delete(key)
    print("\nKey: [" + key + "] deleted from AVL tree")

    print("Inorder traversal of the modified AVL tree is:")
    tree.inorder()

    key = "pidancode.com"
    if tree.search(key):
        print("\nKey: [" + key + "] found in AVL tree")
    else:
        print("\nKey: [" + key + "] not found in AVL tree")

    key = "Hello World"
    if tree.search(key):
        print("Key: [" + key + "] found in AVL tree")
    else:
        print("Key: [" + key + "] not found in AVL tree")

Inorder traversal of the constructed AVL tree is:
AI Google Hello World Python pidancode.com Algorithm 皮蛋编程 

Key: [Python] deleted from AVL tree
Inorder traversal of the modified AVL tree is:
AI Google Hello World pidancode.com Algorithm 皮蛋编程 

Key: [pidancode.com] found in AVL tree
Key: [Hello World] not found in AVL tree