Ağaçlar ve Arama Ağaçları (Trees & Search Trees) Algoritması

1class RBTNode {
2  val: number;
3  color: 'RED' | 'BLACK';
4  left: RBTNode | null = null;
5  right: RBTNode | null = null;
6  constructor(val: number) {
7    this.val = val;
8    this.color = 'RED';
9  }
10}
11
12class RedBlackTree {
13  root: RBTNode | null = null;
14
15  insert(val: number, trace: string[]) {
16    trace.push(`${val} ağaca ekleniyor.`);
17    this.root = this.insertRec(this.root, val, trace);
18    this.root.color = 'BLACK'; // Kök her zaman siyahtır
19  }
20
21  private insertRec(node: RBTNode | null, val: number, trace: string[]): RBTNode {
22    if (node === null) return new RBTNode(val);
23
24    if (val < node.val) {
25      node.left = this.insertRec(node.left, val, trace);
26    } else if (val > node.val) {
27      node.right = this.insertRec(node.right, val, trace);
28    }
29
30    // Dengelenme kuralları simülasyonu
31    if (this.isRed(node.right) && !this.isRed(node.left)) {
32      trace.push(`Sola rotasyon yapılıyor: Node ${node.val}`);
33      node = this.rotateLeft(node);
34    }
35    if (this.isRed(node.left) && this.isRed(node.left?.left)) {
36      trace.push(`Sağa rotasyon yapılıyor: Node ${node.val}`);
37      node = this.rotateRight(node);
38    }
39    if (this.isRed(node.left) && this.isRed(node.right)) {
40      trace.push(`Renk değişimi yapılıyor: Node ${node.val}`);
41      this.flipColors(node);
42    }
43
44    return node;
45  }
46
47  private isRed(node: RBTNode | null): boolean {
48    return node !== null && node.color === 'RED';
49  }
50
51  private rotateLeft(h: RBTNode): RBTNode {
52    const x = h.right!;
53    h.right = x.left;
54    x.left = h;
55    x.color = h.color;
56    h.color = 'RED';
57    return x;
58  }
59
60  private rotateRight(h: RBTNode): RBTNode {
61    const x = h.left!;
62    h.left = x.right;
63    x.right = h;
64    x.color = h.color;
65    h.color = 'RED';
66    return x;
67  }
68
69  private flipColors(h: RBTNode) {
70    h.color = 'RED';
71    if (h.left) h.left.color = 'BLACK';
72    if (h.right) h.right.color = 'BLACK';
73  }
74}