89 lines
1.4 KiB
Go
89 lines
1.4 KiB
Go
package avl
|
|
|
|
import (
|
|
"bytes"
|
|
"fmt"
|
|
"testing"
|
|
)
|
|
|
|
type testKey int
|
|
|
|
func (k testKey) Compare(c Comparable) int {
|
|
var (
|
|
ck testKey
|
|
ok bool
|
|
)
|
|
|
|
if ck, ok = c.(testKey); !ok {
|
|
panic("unexpected type")
|
|
}
|
|
|
|
return int(k - ck)
|
|
}
|
|
|
|
func (k testKey) String() string {
|
|
return fmt.Sprintf("%d", int(k))
|
|
}
|
|
|
|
func preOrder(b *bytes.Buffer, node *Node) {
|
|
if node != nil {
|
|
_, _ = fmt.Fprint(b, node.key, " ")
|
|
preOrder(b, node.left)
|
|
preOrder(b, node.right)
|
|
}
|
|
}
|
|
|
|
func TestInsert(t *testing.T) {
|
|
var (
|
|
root *Node
|
|
b *bytes.Buffer
|
|
)
|
|
|
|
root = Insert(root, testKey(10))
|
|
root = Insert(root, testKey(20))
|
|
root = Insert(root, testKey(30))
|
|
root = Insert(root, testKey(40))
|
|
root = Insert(root, testKey(50))
|
|
root = Insert(root, testKey(25))
|
|
|
|
b = bytes.NewBuffer([]byte{})
|
|
preOrder(b, root)
|
|
|
|
//The constructed AVL Tree would be
|
|
// 30
|
|
// / \
|
|
// 20 40
|
|
// / \ \
|
|
// 10 25 50
|
|
|
|
t.Log("preorder traversal of the tree")
|
|
t.Log(b)
|
|
}
|
|
|
|
func TestInsert2(t *testing.T) {
|
|
var (
|
|
tree *Tree
|
|
keys = []testKey{10, 20, 25, 30, 40, 50}
|
|
out []Comparable
|
|
)
|
|
|
|
tree = new(Tree)
|
|
tree.Insert(keys[0])
|
|
tree.Insert(keys[1])
|
|
tree.Insert(keys[3])
|
|
tree.Insert(keys[4])
|
|
tree.Insert(keys[5])
|
|
tree.Insert(keys[2])
|
|
|
|
out = tree.Slice()
|
|
for i, k := range out {
|
|
if ck, ok := k.(testKey); ok {
|
|
if ck != keys[i] {
|
|
t.Fatal("mismatch data")
|
|
}
|
|
} else {
|
|
t.Fatal("invalid data type")
|
|
}
|
|
}
|
|
}
|