企业官网建设流程全解析

盐城市亭湖区城乡建设网站,做网站微信群,如何创建自己的邮箱,wordpress 商品 模板标签#xff1a; #数据结构 #算法 #红黑树 #Java集合 #面试必备 #可视化 #x1f480; 前言#xff1a;二叉搜索树 (BST) 的“死穴” 我们都知道二叉搜索树#xff08;BST#xff09;的特性#xff1a;左子树 根 右子树。 在理想情况下#xff0c;它的查找效…标签#数据结构 #算法 #红黑树 #Java集合 #面试必备 #可视化 前言二叉搜索树 (BST) 的“死穴”我们都知道二叉搜索树BST的特性左子树 根 右子树。在理想情况下它的查找效率是 。但在极端情况下例如插入 1, 2, 3, 4, 5它会退化成一条链表效率暴跌至 。BST 退化示意图 (Mermaid):退化 BST (链表)12345理想 BST (平衡)213为了解决这个问题我们需要自平衡。AVL 树追求极致平衡高度差不超过 1但维护成本太高。于是红黑树横空出世。 一、 降维打击红黑树的本质是 2-3 树如果你直接看红黑树的 5 条规则绝对会晕。但如果你先看2-3 树一切都豁然开朗。1. 什么是 2-3 树2-节点存 1 个值有 2 个孩子和普通二叉树一样。3-节点存 2 个值有 3 个孩子比如[3, 5]在一个节点里。2-3 树的核心特性绝对平衡。所有叶子节点都在同一层当插入数据导致节点“过胖”变成 4-节点时它会中间向上分裂保持高度平衡。2. 红黑树怎么来的红黑树其实就是用二叉树的形式来模拟 2-3 树。2-节点 黑色节点。3-节点一黑一红红节点通过红链接挂在黑节点旁边。映射关系图 (Mermaid):红黑树的表示Red_LinkBA右子树左子树中子树2-3 树的 3-节点左中右A , BWaitWaitWait秒懂结论红链接不仅仅是颜色它代表**“结合”。红节点和它的黑父节点其实在逻辑上是同一个大节点**3-节点。黑链接代表普通的父子关系。 二、 破解红黑树的 5 条天书规则理解了“红黑树 2-3 树”后我们再看规则简直就是废话规则为什么(2-3 树视角)1. 节点是红或黑因为要区分是 2-节点还是 3-节点。2. 根节点是黑色根节点如果红了说明它是别人的子3-节点的一部分但它是根没爸爸所以必须黑。3. 叶子(NIL)是黑色空节点默认为黑为了方便计算黑高。4. 不能有两个红节点相连核心因为 3-节点红黑是允许的但 4-节点红红黑在标准红黑树中需要分裂不允许保留。5. 任意路径黑节点数相同核心因为 2-3 树是绝对平衡的。红节点是“内部融合”的不贡献高度。去掉红节点大家高度当然一样️ 三、 三板斧左旋、右旋、变色当插入新节点默认为红色因为我们总想把新值融合进现有的节点凑成 3-节点时可能会破坏规则。我们需要三招来修复。1. 左旋 (Left Rotate)当右边出现红节点时因为我们规定红节点只能挂在左边或者为了平衡需要左旋。左旋后RedSEA左旋前RedESA2. 右旋 (Right Rotate)当左边出现连续两个红节点双红违规时需要右旋。3. 颜色翻转 (Color Flip)当一个节点的左右孩子都是红色时。这意味着它变成了一个临时 4-节点[红, 黑, 红]。在 2-3 树中4-节点需要分裂中间的提上去变红两边的独立变黑。颜色翻转示意图 (Mermaid):翻转后 (分裂)HLR翻转前 (临时4节点)RedRedHLR⚔️ 四、 实战演练插入推导假设我们要插入序列10, 20, 30。插入 10根节点直接变黑。10(黑)插入 20新节点为红比 10 大放右边。10(黑) ---红--- 20(红)违规右边有红链接修正左旋。变成20(黑) ---红--- 10(红)。插入 30新节点为红比 20 大放右边。20(黑) ---红--- 30(红)左边还有个 10(红)现在状态10(红) --- 20(黑) --- 30(红)。触发左右双红 -颜色翻转。10(黑),20(红),30(黑)。20是根必须变黑。最终20(黑)为根左右是10(黑)和30(黑)。完美平衡 总结红黑树并没有那么可怕它只是2-3 树的“二进制”影分身。所有的红色节点都只是在依附于父亲假装自己和父亲是一个大节点。所有的旋转和变色都只是为了模拟 2-3 树的分裂和生长。下次面试官再问你红黑树不要背口诀试着画出那个 2-3 树的对应关系告诉他“红黑树就是为了保证黑高平衡。”Next Step:打开 JDK 源码找到TreeMap.java搜索rotateLeft和fixAfterInsertion方法。对照着上面的图你会发现那些曾经像天书一样的代码现在竟然能读懂了