summaryrefslogtreecommitdiff
path: root/src/03/06/README.md
diff options
context:
space:
mode:
authormo khan <mo.khan@gmail.com>2020-09-26 19:44:29 -0600
committermo khan <mo.khan@gmail.com>2020-09-26 19:44:29 -0600
commit5cb4ce51804e8bc60fef6f3e33ceaee0f05bacc6 (patch)
tree58a88d84a8d826ae89a23d95d74404a1741bd3ba /src/03/06/README.md
parentc93020800e852b17f4cf30fb867bccac88d61cbd (diff)
Collapse all questions into a single README
Diffstat (limited to 'src/03/06/README.md')
-rw-r--r--src/03/06/README.md48
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)