diff options
| author | mo khan <mo.khan@gmail.com> | 2020-09-26 19:44:29 -0600 |
|---|---|---|
| committer | mo khan <mo.khan@gmail.com> | 2020-09-26 19:44:29 -0600 |
| commit | 5cb4ce51804e8bc60fef6f3e33ceaee0f05bacc6 (patch) | |
| tree | 58a88d84a8d826ae89a23d95d74404a1741bd3ba /src/03/06/README.md | |
| parent | c93020800e852b17f4cf30fb867bccac88d61cbd (diff) | |
Collapse all questions into a single README
Diffstat (limited to 'src/03/06/README.md')
| -rw-r--r-- | src/03/06/README.md | 48 |
1 files changed, 0 insertions, 48 deletions
diff --git a/src/03/06/README.md b/src/03/06/README.md deleted file mode 100644 index 01a4dbe..0000000 --- a/src/03/06/README.md +++ /dev/null @@ -1,48 +0,0 @@ -Why does the method `remove(x)` in the `RedBlackTree` implementation -perform the assignment `u:parent = w:parent?` -Shouldn’t this already be done by the call to `splice(w)`? - -```java -boolean remove(T x) -{ - Node<T> u = findLast(x); - if (u == nil || compare(u.x, x) != 0) - return false; - Node<T> w = u.right; - if (w == nil) { - w = u; - u = w.left; - } else { - while (w.left != nil) - w = w.left; - u.x = w.x; - u = w.right; - } - splice(w); - u.colour += w.colour; - u.parent = w.parent; - removeFixup(u); - return true; -} - -void removeFixup(Node<T> u) { - while (u.colour > black) { - if (u == r) { - u.colour = black; - } else if (u.parent.left.colour == red) { - u = removeFixupCase1(u); - } else if (u == u.parent.left) { - u = removeFixupCase2(u); - } else { - u = removeFixupCase3(u); - } - } - if (u != r) { - Node<T> w = u.parent; - if (w.right.colour == red && w.left.colour == black) { - flipLeft(w); - } - } -} -``` -Source [Open Data Structures](https://www.aupress.ca/app/uploads/120226_99Z_Morin_2013-Open_Data_Structures.pdf) |
