diff options
| -rw-r--r-- | set/set.go | 4 | ||||
| -rw-r--r-- | set/tree.go | 45 |
2 files changed, 42 insertions, 7 deletions
@@ -3,8 +3,8 @@ package set import "fmt" var ( - NotFound = fmt.Errorf("Could not find entry") - NotImplemented = fmt.Errorf("Method not implemented") + NotFound = fmt.Errorf("could not find entry") + NotImplemented = fmt.Errorf("method not implemented") ) type Set interface { diff --git a/set/tree.go b/set/tree.go index 819f83c..3c83f78 100644 --- a/set/tree.go +++ b/set/tree.go @@ -65,18 +65,23 @@ func (t *Tree) Del(key int) (int, error) { return n.val, nil default: // I have two childs! + + // Right child has no left child + if n.right.left == nil { + val := n.val + n.right.left = n.left + *ptr = n.right + return val, nil + } + return 0, NotImplemented } } -func (t *Tree) min(ptr **node) (**node, *node, error) { - return nil, nil, NotImplemented -} - func (t *Tree) search(ptr **node, key int) (**node, *node, error) { n := *ptr if n == nil { - return ptr, nil, NotFound + return nil, nil, NotFound } switch { @@ -88,3 +93,33 @@ func (t *Tree) search(ptr **node, key int) (**node, *node, error) { return ptr, n, nil } } + +func (t *Tree) min(ptr **node, key int) (**node, *node, error) { + n := *ptr + if n == nil { + return nil, nil, NotFound + } + + for { + if n.left == nil { + return ptr, n, nil + } + ptr = &n.left + n = n.left + } +} + +func (t *Tree) max(ptr **node, key int) (**node, *node, error) { + n := *ptr + if n == nil { + return nil, nil, NotFound + } + + for { + if n.right == nil { + return ptr, n, nil + } + ptr = &n.right + n = n.right + } +} |