Advanced Data Structures - Java Concepts - page 994

71
72 if (!found) return ;
73
74 // toBeRemoved contains obj
75
76 // If one of the children is empty, use the other
77
78 if (toBeRemoved.left == null ||
toBeRemoved.right == null )
79 {
80 Node newChild;
81 if (toBeRemoved.left == null )
82 newChild = toBeRemoved.right;
83 else
84 newChild = toBeRemoved.left;
85
86 if (parent == null ) // Found in root
87 root = newChild;
88 else if (parent.left == toBeRemoved)
89 parent.left = newChild;
90 else
91 parent.right = newChild;
92 return ;
93 }
94
95 // Neither subtree is empty
96
97 // Find smallest element of the right subtree
98
99 Node smallestParent = toBeRemoved;
100 Node smallest = toBeRemoved.right;
101 while (smallest.left != null )
102 {
103 smallestParent = smallest;
104 smallest = smallest.left;
105 }
106
107 // smallest contains smallest child in right subtree
108
109 // Move contents, unlink child
110