java红黑树伪代码实现红黑树实现map

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

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

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名注册、网络空间、营销软件、网站建设、鄂温克网站维护、网站推广。

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

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

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

不知道你所说的修改是什么意思，是修改卫星数据还是修改key值？

如果是修改卫星数据，那么不需要改动树结构；

如果是修改key值，那么愚以为，删除和插入两个操作相加是最好的办法，因为即使两者操作叠加，时间复杂度也不会超过log(n)

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

在linux操作系统内核实现里经常使用的红黑树如下：

二叉树，按中序遍历后为一递增数组，自平衡意味着树的高度有一个上限，对于红黑树，其为2log(n+1)，所以时间复杂度为最差为Olog(n)。

赋予二叉搜索树自平衡特性的方法有多种，红黑树通过一下4条约束实现自平衡:

Every node is either red or black.

All NIL nodes (figure 1) are considered black.

A red node does not have a red child.

Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

其中根节点为黑色。

红黑树的搜索与二叉搜索树无异，但是插入和删除可能会违背上述四条原则。需要用到左旋右旋操作。左旋右旋上图，可以看到左旋右旋本身不改变二叉搜索树的特性，旋转后必要时改变节点的颜色可消除插入或者删除带来的红冲突和黑冲突，有时红黑树的重新平衡需要迭代进行。

红黑树比较适合的应用场景:

需要动态插入、删除、查找的场景，包括但不限于：

某些数据库的增删改查，比如select * from xxx where 这类条件检索。

linux内核中进程通过红黑树组织管理，便于快速插入、删除、查找进程的task_struct。

linux内存中内存的管理：分配和回收。用红黑树组织已经分配的内存块，当应用程序调用free释放内存的时候，可以根据内存地址在红黑树中快速找到目标内存块。

hashmap中(key,value)增、删、改查的实现；java 8就采用了RBTree替代链表。

Ext3文件系统，通过红黑树组织目录项。

这篇文章讲的很明白了。

很疑惑，为什么大家碰到问题不先自己去百度呢？

本文名称：java红黑树伪代码实现红黑树实现map
文章地址：http://pwwzsj.com/article/dogisgd.html