avl_test.go

package avl

import (
	"math/rand"
	"reflect"
	"sort"
	"testing"
)

func TestInsertContains(t *testing.T) {
	var tr Tree[int]
	keys := []int{10, 20, 30, 40, 50, 25}
	for _, k := range keys {
		if !tr.Insert(k) {
			t.Errorf("Insert(%d) returned false on first insert", k)
		}
	}
	if tr.Insert(10) {
		t.Error("Insert(10) twice returned true")
	}
	if tr.Len() != len(keys) {
		t.Errorf("Len = %d", tr.Len())
	}
	for _, k := range keys {
		if !tr.Contains(k) {
			t.Errorf("Contains(%d) = false", k)
		}
	}
	if tr.Contains(999) {
		t.Error("Contains(999) = true")
	}
	if !tr.IsBalanced() {
		t.Error("tree is not balanced")
	}
}

func TestInOrderSorted(t *testing.T) {
	r := rand.New(rand.NewSource(123))
	var tr Tree[int]
	want := make(map[int]struct{})
	for i := 0; i < 500; i++ {
		v := r.Intn(10000)
		tr.Insert(v)
		want[v] = struct{}{}
	}
	got := tr.InOrder()
	expected := make([]int, 0, len(want))
	for k := range want {
		expected = append(expected, k)
	}
	sort.Ints(expected)
	if !reflect.DeepEqual(got, expected) {
		t.Errorf("InOrder mismatch: got %d keys, want %d", len(got), len(expected))
	}
	if !tr.IsBalanced() {
		t.Error("not balanced after random inserts")
	}
}

func TestDelete(t *testing.T) {
	var tr Tree[int]
	for _, k := range []int{50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45} {
		tr.Insert(k)
	}

	if !tr.Delete(30) {
		t.Fatal("Delete(30) = false")
	}
	if tr.Contains(30) {
		t.Error("30 still present")
	}
	if !tr.IsBalanced() {
		t.Error("not balanced after delete")
	}

	if tr.Delete(999) {
		t.Error("Delete(999) = true")
	}

	for _, k := range tr.InOrder() {
		if !tr.Contains(k) {
			t.Errorf("Contains(%d) = false after delete", k)
		}
	}
}

func TestStressDelete(t *testing.T) {
	r := rand.New(rand.NewSource(7))
	var tr Tree[int]
	values := r.Perm(2000)
	for _, v := range values {
		tr.Insert(v)
	}
	r.Shuffle(len(values), func(i, j int) { values[i], values[j] = values[j], values[i] })
	for _, v := range values[:1000] {
		if !tr.Delete(v) {
			t.Fatalf("delete %d failed", v)
		}
	}
	if !tr.IsBalanced() {
		t.Fatal("not balanced after stress delete")
	}
	if tr.Len() != 1000 {
		t.Fatalf("Len = %d", tr.Len())
	}
}