more on bst

3 files changed, 102 insertions, 40 deletions

diff --git a/set/set.go b/set/set.go
new file mode 100644
index 0000000..32174bc
--- /dev/null
+++ b/set/set.go
@@ -0,0 +1,15 @@
+package set
+
+import "fmt"
+
+var (
+	NotFound       = fmt.Errorf("Could not find entry")
+	NotImplemented = fmt.Errorf("Method not implemented")
+)
+
+type Set interface {
+	Empty() bool
+	Set(key int, val int)
+	Get(key int) (int, error)
+	Del(key int) (int, error)
+}
diff --git a/set/set_test.go b/set/set_test.go
new file mode 100644
index 0000000..16d3e8c
--- /dev/null
+++ b/set/set_test.go
@@ -0,0 +1,38 @@
+package set
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/snonux/algorithms/ds"
+)
+
+const factor int = 10
+const minLength int = 1
+const maxLength int = 10
+
+func TestSet(t *testing.T) {
+	s := NewElementary()
+	for i := minLength; i <= maxLength; i *= factor {
+		test(s, i, t)
+	}
+}
+
+func test(s Set, l int, t *testing.T) {
+	cb := func(t *testing.T) {
+		list := ds.NewRandomArrayList(l, -1)
+		for i, a := range list {
+			s.Set(a, i)
+		}
+		for i, a := range list {
+			val, err := s.Get(a)
+			if err != nil {
+				t.Errorf("Element %v: %v", val, err)
+			}
+			if val != i {
+				t.Errorf("Element is %v but expected %v", val, i)
+			}
+		}
+	}
+	t.Run(fmt.Sprintf("%d", l), cb)
+}
diff --git a/set/tree.go b/set/tree.go
index 8233b0e..819f83c 100644
--- a/set/tree.go
+++ b/set/tree.go
@@ -19,63 +19,72 @@ func (t *Tree) Empty() bool {
 	return t.root == nil
 }
 
-func (t *Tree) set(n *node, key, val int) {
-	switch {
-	case key < n.key:
-		if n.left == nil {
-			n.left = &node{key, val, nil, nil}
-			return
-		}
-		t.set(n.left, key, val)
-
-	case key > n.key:
-		if n.right == nil {
-			n.right = &node{key, val, nil, nil}
-			return
-		}
-		t.set(n.right, key, val)
-	default:
-		// Val is already in the tree
-	}
-}
-
 func (t *Tree) Set(key, val int) {
 	if t.Empty() {
 		t.root = &node{key, val, nil, nil}
 		return
 	}
-	t.set(t.root, key, val)
+	ptr, _, err := t.search(&t.root, key)
+	if err != nil {
+		// key already in the tree as node found
+		return
+	}
+
+	*ptr = &node{key, val, nil, nil}
 }
 
-func (t *Tree) get(n *node, key int) (int, error) {
-	if n == nil {
-		return 0, NotFound
+func (t *Tree) Get(key int) (int, error) {
+	_, n, err := t.search(&t.root, key)
+	return n.val, err
+}
+
+func (t *Tree) Del(key int) (int, error) {
+	ptr, n, err := t.search(&t.root, key)
+	if err != nil {
+		return n.val, err
 	}
 
+	// Case 1: n is leaf node
+	// Case 2: n has one child
+	// Case 3: n has two childs
+
 	switch {
-	case key < n.key:
-		return t.get(n.left, key)
-	case key > n.key:
-		return t.get(n.right, key)
-	default:
+	case n.left == nil:
+		if n.right == nil {
+			// I am a leaf node
+			*ptr = nil
+			return n.val, nil
+		}
+		// I have a right child
+		*ptr = n.right
+		return n.val, nil
+
+	case n.right == nil:
+		// I have a left child
+		*ptr = n.left
 		return n.val, nil
+	default:
+		// I have two childs!
+		return 0, NotImplemented
 	}
 }
 
-func (t *Tree) Get(key int) (int, error) {
-	return t.get(t.root, key)
+func (t *Tree) min(ptr **node) (**node, *node, error) {
+	return nil, nil, NotImplemented
 }
 
-func (t *Tree) Del(key int) (int, error) {
-	if t.root == nil {
-		return 0, NotFound
+func (t *Tree) search(ptr **node, key int) (**node, *node, error) {
+	n := *ptr
+	if n == nil {
+		return ptr, nil, NotFound
 	}
 
-	if t.root.key == key {
-		val := t.root.val
-
-		return val, nil
+	switch {
+	case key < n.key:
+		return t.search(&n.left, key)
+	case n.key < key:
+		return t.search(&n.right, key)
+	default:
+		return ptr, n, nil
 	}
-
-	return 0, NotImplemented
 }