先记录下TreeMap源代码删除后的调整方法(删除方法请百度AVLTree的删除):
下面是删除调整方法:
private void fixAfterDeletion(Entry<K,V> x) { while (x != root && colorOf(x) == BLACK) {//如果当前节点不为根节点并且当前节点的颜色为黑色 if (x == leftOf(parentOf(x))) {//如果当前节点为父节点的左孩子 Entry<K,V> sib = rightOf(parentOf(x));//获取父节点的右孩子 if (colorOf(sib) == RED) {//如果右孩子为红色 setColor(sib, BLACK);//设置右孩子为黑色 setColor(parentOf(x), RED);//设置父节点为红色 rotateLeft(parentOf(x));//左转 sib = rightOf(parentOf(x));//把右孩子变成父级节点的右孩子(这个时候父级节点是之前x的祖父节点) } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {//如果右孩子的左节点和右节点都是黑色 setColor(sib, RED);//设置右孩子为红色 x = parentOf(x);//把当前节点引用指向其父节点 } else {//否则 if (colorOf(rightOf(sib)) == BLACK) {//如果右孩子的右节点为黑色(其右孩子的左节点为红色) setColor(leftOf(sib), BLACK);//设置右孩子的左节点为黑色 setColor(sib, RED);//设置右孩子为红色 rotateRight(sib);//根据右孩子进行右转 sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x)));//设置右孩子颜色为父级节点同色 setColor(parentOf(x), BLACK);//设置父级节点为黑色 setColor(rightOf(sib), BLACK);//设置右孩子的右节点为黑色 rotateLeft(parentOf(x));//左转 x = root; } } else { // symmetric//如果当前节点为父节点的右孩子 Entry<K,V> sib = leftOf(parentOf(x));//获取当前节点父节点的左孩子 if (colorOf(sib) == RED) {//如果左孩子颜色为红色 setColor(sib, BLACK);//设置左孩子为黑色 setColor(parentOf(x), RED);//设置父节点为红色 rotateRight(parentOf(x));//右转 sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {//如果右孩子的左节点和右节点都是黑色 setColor(sib, RED);//设置左孩子为红色 x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) {//如果左孩子的左节点为黑色(其右孩子的左节点为红色) setColor(rightOf(sib), BLACK);//设置左孩子的右节点为黑色 setColor(sib, RED);//设置左孩子为红色 rotateLeft(sib);//左转 sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x)));//设置左孩子颜色为父级节点同色 setColor(parentOf(x), BLACK);//设置父节点为黑色 setColor(leftOf(sib), BLACK);//设置左孩子的左节点为黑色 rotateRight(parentOf(x));//右转 x = root; } } } setColor(x, BLACK); }
删除有点复杂,自己搞的不是太懂,只知道大概有四种情况:
第一种情况:
当兄弟节点为右节点且为红色:把右兄弟节点设置为黑色,父节点设置成红色,对父节点进行左转
第二种情况:
当右兄弟节点的子节点都为黑色,则把右兄弟节点设置成红色,当前节点引用指向父节点
第三种情况:
当兄弟节点的左子节点为红色,把左子节点设置成黑色,兄弟节点设置成红色,对兄弟节点进行右转
第四种情况:
当兄弟节点的右节点为红色,把兄弟节点颜色设置成父节点颜色同色,兄弟节点的右节点设置成黑色,父节点设置成黑色,对父节点进行左转
自己学的也不是太清晰,只能靠源码去分情况。继续学习吧~,如果有人看到此文章,感觉那里错误,请留言,非常感谢