public void put(K key,V value){
TreeNode<K, V> node = new TreeNode<>(key, value);
setRed(node);
//红黑树插入
TreeNode t = this.root,p=null;
if (t==null){
root = node;
setBlack(root);
return;
}else {//寻找插入位置
while(t!=null){
p=t;
if (node.compareTo(t)==0){//覆盖退出
t.setValue(node.getValue());
return;
}else if (node.compareTo(t)>0){
t = t.right;
}else {
t = t.left;
}
}
}
if (node.compareTo(p)>0){
p.right = node;
node.parent = p;
}else {
p.left = node;
node.parent = p;
}
//调整
TreeNode parent=null,pParent=null,uncle = null;
while ((parent = node.parent)!=null &&isRed(parent)){//父亲是红色,那必然有爷爷
pParent = parent.parent;
uncle = getUncle(node);
if (isRed(uncle)){
setRed(pParent);
setBlack(parent);
setBlack(uncle);
node = pParent;
}else if (isBlack(uncle)){
if (parent.isLeft()){
if (!node.isLeft()){
node = parent;
leftRotate(node);
}
setRed(pParent);
setBlack(parent);
rightRotate(pParent);
return;
}else {
if (node.isLeft()){
node = parent;
rightRotate(node);
}
setRed(pParent);
setBlack(parent);
leftRotate(pParent);
return;
}
}
}
if (parent==null){
setBlack(node);
}
}
![](https://profile-avatar.csdnimg.cn/edbf9ee20e644fe891188d7e129013f0_qq_40996105.jpg!4)
这个红黑树插入的速度比java的HashMap慢一倍,10000000数据要8秒,咋搞?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
悬赏问题
- ¥15 关于树的路径求解问题
- ¥15 yolo在训练时候出现File "D:\yolo\yolov5-7.0\train.py"line 638,in <module>
- ¥30 戴尔inspiron独显直连
- ¥15 进行一项代码设计遇到问题
- ¥15 Mutisim中关于74LS192N计数器芯片设计(计数器)
- ¥50 fastadmin后台无法删除文件
- ¥15 oracle查询Socket read timed out错误
- ¥15 matlab支持向量机使用错误
- ¥99 利用C/C++语言,使用TCP/IP协议,编一个简易聊天程序
- ¥15 如何使用python 实现对串口/dev/ttyUSB0进行上锁,使得该串口只能在一个python脚本中使用,其他脚本不能操作这个串口