Question

红黑树如何执行修改操作？

我查过很多红黑树介绍，都只说明了如何进行插入和删除操作，如果是进行修改操作呢？即更改树中一个节点的key值，该如何操作保持红黑树性质？
当然我也可以先删除那个修改点，再把修改点当成新点插入，这样的复杂度也是O(lgn），不过系数会比较大，我想了解有没有更好的办法。
我不是不理解红黑树，我也是参照《算法导论》写了个红黑树，比你写的还多一个区间查找功能……但问题是还没有看到相关资料讨论过自平衡树的修改操作（包括AVL树我也没见过），我自己想的结果是由于修改操作的最坏可能性，似乎“修改=删除+重新添加”是最可行的办法了。我想知道高手们是否对自平衡树的修改操作有更多想法。

Answer 1

红黑树解释起来比较麻烦，里面有一些树节点的旋转工作，我有编好的程序，也是搞了n多天才搞定的。你先看看（代码是C++的）。里面实现了其节点插入、删除、遍历、前驱、后继等接口。

程序太长，没法拷贝过来，到我的博客去看吧。

如果程序没法理解，请查看麻省理工的《算法导论》中文版关于二叉查找树和红黑树的章节，里面有详细介绍和很多伪代码，我的代码就是参考伪代码写出来的。

=============最新回复==============

不知道你所说的修改是什么意思，是修改卫星数据还是修改key值？
如果是修改卫星数据，那么不需要改动树结构；
如果是修改key值，那么愚以为，删除和插入两个操作相加是最好的办法，因为即使两者操作叠加，时间复杂度也不会超过log(n)

麻省理工的《算法导论》中文版卓越网上有热卖哦：-）