delete removes an element from the tree. It is an error to try deleting an element that does not exist. In order to remove an element properly, Delete needs to know the node’s parent node. Parent must not be nil.
(key int, parent *node)
| 294 | // element properly, Delete needs to know the node’s parent node. |
| 295 | // Parent must not be nil. |
| 296 | func (n *node) delete(key int, parent *node) error { |
| 297 | if n == nil { |
| 298 | return errors.New("value to be deleted does not exist in the tree") |
| 299 | } |
| 300 | |
| 301 | switch { |
| 302 | case key < n.data.Key: |
| 303 | return n.left.delete(key, n) |
| 304 | |
| 305 | case key > n.data.Key: |
| 306 | return n.right.delete(key, n) |
| 307 | |
| 308 | default: |
| 309 | switch { |
| 310 | case n.left == nil && n.right == nil: |
| 311 | n.replaceNode(parent, nil) |
| 312 | return nil |
| 313 | case n.left == nil: |
| 314 | n.replaceNode(parent, n.right) |
| 315 | return nil |
| 316 | case n.right == nil: |
| 317 | n.replaceNode(parent, n.left) |
| 318 | return nil |
| 319 | } |
| 320 | replacement, replParent := n.left.findMax(n) |
| 321 | n.data = replacement.data |
| 322 | return replacement.delete(replacement.data.Key, replParent) |
| 323 | } |
| 324 | } |
| 325 | |
| 326 | // preOrder traverses the node by traversing the child nodes recursively. |
| 327 | func (n *node) preOrder(f func(*node)) { |
no test coverage detected