红黑树一种重要的平衡二叉搜索树实现方法.pptx

红黑树

一种重要的平衡二叉搜索树实现方法;平衡二叉搜索树;平衡二叉树的本质含义：;左/右旋转的同时保持二叉搜索性质;;;这个问题有多严重呢？;所以，问题的焦点在于以下结构;所以，问题的焦点在于以下结构;;实际上我们可以这样归结问题：;红黑树是一种什么样的实现方式？;就插入而言：;;下一个情形;我们能否找到所有的冲突情形呢？;这个格局可以被抽象为A格局;我们能否找到所有的冲突情形呢？;这个格局可以被抽象为B格局;当我们设计插入的值出现在左边时，

同样能总结出以下两个格局;总共会形成以下4个格局：;万象归一;再看红黑树;繁琐的删除;;反之：;特别注意x，y，z三个变量;红黑树中的删除;看看简单情况;麻烦在哪里？;如何处理？;双重颜色的修复：1)额外的黑上移，直至遇到红节点;2)通过左移将额外的黑分配给父节点;