1.红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色.并且有如下性质:
特性:从根到叶子结点最长的可能路径不多于最短的可能路径的两倍长.
1.左旋
2.右旋
3.插入(5种情况)
4.删除
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 | 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); // 情况1 setColor(parentOf(x), RED); // 情况1 rotateLeft(parentOf(x)); // 情况1 sib = rightOf(parentOf(x)); // 情况1 } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); // 情况2 x = parentOf(x); // 情况2 } else { if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); // 情况3 setColor(sib, RED); // 情况3 rotateRight(sib); // 情况3 sib = rightOf(parentOf(x)); // 情况3 } setColor(sib, colorOf(parentOf(x))); // 情况4 setColor(parentOf(x), BLACK); // 情况4 setColor(rightOf(sib), BLACK); // 情况4 rotateLeft(parentOf(x)); // 情况4 x = root; // 情况4 } } else { // 跟前四种情况对称 Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); // 情况5 setColor(parentOf(x), RED); // 情况5 rotateRight(parentOf(x)); // 情况5 sib = leftOf(parentOf(x)); // 情况5 } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); // 情况6 x = parentOf(x); // 情况6 } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); // 情况7 setColor(sib, RED); // 情况7 rotateLeft(sib); // 情况7 sib = leftOf(parentOf(x)); // 情况7 } setColor(sib, colorOf(parentOf(x))); // 情况8 setColor(parentOf(x), BLACK); // 情况8 setColor(leftOf(sib), BLACK); // 情况8 rotateRight(parentOf(x)); // 情况8 x = root; // 情况8 } } } setColor(x, BLACK);} |
---|
(具体插入和删除操作见 http://www.imooc.com/article/11715)