http://example.org/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Recent content in 数据结构 on FulurHugozh-CNTue, 29 Apr 2025 19:52:52 +0800http://example.org/posts/data_structure/red-black-trees/Tue, 29 Apr 2025 19:52:52 +0800http://example.org/posts/data_structure/red-black-trees/<h2 id="一红黑树核心性质"><strong>一、红黑树核心性质</strong></h2> <p>红黑树是一种<strong>自平衡二叉查找树</strong>，通过以下规则确保平衡性：</p> <ol> <li><strong>颜色规则</strong>：每个节点非红即黑。</li> <li><strong>根节点规则</strong>：根节点必为黑色。</li> <li><strong>叶子节点规则</strong>：所有叶子节点（NIL节点）均为黑色。</li> <li><strong>红色节点规则</strong>：红色节点的子节点必须为黑色（不允许连续红色节点）。</li> <li><strong>黑高规则</strong>：从任一节点到其所有叶子节点的路径中，黑色节点数量相同（黑高一致）。</li> </ol> <hr> <h2 id="二插入操作详解"><strong>二、插入操作详解</strong></h2> <p>红黑树的插入分两步：<strong>标准BST插入</strong> + <strong>平衡修复</strong>。</p>