Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct Link(N) {
- private:
- N* child;
- public:
- this(N* n, Color c) {
- child = cast(N*) ((cast(size_t) n) | c);
- }
- auto getAs(Color c) {
- return Link(node(), c);
- }
- N* node() const {
- return cast(N*) ((cast(size_t) child) & ~0x01);
- }
- Color color() const {
- return cast(Color) ((cast(size_t) child) & 0x01);
- }
- bool isRed() const {
- return color() == Color.Red;
- }
- bool isBlack() const {
- return color() == Color.Black;
- }
- private:
- // Rotate the tree and return the new root.
- auto rotateLeft() {
- auto right = node().right;
- node().right = right.node().left;
- right.node().left = node();
- return right;
- }
- // Rotate the tree and return the new root.
- auto rotateRight() {
- auto left = node().left;
- node().left = left.node().right;
- left.node().right = node();
- return left;
- }
- }
- enum Color {
- Black = false,
- Red = true,
- }
- // Insert a new node in the tree.
- auto rb_insert(N)(N* root, N* n) {
- // rbtree's depth is ln(n) which is at most 8 * size_t.sizeof.
- // But a branch can be at most 2* longer than the shortest one.
- Path!N[16 * size_t.sizeof] path; // TODO: make this void initialized.
- auto stackp = &path[0]; // TODO: use .ptr when available.
- // Root is always black.
- stackp.link = Link!N(root, Color.Black);
- while (stackp.node !is null) {
- auto cmp = stackp.cmp = n.opCmp(stackp.node);
- assert(cmp != 0);
- auto link = stackp.link;
- stackp++;
- stackp.link = (cmp < 0)
- ? stackp.link.node().left
- : stackp.link.node().right;
- }
- // Inserted node is always red.
- stackp.link = Link!N(n, Color.Red);
- // Now we found an insertion point, let's fix the tree.
- for (stackp--; stackp !is &path[-1]; stackp--) {
- auto link = stackp.link;
- if (stackp.cmp < 0) {
- auto left = link.node().left = stackp[1].link;
- if (left.isBack()) {
- return;
- }
- auto leftleft = left.node().left;
- if (leftleft.isBlack()) {
- continue;
- }
- /**
- * l = left
- * b = changed to black
- *
- * NB: Because of the handling of the right branch,
- * it is impossible to have 2 red node on the right.
- *
- * B
- * / Rl
- * Rl => / \
- * / Rb B
- * R
- */
- left.get().left = leftleft.getAs(Color.Black);
- stackp.link = link.rotateRight();
- } else {
- auto right = link.node().right = stackp[1].link;
- if (right.isBlack()) {
- return;
- }
- auto left = link.node().left;
- if (left.isRed()) {
- /**
- * r = right
- * b = changed to black
- * r = changed to red
- *
- * NB: Because left is red, we know link is black.
- * NB: We can't have 2 red nodes on the right.
- *
- * B Br
- * / \ / \
- * R R => Rb Rb
- * / \ / \
- * R B R B
- */
- link.node().left = left.getAs(Color.Back);
- link.node().right = right.getAs(Color.Back);
- stackp.link = link.getAs(Color.Red);
- continue;
- }
- /**
- * R
- * This ensure that \ is impossible.
- * R
- *
- * l = left
- * b = changed to black
- * r = changed to red
- *
- * If we have 2 red node on the right at link level
- * we rebalance to have them on the left and push
- * the problem one level up.
- *
- * R
- * R /
- * / \ => R
- * B R /
- * B
- *
- * Or we have 2 red on the left, in which case
- * the link must be black.
- *
- * B Rb
- * / \ / \
- * B R => Br B
- * / \ / \
- * R B B R
- *
- * And it is all screwed up :( What is wrong here ?
- */
- auto l = link.rotateLeft().getAs(link.color());
- l.node().left = link.getAs(Color.Red);
- stackp.link = l;
- }
- }
- return stackp.link.node();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement