红黑树实现其实非常简单,不需要考虑图形,只从逻辑上分析即可直接写代码
红黑树规范
1. 根为黑色 通过根的变色,可以实现整体黑色的增减
2. 每条路径黑色数量相等
3. 红色不相邻 结合2点,最长路径不超两倍,保证基本分布平均
实现:编写节点替换父亲的函数 编写红平衡函数 编写黑平衡函数 具体实现:
节点替父函数:总是交换颜色!!!
1.替父的节点,如为红子,黑高不变,红可任意替父,如果为黑子,兄弟树增加一黑,本通道Far子树(离父更远),减少一黑,如果Far子为红,改黑后,黑不变,用于兄弟黑子删除
2. 红黑分析:会影响三条线:兄弟树 Near树(离父近,会交给父) Far树
3. 兄弟树路径:原为父,现在为父+this,增加this颜色
4. Near子树路径:原为this+父,现在仍为this+父,总不变
5. Far子树路径:原为this+父,现为this,少父色,与父交换后,少this色
6. 由上可知,如this为红,黑高不变,如this为黑,兄弟增加一黑,如果Far子为红,变黑后不变
增加节点:
1. 增加节点为红,按其键值找到父节点
2. 父节点为空,设为根,变黑
3. 不为根,则添加为父,进行红平衡处理
红平衡递归函数:
1. 递归出口:父节点为黑,满足红黑要求
2. 继续递归:叔叔为红,则将父与叔叔变黑,此时将祖节点变红,祖通道黑不变,如祖不为根则改红后继续递归,如为根,则整体黑高增加一个
3. 递归出口:父节点为红,祖必为黑,不在祖及父中间,父替祖,红色转给祖,父代祖位,红色已不相连,满足要求
4. 父节点为红,键值如果在祖及父中间,如果由父替,父与祖换色后,仍会红红相连,此时用this替父再替祖,满足要求
删除节点
1. 删除时,先找替代,其替代为其投影最靠近的点,用其取代,可保证不影响树形,右子的最左,或左子的最右,任选一个即可,以下选右边最近的点
2. 替代可能有右子,必为红,将右子进位,将红传给替代,后续可直接删除
3. 替代可能为自身,此时可能有左子,必为红,将此子进位,自身变红
4. 删除时,如替代为红,直接删除,否则黑平衡处理
黑平衡函数 需要本通道增加一黑,兄弟通道黑不变
1. 递归出口:为根 整体黑高减少一个
2. 递归出口:不为根必有兄弟,如近侄为红,将其替兄替父,变黑即高满足要求
3. 递归出口:远侄为红,兄替父,红变黑,满足要求
4. 递归出口:如父为红,兄弟必为黑,将父兄换色(兄弟已确认无红子,可变红),兄弟树先兄后父变先父后兄,黑不变,this通道增加一黑,满足要求
5. 如兄弟为红,用兄弟替父,再递归检查,等于检查兄弟过来的子树,总有出口
6. 全黑,将兄弟变红,父通道整体需要增加一黑,用父递归
将替代断开连接,并替换删除目标,复制其颜色即可
分析及源码https://github.com/ZhangGuibin133/RedBlackTree
具体实现:节点替父函数
//子升级为父,总是交换颜色,如子为红子,红黑不变化,即红子可任意换位,不影响红黑规则
// 如子为黑子,本树多一黑,子的Far子树少一黑,如Far子树可置黑,子的原子树黑不变
// 返回自身,用于链式调用
inline fun replaceFather(): Node {
val oldFather =father!!
swapColor(oldFather)//先互换颜色
//移交父级关系,如为父的左子仍为其左子,否则仍为其右子
father = oldFather.father?.also { if (it.left == oldFather)it.left =this else it.right =this }
oldFather.father =this
//处理儿子及相互关系,如原为父左子,用右子代位,用父代右子位,否则用左子代位,用父代左子
if (this == oldFather.left) {
oldFather.left =right?.also { it.father = oldFather}
right = oldFather
}else {
oldFather.right =left?.also { it.father = oldFather}
left = oldFather
}
return this
}
//只有红色节点才进行检查,根不会参与此递归,必有父
private fun Node.redBalance() {
when {
//递归出口:父为黑,满足要求,以下递归,父即为红,必有祖
father!!.isBlack ->return
//uncle与父同为红色,同改黑色,如祖为根则黑色增加一层,否则将祖改色递归
uncle()?.isRedSetBlack() ==true -> {
father!!.isBlack =true
grandFather()!!.let {
if (it !=root)it.apply { isBlack =false }.redBalance()
}
}
//递归出口 Uncle为黑色或无,如不在祖与父中间,一次代替,否则两次代替
this ==father!!.farSon() ->father!!.replaceFather().checkRoot()
this ==father!!.nearSon() -> replaceFather().replaceFather().checkRoot()
}
}
//需要本通道减少一个黑色 另一边黑色不变
private fun Node.blackBalance() {
when {
//递归出口,为根节点,黑色减少了一层
father ==null ->return
//递归出口,兄弟有红子,变黑,替父,此时本通道多一黑,原兄弟通道黑不变
brother()!!.farSon()?.isRedSetBlack() ==true -> brother()!!.replaceFather().checkRoot()
//递归出口:如果兄弟靠近父亲的子节点为红色,先子代兄,再代父
brother()!!.nearSon()?.isRedSetBlack() ==true ->
brother()!!.nearSon()!!.replaceFather().replaceFather().checkRoot()
//递归出口:父节点为红,置黑,本通道多一黑,兄弟通道可改红(侄全为黑),保持黑不变
father!!.isRedSetBlack() -> brother()!!.isBlack =false
//兄弟为红,将其与父交换顶点,变黑色,父为红色,再行递归处理,后续相当于处理兄弟的子树,总有出口
brother()?.isRed() ==true ->run { brother()!!.replaceFather().checkRoot(); blackBalance()}
//全黑,无法内部处理,将兄弟变红,整体减少一个黑色,任务交给上级
else ->run { brother()!!.isBlack =false; father!!.blackBalance()}
}
}
