标签
红黑树：平衡二叉树的一种，简单理解它的规则
2025-12-20 111 阅读 数据结构 红黑树 平衡二叉树 数据结构 自平衡树 Java TreeMap

红黑树是自平衡二叉搜索树，通过颜色标记和5条规则保证平衡，使插入、删除、查找复杂度稳定在O(log n)。核心规则包括：节点非红即黑；根为黑色；空叶子（NIL）为黑色；红节点子节点必为黑色（避免连续红节点）；任一节点到后代NIL路径的黑节点数（黑高）一致。规则4阻止连续红节点，规则5确保黑高相等，共同限制树高在O(log n)。插入新节点为红色，若父红需调整（变色或旋转）。广泛应用于Java TreeMap、Redis有序集合等，以平衡结构实现高效有序操作。

阅读全文
平衡二叉树：为什么需要平衡？旋转操作简单讲
2025-12-20 108 阅读 数据结构 平衡二叉树 AVL树 旋转操作 平衡因子 数据结构

二叉搜索树（BST）因极端插入可能退化为链表，操作复杂度升至O(n)。平衡二叉树通过**平衡因子**（节点左右子树高度差）控制平衡，要求平衡因子为-1、0或1。当不平衡时，通过**旋转操作**（LL右旋、RR左旋、LR先左旋后右旋、RL先右旋后左旋）调整结构，使树高保持log n级别，确保查找、插入、删除等操作复杂度稳定在O(log n)。旋转本质是调整支点，恢复树的平衡结构。

阅读全文