如何实现TreeNode的平衡

要实现一个平衡的树，通常我们会使用 AVL 树或红黑树。这里我将简要介绍如何实现一个简单的 AVL 树。

AVL 树是一种自平衡二叉搜索树，它的每个节点的左子树和右子树的高度差不超过 1。为了实现一个 AVL 树，我们需要定义一个 TreeNode 类，并实现插入、删除和平衡等操作。

首先，定义一个 TreeNode 类：

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

接下来，实现插入操作。在插入节点时，我们需要更新节点的高度，并检查树是否平衡。如果不平衡，我们需要进行相应的旋转操作来恢复平衡。

class AVLTree:
    def insert(self, root, key):
        if not root:
            return TreeNode(key)
        elif key< root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

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

        balance = self.get_balance(root)

        # Left Left Case
        if balance > 1 and key< root.left.key:
            return self.right_rotate(root)

        # Right Right Case
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)

        # Left Right Case
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # Right Left Case
        if balance < -1 and key< root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def get_height(self, root):
        if not root:
            return 0
        return root.height

    def get_balance(self, root):
        if not root:
            return 0
        return self.get_height(root.left) - self.get_height(root.right)

    def left_rotate(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

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

        return y

    def right_rotate(self, y):
        x = y.left
        T2 = x.right

        x.right = y
        y.left = T2

        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))

        return x

类似地，你可以实现删除操作，并在删除节点时检查树是否平衡。如果不平衡，进行相应的旋转操作来恢复平衡。

注意：这里给出的代码仅作为实现 AVL 树的参考，你可能需要根据自己的需求进行调整和优化。