转载

图解红黑树

红黑树

红黑树是一种二叉搜索树,可以保证树得查找、插入、删除得时间复杂都为O(lgn)

红黑树有重要得三个性质:

1、根结点的颜色为黑色

2、父、子结点不能同时为红色

3、对每个结点,从该结点出发到其后代的叶结点路径,均包含相同数目的黑色结点

树的旋转

首先定义旋转,后面的插入和删除操作都需要用到旋转操作,旋转分为左旋和右旋

如图所示,左边图右旋x结点,可以得到右图。右图左旋y结点可以得到左图

红黑树的插入操作

红黑树的插入操作相对于删除操作较为简单,创建一个新结点 z z ,进行相应赋值,并将其染成红色。

首先通过搜索找到插入的位置。分为两种情况

  • 新插入的结点 z z 为根结点 (解决方法:将根结点染黑即可)

    新插入的结点 z z 的父结点为黑色 (不用任何操作)

  • 新插入的结点 z z 的父结点为红色(违反前面所述性质2)

    可以分为三种情况对红黑树进行修复

    • 叔结点为红色

      将父结点和叔结点染黑,父结点染红,之后对祖父结点进行相同的递归操作

    • 叔结点为黑色,新插入的结点 z z 是父结点的右结点

      对结点 z z 进行左旋操作,转为情况三

    • 叔结点为黑色,新插入的结点 z z 是父结点的左结点

      父节点右旋,之后与祖父节点颜色互换。

红黑树的删除操作

红黑树的删除操作较为复杂。删除的节点分为几种情况

  • 删除节点是叶节点直接删除就好

  • 删除的节点只有一个子节点,删除节点,并且由子节点占据删除节点位置

  • 删除的节点既有左节点、又有右节点,找到节点中序遍历的直接后缀或直接前缀

    z是需要删除的节点,y是其直接前缀,x是y的左节点

    删除z节点,y节点替换z节点,x替换y节点

  • 删除节点如果是黑色,必须在其原位置添加一层黑色,如果原来节点是红色,简单得去除一层黑色,就可以解决,如果原来节点是黑色,成为双黑色,需要去除多余的黑色

    去除多余得黑色,可以分为四种情况

    • 叔节点为红色

      叔节点左旋,并且颜色与父节点互换,转为情况2、3、4

    • 叔节点为黑色,并且两个子节点均为黑色

      这种情况最简单,将叔节点染成红色,去除原来节点多余的黑色即可,对父节点添加一层黑色,

      进行相应的递归操作

    • 叔节点为黑色,左节点为红色,右节点为黑色

      叔的左节点右旋,之后与叔节点颜色互换,转为情况4

    • 叔节点为黑色,左节点黑色,右节点红色

正文到此结束
本文目录