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