重念一次早該補起來的「資料結構與演算法」。這篇筆記下 紅黑樹 Red-Black Tree 的旋轉邏輯。
課程相關資訊
[連結]：https://hiskio.com/en/courses/572/lectures/146364
本篇範圍：Chapter 14
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
class TreeNode<T> { value: T; left: TreeNode<T> | null = null; right: TreeNode<T> | null = null; parent: TreeNode<T> | null = null; color: 'red' | 'black' = 'red'; constructor(value: T) { this.value = value; } } class RedBlackTree<T> { root: TreeNode<T> | null = null; // 左旋轉 private leftRotate(x: TreeNode<T>) { const y = x.right!; x.right = y.left; if (y.left) y.left.parent = x; y.parent = x.parent; if (!x.parent) { this.root = y; } else if (x === x.parent.left) { x.parent.left = y; } else { x.parent.right = y; } y.left = x; x.parent = y; } // 右旋轉 private rightRotate(y: TreeNode<T>) { const x = y.left!; y.left = x.right; if (x.right) x.right.parent = y; x.parent = y.parent; if (!y.parent) { this.root = x; } else if (y === y.parent.left) { y.parent.left = x; } else { y.parent.right = x; } x.right = y; y.parent = x; } // 插入新節點 insert(value: T) { const newNode = new TreeNode(value); if (!this.root) { this.root = newNode; this.root.color = 'black'; } else { let current = this.root; let parent: TreeNode<T> | null = null; while (current) { parent = current; if (value < current.value) { current = current.left; } else { current = current.right; } } newNode.parent = parent; if (value < parent!.value) { parent!.left = newNode; } else { parent!.right = newNode; } this.fixInsert(newNode); } } // 插入修復方法 private fixInsert(node: TreeNode<T>) { while (node.parent && node.parent.color === 'red') { if (node.parent === node.parent.parent!.left) { const uncle = node.parent.parent!.right; if (uncle && uncle.color === 'red') { node.parent.color = 'black'; uncle.color = 'black'; node.parent.parent!.color = 'red'; node = node.parent.parent!; } else { if (node === node.parent.right) { node = node.parent; this.leftRotate(node); } node.parent!.color = 'black'; node.parent!.parent!.color = 'red'; this.rightRotate(node.parent!.parent!); } } else { const uncle = node.parent.parent!.left; if (uncle && uncle.color === 'red') { node.parent.color = 'black'; uncle.color = 'black'; node.parent.parent!.color = 'red'; node = node.parent.parent!; } else { if (node === node.parent.left) { node = node.parent; this.rightRotate(node); } node.parent!.color = 'black'; node.parent!.parent!.color = 'red'; this.leftRotate(node.parent!.parent!); } } } this.root!.color = 'black'; } printTree(node: TreeNode<T> | null = this.root, indent: string = '', last: boolean = true) { if (node !== null) { console.log(indent + (last ? '└─ ' : '├─ ') + (node.color === 'red' ? 'R' : 'B') + node.value); indent += last ? ' ' : '| '; this.printTree(node.left, indent, false); this.printTree(node.right, indent, true); } } } // 測試紅黑樹的插入 const rbt = new RedBlackTree<number>(); // 插入節點 rbt.insert(10); rbt.insert(20); rbt.insert(30); rbt.insert(15); rbt.insert(25); // 輸出結果 rbt.printTree(); |
系列文章
[blogimove-CPC-TAG=theIdeaOfAlgorithm-MODE=1-POSTNUM=-ORDERBY=title-ORDERTYPE=desc]
按讚加入粉絲團
