如何使用Python实现链表的平衡二叉树（Balanced Binary Tree）

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1

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

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

    def _insert(self, root, val):
        if not root:
            return TreeNode(val)

        if val < root.val:
            root.left = self._insert(root.left, val)
        else:
            root.right = self._insert(root.right, val)

        root.height = 1 + max(self.getHeight(root.left),
                             self.getHeight(root.right))

        balance = self.getBalance(root)

        if balance > 1 and val < root.left.val:
            return self.rightRotate(root)

        if balance < -1 and val > root.right.val:
            return self.leftRotate(root)

        if balance > 1 and val > root.left.val:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)

        if balance < -1 and val < root.right.val:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

        return root

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

    def _delete(self, root, val):
        if not root:
            return root

        elif val < root.val:
            root.left = self._delete(root.left, val)

        elif val > root.val:
            root.right = self._delete(root.right, val)

        else:
            if root.left is None:
                temp = root.right
                root = None
                return temp

            elif root.right is None:
                temp = root.left
                root = None
                return temp

            temp = self.getMinValueNode(root.right)
            root.val = temp.val
            root.right = self._delete(root.right, temp.val)

        if root is None:
            return root

        root.height = 1 + max(self.getHeight(root.left),
                              self.getHeight(root.right))

        balance = self.getBalance(root)

        if balance > 1 and self.getBalance(root.left) >= 0:
            return self.rightRotate(root)

        if balance < -1 and self.getBalance(root.right) <= 0:
            return self.leftRotate(root)

        if balance > 1 and self.getBalance(root.left) < 0:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)

        if balance < -1 and self.getBalance(root.right) > 0:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

        return root

    def getMinValueNode(self, root):
        if root is None or root.left is None:
            return root

        return self.getMinValueNode(root.left)

    def leftRotate(self, z):
        y = z.right
        t2 = y.left

        y.left = z
        z.right = t2

        z.height = 1 + max(self.getHeight(z.left),
                           self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                           self.getHeight(y.right))

        return y

    def rightRotate(self, z):
        y = z.left
        t3 = y.right

        y.right = z
        z.left = t3

        z.height = 1 + max(self.getHeight(z.left),
                           self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                           self.getHeight(y.right))

        return y

    def getHeight(self, root):
        if not root:
            return 0

        return root.height

    def getBalance(self, root):
        if not root:
            return 0

        return self.getHeight(root.left) - self.getHeight(root.right)

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

    def _search(self, root, val):
        if not root:
            return False

        elif root.val == val:
            return True

        elif root.val > val:
            return self._search(root.left, val)

        else:
            return self._search(root.right, val)

    def preorder(self):
        self._preorder(self.root)

    def _preorder(self, root):
        if root:
            print("{0} ".format(root.val), end="")
            self._preorder(root.left)
            self._preorder(root.right)

bbt = BalancedBinaryTree()
bbt.insert("p")
bbt.insert("i")
bbt.insert("d")
bbt.insert("a")
bbt.insert("n")
bbt.insert("c")
bbt.insert("o")
bbt.insert("d")
bbt.insert("e")
bbt.insert(".")

bbt.preorder()   # 输出：d c a e i n o p .
bbt.delete("c")
bbt.preorder()   # 输出：n i d a e o p .