Python实现二叉排序树与平衡二叉树的示例代码

现在让我们来详细讲解如何使用Python实现二叉排序树与平衡二叉树。

二叉排序树

二叉排序树（BST）是一种特殊的二叉树，它的每个节点最多有两个子节点，左子节点的值比父节点小，右子节点的值比父节点大。因此，二叉排序树可以很好地存储和快速查找有序数据。

实现过程

1. 定义节点类

我们首先需要定义二叉排序树的节点类，它至少需要包含以下属性：

• value：存储节点的值
• left：存储左子节点的引用
• right：存储右子节点的引用

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

1. 插入节点

对于一个没有任何节点的空树，我们将插入第一个节点作为根节点，否则我们需要通过递归查找合适的插入位置。

def insert_node(root, value):
    if root is None:
        root = TreeNode(value)
    elif root.value > value:
        root.left = insert_node(root.left, value)
    elif root.value < value:
        root.right = insert_node(root.right, value)
    return root

1. 删除节点

删除节点是二叉排序树中比较常见的操作，我们需要实现以下两个删除节点的函数：

• 查找待删除节点
• 删除节点

def find_node(root, value):
    if root is None or root.value == value:
        return root
    elif root.value > value:
        return find_node(root.left, value)
    else:
        return find_node(root.right, value)


def delete_node(root, value):
    if root is None:
        return root
    if root.value == value:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        else:
            min_node = find_min_node(root.right)
            root.value = min_node.value
            root.right = delete_node(root.right, min_node.value)
    elif root.value > value:
        root.left = delete_node(root.left, value)
    else:
        root.right = delete_node(root.right, value)
    return root


def find_min_node(root):
    while root.left is not None:
        root = root.left
    return root

示例

现在让我们通过一个示例来理解二叉排序树的使用。

我们现在有一组数据[5, 6, 2, 8, 3, 1, 4]，我们可以通过以下代码将它们插入二叉排序树中并进行中序遍历来验证插入操作是否正确。

def inorder_traverse(root, values):
    if root is not None: 
        inorder_traverse(root.left, values) 
        values.append(root.value) 
        inorder_traverse(root.right, values) 
    return values


if __name__ == '__main__':
    nums = [5, 6, 2, 8, 3, 1, 4]
    root = None
    for num in nums:
        root = insert_node(root, num)
    res = inorder_traverse(root, [])
    print(res)   # [1, 2, 3, 4, 5, 6, 8]
    root = delete_node(root, 5)
    res = inorder_traverse(root, [])
    print(res)   # [1, 2, 3, 4, 6, 8]

注意我们还演示了删除节点的操作。

平衡二叉树

平衡二叉树（AVL Tree）是一种二叉排序树，但相比于二叉排序树，它的左右子树的高度差不能超过1，这样可以确保树的高度平衡，插入和查找操作的时间复杂度可以保证在O(logn)。

实现过程

平衡二叉树实现起来比较复杂，我们需要先了解如何计算平衡因子，并实现旋转操作。

1. 计算平衡因子

平衡因子：左子树的高度减去右子树的高度。

我们可以通过以下代码计算节点的平衡因子：

def get_height(root):
    if root is None:
        return 0
    return max(get_height(root.left), get_height(root.right)) + 1


def get_balance_factor(root):
    if root is None:
        return 0
    return get_height(root.left) - get_height(root.right)

1. 实现旋转操作

旋转操作可以分为左旋和右旋两种，它们可以帮助我们调整平衡二叉树，使得节点的平衡因子恢复为-1、0或1。

def left_rotate(root):
    right_node = root.right
    root.right = right_node.left
    right_node.left = root
    return right_node


def right_rotate(root):
    left_node = root.left
    root.left = left_node.right
    left_node.right = root
    return left_node

1. 插入节点

对于一个没有任何节点的空树，我们将插入第一个节点作为根节点，否则我们需要通过递归查找合适的插入位置。

插入节点之后，我们需要检查是否需要通过旋转操作来调整平衡。

def insert_node(root, value):
    if root is None:
        root = TreeNode(value)
    elif root.value > value:
        root.left = insert_node(root.left, value)
    elif root.value < value:
        root.right = insert_node(root.right, value)
    # 更新平衡因子
    balance_factor = get_balance_factor(root)
    # LL
    if balance_factor > 1 and value < root.left.value:
        return right_rotate(root)
    # RR
    elif balance_factor < -1 and value > root.right.value:
        return left_rotate(root)
    # LR
    elif balance_factor > 1 and value > root.left.value:
        root.left = left_rotate(root.left)
        return right_rotate(root)
    # RL
    elif balance_factor < -1 and value < root.right.value:
        root.right = right_rotate(root.right)
        return left_rotate(root)
    return root

示例

现在让我们通过一个示例来理解平衡二叉树的使用。

我们现在有一组数据[5, 6, 2, 8, 3, 1, 4]，我们可以通过以下代码将它们插入平衡二叉树中并进行中序遍历来验证插入操作是否正确。

if __name__ == '__main__':
    nums = [5, 6, 2, 8, 3, 1, 4]
    root = None
    for num in nums:
        root = insert_node(root, num)
    res = inorder_traverse(root, [])
    print(res)   # [1, 2, 3, 4, 5, 6, 8]
    root = delete_node(root, 5)
    res = inorder_traverse(root, [])
    print(res)   # [1, 2, 3, 4, 6, 8]

注意我们通过AVL Tree保证了二叉树的高度平衡，因此对于同样的数据，我们可以得到不同的高度，这可以节省查找操作的时间复杂度。

以上是二叉排序树与平衡二叉树的Python实现攻略，希望对你有所帮助。