資料結構

1class RBNode {
2  left: RBNode | null = null;
3  right: RBNode | null = null;
4  parent: RBNode | null = null;
5  red = true;                                          // new nodes start red
6  constructor(public key: number) {}
7}
8 
9class RedBlackTree {
10  root: RBNode | null = null;
11 
12  insert(key: number): void {
13    let parent: RBNode | null = null;
14    let node = this.root;
15    while (node) {
16      if (key === node.key) return;
17      parent = node;
18      node = key < node.key ? node.left : node.right;
19    }
20    const z = new RBNode(key);
21    z.parent = parent;
22    if (!parent) this.root = z;
23    else if (key < parent.key) parent.left = z;
24    else parent.right = z;
25    this.fixAfterInsert(z);
26  }
27 
28  private fixAfterInsert(z: RBNode): void {
29    while (z.parent && z.parent.red) {
30      const p = z.parent;
31      const g = p.parent!;
32      const uncle = p === g.left ? g.right : g.left;
33      if (uncle && uncle.red) {
34        p.red = false;
35        uncle.red = false;
36        g.red = true;
37        z = g;
38      } else if (p === g.left) {
39        if (z === p.right) { z = p; this.rotateLeft(z); }
40        z.parent!.red = false;
41        g.red = true;
42        this.rotateRight(g);
43      } else {
44        if (z === p.left) { z = p; this.rotateRight(z); }
45        z.parent!.red = false;
46        g.red = true;
47        this.rotateLeft(g);
48      }
49    }
50    this.root!.red = false;
51  }
52 
53  private rotateLeft(x: RBNode): void {
54    const y = x.right!;
55    x.right = y.left;
56    if (y.left) y.left.parent = x;
57    this.replace(x, y);
58    y.left = x;
59    x.parent = y;
60  }
61 
62  private rotateRight(y: RBNode): void {
63    const x = y.left!;
64    y.left = x.right;
65    if (x.right) x.right.parent = y;
66    this.replace(y, x);
67    x.right = y;
68    y.parent = x;
69  }
70 
71  // Puts `next` where `old` hung from its parent.
72  private replace(old: RBNode, next: RBNode): void {
73    next.parent = old.parent;
74    if (!old.parent) this.root = next;
75    else if (old === old.parent.left) old.parent.left = next;
76    else old.parent.right = next;
77  }
78}