红黑树

红黑树原理讲解

性质1: 每个节点要么是 黑色 ,要么是 红色 。 性质2: 根节点是 黑色 。 性质3: 每个叶子节点(NIL)是黑色。 性质4: 每个 红色 节点的两个子节点一定都是 黑色 。 性质5: 任意一个节点到每个叶子节点的路径都包含 数量相同 的 黑节点 。俗称: 黑高 ! 从性质5又可以推出: 性质5.1: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。 插入操作包括两部分工作: 注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。 最简单的一种情景,直接把插入结点作为根结点就行 注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。 处理: 更新当前结点的值,为插入结点的值 由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。 再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为 红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。 依据红黑树 性质4可知,红色结点不能相连===>祖父结点肯定为黑结点 因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红 处理: 1.将P和U结点改为黑色 2.将PP改为红色 3.将PP设置为当前结点,进行后序处理 注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。 处理: 处理: 该情景对应情景4.2,只是方向反转,直接看图 处理: 处理:

什么是红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。树的旋转当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。为了保持红黑树的性质，我们可以对相关结点做一系列的调整，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质（五点性质）。