| 1 | "use strict";
|
|---|
| 2 |
|
|---|
| 3 | Object.defineProperty(exports, "__esModule", {
|
|---|
| 4 | value: true
|
|---|
| 5 | });
|
|---|
| 6 | exports.RedBlackNode = RedBlackNode;
|
|---|
| 7 | exports.default = void 0;
|
|---|
| 8 | function RedBlackTree() {
|
|---|
| 9 | this._ = null; // root node
|
|---|
| 10 | }
|
|---|
| 11 | function RedBlackNode(node) {
|
|---|
| 12 | node.U =
|
|---|
| 13 | // parent node
|
|---|
| 14 | node.C =
|
|---|
| 15 | // color - true for red, false for black
|
|---|
| 16 | node.L =
|
|---|
| 17 | // left node
|
|---|
| 18 | node.R =
|
|---|
| 19 | // right node
|
|---|
| 20 | node.P =
|
|---|
| 21 | // previous node
|
|---|
| 22 | node.N = null; // next node
|
|---|
| 23 | }
|
|---|
| 24 | RedBlackTree.prototype = {
|
|---|
| 25 | constructor: RedBlackTree,
|
|---|
| 26 | insert: function (after, node) {
|
|---|
| 27 | var parent, grandpa, uncle;
|
|---|
| 28 | if (after) {
|
|---|
| 29 | node.P = after;
|
|---|
| 30 | node.N = after.N;
|
|---|
| 31 | if (after.N) after.N.P = node;
|
|---|
| 32 | after.N = node;
|
|---|
| 33 | if (after.R) {
|
|---|
| 34 | after = after.R;
|
|---|
| 35 | while (after.L) after = after.L;
|
|---|
| 36 | after.L = node;
|
|---|
| 37 | } else {
|
|---|
| 38 | after.R = node;
|
|---|
| 39 | }
|
|---|
| 40 | parent = after;
|
|---|
| 41 | } else if (this._) {
|
|---|
| 42 | after = RedBlackFirst(this._);
|
|---|
| 43 | node.P = null;
|
|---|
| 44 | node.N = after;
|
|---|
| 45 | after.P = after.L = node;
|
|---|
| 46 | parent = after;
|
|---|
| 47 | } else {
|
|---|
| 48 | node.P = node.N = null;
|
|---|
| 49 | this._ = node;
|
|---|
| 50 | parent = null;
|
|---|
| 51 | }
|
|---|
| 52 | node.L = node.R = null;
|
|---|
| 53 | node.U = parent;
|
|---|
| 54 | node.C = true;
|
|---|
| 55 | after = node;
|
|---|
| 56 | while (parent && parent.C) {
|
|---|
| 57 | grandpa = parent.U;
|
|---|
| 58 | if (parent === grandpa.L) {
|
|---|
| 59 | uncle = grandpa.R;
|
|---|
| 60 | if (uncle && uncle.C) {
|
|---|
| 61 | parent.C = uncle.C = false;
|
|---|
| 62 | grandpa.C = true;
|
|---|
| 63 | after = grandpa;
|
|---|
| 64 | } else {
|
|---|
| 65 | if (after === parent.R) {
|
|---|
| 66 | RedBlackRotateLeft(this, parent);
|
|---|
| 67 | after = parent;
|
|---|
| 68 | parent = after.U;
|
|---|
| 69 | }
|
|---|
| 70 | parent.C = false;
|
|---|
| 71 | grandpa.C = true;
|
|---|
| 72 | RedBlackRotateRight(this, grandpa);
|
|---|
| 73 | }
|
|---|
| 74 | } else {
|
|---|
| 75 | uncle = grandpa.L;
|
|---|
| 76 | if (uncle && uncle.C) {
|
|---|
| 77 | parent.C = uncle.C = false;
|
|---|
| 78 | grandpa.C = true;
|
|---|
| 79 | after = grandpa;
|
|---|
| 80 | } else {
|
|---|
| 81 | if (after === parent.L) {
|
|---|
| 82 | RedBlackRotateRight(this, parent);
|
|---|
| 83 | after = parent;
|
|---|
| 84 | parent = after.U;
|
|---|
| 85 | }
|
|---|
| 86 | parent.C = false;
|
|---|
| 87 | grandpa.C = true;
|
|---|
| 88 | RedBlackRotateLeft(this, grandpa);
|
|---|
| 89 | }
|
|---|
| 90 | }
|
|---|
| 91 | parent = after.U;
|
|---|
| 92 | }
|
|---|
| 93 | this._.C = false;
|
|---|
| 94 | },
|
|---|
| 95 | remove: function (node) {
|
|---|
| 96 | if (node.N) node.N.P = node.P;
|
|---|
| 97 | if (node.P) node.P.N = node.N;
|
|---|
| 98 | node.N = node.P = null;
|
|---|
| 99 | var parent = node.U,
|
|---|
| 100 | sibling,
|
|---|
| 101 | left = node.L,
|
|---|
| 102 | right = node.R,
|
|---|
| 103 | next,
|
|---|
| 104 | red;
|
|---|
| 105 | if (!left) next = right;else if (!right) next = left;else next = RedBlackFirst(right);
|
|---|
| 106 | if (parent) {
|
|---|
| 107 | if (parent.L === node) parent.L = next;else parent.R = next;
|
|---|
| 108 | } else {
|
|---|
| 109 | this._ = next;
|
|---|
| 110 | }
|
|---|
| 111 | if (left && right) {
|
|---|
| 112 | red = next.C;
|
|---|
| 113 | next.C = node.C;
|
|---|
| 114 | next.L = left;
|
|---|
| 115 | left.U = next;
|
|---|
| 116 | if (next !== right) {
|
|---|
| 117 | parent = next.U;
|
|---|
| 118 | next.U = node.U;
|
|---|
| 119 | node = next.R;
|
|---|
| 120 | parent.L = node;
|
|---|
| 121 | next.R = right;
|
|---|
| 122 | right.U = next;
|
|---|
| 123 | } else {
|
|---|
| 124 | next.U = parent;
|
|---|
| 125 | parent = next;
|
|---|
| 126 | node = next.R;
|
|---|
| 127 | }
|
|---|
| 128 | } else {
|
|---|
| 129 | red = node.C;
|
|---|
| 130 | node = next;
|
|---|
| 131 | }
|
|---|
| 132 | if (node) node.U = parent;
|
|---|
| 133 | if (red) return;
|
|---|
| 134 | if (node && node.C) {
|
|---|
| 135 | node.C = false;
|
|---|
| 136 | return;
|
|---|
| 137 | }
|
|---|
| 138 | do {
|
|---|
| 139 | if (node === this._) break;
|
|---|
| 140 | if (node === parent.L) {
|
|---|
| 141 | sibling = parent.R;
|
|---|
| 142 | if (sibling.C) {
|
|---|
| 143 | sibling.C = false;
|
|---|
| 144 | parent.C = true;
|
|---|
| 145 | RedBlackRotateLeft(this, parent);
|
|---|
| 146 | sibling = parent.R;
|
|---|
| 147 | }
|
|---|
| 148 | if (sibling.L && sibling.L.C || sibling.R && sibling.R.C) {
|
|---|
| 149 | if (!sibling.R || !sibling.R.C) {
|
|---|
| 150 | sibling.L.C = false;
|
|---|
| 151 | sibling.C = true;
|
|---|
| 152 | RedBlackRotateRight(this, sibling);
|
|---|
| 153 | sibling = parent.R;
|
|---|
| 154 | }
|
|---|
| 155 | sibling.C = parent.C;
|
|---|
| 156 | parent.C = sibling.R.C = false;
|
|---|
| 157 | RedBlackRotateLeft(this, parent);
|
|---|
| 158 | node = this._;
|
|---|
| 159 | break;
|
|---|
| 160 | }
|
|---|
| 161 | } else {
|
|---|
| 162 | sibling = parent.L;
|
|---|
| 163 | if (sibling.C) {
|
|---|
| 164 | sibling.C = false;
|
|---|
| 165 | parent.C = true;
|
|---|
| 166 | RedBlackRotateRight(this, parent);
|
|---|
| 167 | sibling = parent.L;
|
|---|
| 168 | }
|
|---|
| 169 | if (sibling.L && sibling.L.C || sibling.R && sibling.R.C) {
|
|---|
| 170 | if (!sibling.L || !sibling.L.C) {
|
|---|
| 171 | sibling.R.C = false;
|
|---|
| 172 | sibling.C = true;
|
|---|
| 173 | RedBlackRotateLeft(this, sibling);
|
|---|
| 174 | sibling = parent.L;
|
|---|
| 175 | }
|
|---|
| 176 | sibling.C = parent.C;
|
|---|
| 177 | parent.C = sibling.L.C = false;
|
|---|
| 178 | RedBlackRotateRight(this, parent);
|
|---|
| 179 | node = this._;
|
|---|
| 180 | break;
|
|---|
| 181 | }
|
|---|
| 182 | }
|
|---|
| 183 | sibling.C = true;
|
|---|
| 184 | node = parent;
|
|---|
| 185 | parent = parent.U;
|
|---|
| 186 | } while (!node.C);
|
|---|
| 187 | if (node) node.C = false;
|
|---|
| 188 | }
|
|---|
| 189 | };
|
|---|
| 190 | function RedBlackRotateLeft(tree, node) {
|
|---|
| 191 | var p = node,
|
|---|
| 192 | q = node.R,
|
|---|
| 193 | parent = p.U;
|
|---|
| 194 | if (parent) {
|
|---|
| 195 | if (parent.L === p) parent.L = q;else parent.R = q;
|
|---|
| 196 | } else {
|
|---|
| 197 | tree._ = q;
|
|---|
| 198 | }
|
|---|
| 199 | q.U = parent;
|
|---|
| 200 | p.U = q;
|
|---|
| 201 | p.R = q.L;
|
|---|
| 202 | if (p.R) p.R.U = p;
|
|---|
| 203 | q.L = p;
|
|---|
| 204 | }
|
|---|
| 205 | function RedBlackRotateRight(tree, node) {
|
|---|
| 206 | var p = node,
|
|---|
| 207 | q = node.L,
|
|---|
| 208 | parent = p.U;
|
|---|
| 209 | if (parent) {
|
|---|
| 210 | if (parent.L === p) parent.L = q;else parent.R = q;
|
|---|
| 211 | } else {
|
|---|
| 212 | tree._ = q;
|
|---|
| 213 | }
|
|---|
| 214 | q.U = parent;
|
|---|
| 215 | p.U = q;
|
|---|
| 216 | p.L = q.R;
|
|---|
| 217 | if (p.L) p.L.U = p;
|
|---|
| 218 | q.R = p;
|
|---|
| 219 | }
|
|---|
| 220 | function RedBlackFirst(node) {
|
|---|
| 221 | while (node.L) node = node.L;
|
|---|
| 222 | return node;
|
|---|
| 223 | }
|
|---|
| 224 | var _default = exports.default = RedBlackTree; |
|---|
