头歌数据结构 二叉排序树和二叉平衡树

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它的每个节点都存储一个关键字，且每个节点的关键字都大于其左子树中所有节点的关键字，小于其右子树中所有节点的关键字。这样的二叉树具有很好的查找，插入和删除性能。

而二叉平衡树（Balanced Binary Tree）是一种特殊的二叉排序树，它的每个节点的左子树和右子树的高度差不超过1。这样的二叉树可以保证在最坏情况下，查找、插入和删除操作的时间复杂度都是O(log n)。

常见的二叉平衡树有AVL树、红黑树等。在实际应用中，二叉平衡树被广泛应用于数据库索引、路由表等需要高效查找、插入和删除的场景中。

相关问题

头歌二叉排序树和二叉平衡树

头歌二叉排序树和二叉平衡树都是常用的二叉树数据结构，但它们的特点和应用场景有所不同。

头歌二叉排序树（也称二叉搜索树）是一种特殊的二叉树，它满足左子树所有节点的值小于根节点的值，右子树所有节点的值大于根节点的值。这种特殊的结构使得头歌二叉排序树可以快速地进行查找、插入、删除等操作，时间复杂度为O(logn)。因此，它在实际应用中被广泛使用，如数据库索引、哈希表等。

二叉平衡树是在头歌二叉排序树的基础上进行改进的，它保证左右子树的高度差不超过1，从而避免了头歌二叉排序树在某些特殊情况下会退化成链表的问题，使得查找、插入、删除等操作的时间复杂度仍为O(logn)。因此，二叉平衡树被广泛应用于需要高效地维护有序数据的场景，如红黑树、AVL树等。

总之，头歌二叉排序树适用于静态数据的查找、插入、删除等操作，而二叉平衡树适用于动态数据的维护。

二叉排序树和二叉平衡树nefu数据结构课程设计

### 关于二叉排序树和二叉平衡树

#### 二叉排序树 (Binary Search Tree, BST)

二叉排序树是一种特殊的二叉树，其特性在于对于任意节点`n`而言：

- `n`的左子树中的所有节点的关键字均小于`n`的关键字；
- `n`的右子树中的所有节点的关键字均大于`n`的关键字。

这种性质使得二叉排序树非常适合用于快速查找、插入以及删除操作。当构建一棵接近完全二叉树形态的理想状态下的BST时，这些基本操作的时间复杂度可以达到O(log n)[^1]。

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


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

#### 二叉平衡树 (Balanced Binary Tree)

为了克服普通二叉排序树可能退化成链表的情况（最坏情况下时间复杂度会变为O(n)），引入了自调整机制来保持树的高度尽可能低，即所谓的“平衡”。常见的实现方式包括AVL树和红黑树等。这里以AVL为例说明如何维持树的平衡属性。

每当执行一次插入或删除之后都需要检查并维护当前节点及其祖先节点之间的高度差不超过1。如果违反此条件，则通过旋转操作重新排列部分子树结构从而恢复整个树的平衡性。

# AVL Node definition remains similar to above but with additional height attribute.
class AVLNode(TreeNode):  
    def __init__(self, key=None):
        super().__init__(key=key)
        self.height = 1
        
def get_height(node):
    if not node:
        return 0
    return node.height
    
def update_height(node):
    if node:
        node.height = max(get_height(node.left), get_height(node.right)) + 1

def rotate_left(z):
    y = z.right
    T2 = y.left
    
    # Perform rotation
    y.left = z
    z.right = T2
    
    # Update heights after rotations
    update_height(z)
    update_height(y)
    
    return y 

def rotate_right(z):
    y = z.left
    T3 = y.right
    
    # Perform rotation
    y.right = z
    z.left = T3
    
    # Update heights after rotations
    update_height(z)
    update_height(y)
    
    return y