From 24c2952ab16680383864625c8cc8cd73bfd94849 Mon Sep 17 00:00:00 2001 From: Paul Buetow Date: Thu, 5 Nov 2020 09:42:08 +0000 Subject: BST basic unit test works --- set/bst.go | 143 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ set/set_test.go | 10 +++- set/tree.go | 137 ----------------------------------------------------- 3 files changed, 152 insertions(+), 138 deletions(-) create mode 100644 set/bst.go delete mode 100644 set/tree.go diff --git a/set/bst.go b/set/bst.go new file mode 100644 index 0000000..febf4d4 --- /dev/null +++ b/set/bst.go @@ -0,0 +1,143 @@ +package set + +type node struct { + key int + val int + left *node + right *node +} + +type BST struct { + root *node +} + +func NewBST() *BST { + return &BST{} +} + +func (t *BST) Empty() bool { + return t.root == nil +} + +func (t *BST) Set(key, val int) { + if t.Empty() { + t.root = &node{key, val, nil, nil} + return + } + ptr, _, err := t.search(&t.root, key) + switch err { + case nil: + // key already in the tree + return + case NotFound: + *ptr = &node{key, val, nil, nil} + return + default: + panic(err) + } +} + +func (t *BST) Get(key int) (int, error) { + _, n, err := t.search(&t.root, key) + return n.val, err +} + +func (t *BST) Del(key int) (int, error) { + ptr, n, err := t.search(&t.root, key) + if err != nil { + return 0, err + } + + // Case 1: n is leaf node + // Case 2: n has one child + // Case 3: n has two childs + + switch { + 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 children! + + o, err := t.deleteMin(&n.right) + if err != nil { + return 0, err + } + + o.left = n.left + o.right = n.right + *ptr = o + + return n.val, nil + } +} + +func (t *BST) search(ptr **node, key int) (**node, *node, error) { + n := *ptr + if n == nil { + return ptr, nil, NotFound + } + + 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 + } +} + +func (t *BST) deleteMin(ptr **node) (*node, error) { + ptr, n, err := t.min(ptr) + if err != nil { + return nil, err + } + + *ptr = n.right + n.right = nil + return n, nil +} + +func (t *BST) min(ptr **node) (**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 = *ptr + } +} + +/* +func (t *BST) max(ptr **node) (**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 = *ptr + } +} +*/ diff --git a/set/set_test.go b/set/set_test.go index 16d3e8c..cd44e24 100644 --- a/set/set_test.go +++ b/set/set_test.go @@ -11,17 +11,25 @@ const factor int = 10 const minLength int = 1 const maxLength int = 10 -func TestSet(t *testing.T) { +func TestElementary(t *testing.T) { s := NewElementary() for i := minLength; i <= maxLength; i *= factor { test(s, i, t) } } +func TestBST(t *testing.T) { + s := NewBST() + 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 { + t.Log("Inserting", a, i, s) s.Set(a, i) } for i, a := range list { diff --git a/set/tree.go b/set/tree.go deleted file mode 100644 index 8819791..0000000 --- a/set/tree.go +++ /dev/null @@ -1,137 +0,0 @@ -package set - -type node struct { - key int - val int - left *node - right *node -} - -type Tree struct { - root *node -} - -func NewTree() *Tree { - return &Tree{} -} - -func (t *Tree) Empty() bool { - return t.root == nil -} - -func (t *Tree) Set(key, val int) { - if t.Empty() { - t.root = &node{key, val, nil, nil} - return - } - 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(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 0, err - } - - // Case 1: n is leaf node - // Case 2: n has one child - // Case 3: n has two childs - - switch { - 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 children! - - o, err := t.deleteMin(&n.right) - if err != nil { - return 0, err - } - - o.left = n.left - o.right = n.right - *ptr = o - - return n.val, nil - } -} - -func (t *Tree) search(ptr **node, key int) (**node, *node, error) { - n := *ptr - if n == nil { - return nil, nil, NotFound - } - - 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 - } -} - -func (t *Tree) deleteMin(ptr **node) (*node, error) { - ptr, n, err := t.min(ptr) - if err != nil { - return nil, err - } - - *ptr = n.right - n.right = nil - return n, nil -} - -func (t *Tree) min(ptr **node) (**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 = *ptr - } -} - -func (t *Tree) max(ptr **node) (**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 = *ptr - } -} -- cgit v1.2.3