// 15. hét – Bináris keresőfa
// Futtatás: go run ./h15/bst
package main

import (
	"fmt"
	"math/rand"
	"strings"
)

type Node struct {
	Key         int
	Left, Right *Node
}

type BST struct{ Root *Node }

// Contains – O(h)
func (t *BST) Contains(x int) bool {
	p := t.Root
	for p != nil && p.Key != x {
		if x < p.Key {
			p = p.Left
		} else {
			p = p.Right
		}
	}
	return p != nil
}

func insert(p *Node, x int) *Node {
	if p == nil {
		return &Node{Key: x}
	}
	if x < p.Key {
		p.Left = insert(p.Left, x)
	} else if x > p.Key {
		p.Right = insert(p.Right, x)
	}
	return p
}

func (t *BST) Insert(x int) { t.Root = insert(t.Root, x) }

func (t *BST) Min() int {
	p := t.Root
	for p.Left != nil {
		p = p.Left
	}
	return p.Key
}

func (t *BST) Max() int {
	p := t.Root
	for p.Right != nil {
		p = p.Right
	}
	return p.Key
}

// del: három eset – levél, egy gyerek, két gyerek (inorder rákövetkező)
func del(p *Node, x int) *Node {
	if p == nil {
		return nil
	}
	switch {
	case x < p.Key:
		p.Left = del(p.Left, x)
	case x > p.Key:
		p.Right = del(p.Right, x)
	default:
		if p.Left == nil {
			return p.Right
		}
		if p.Right == nil {
			return p.Left
		}
		s := p.Right
		for s.Left != nil {
			s = s.Left
		}
		p.Key = s.Key
		p.Right = del(p.Right, s.Key)
	}
	return p
}

func (t *BST) Delete(x int) { t.Root = del(t.Root, x) }

func inorder(p *Node, out *[]string) {
	if p == nil {
		return
	}
	inorder(p.Left, out)
	*out = append(*out, fmt.Sprint(p.Key))
	inorder(p.Right, out)
}

func (t *BST) Sorted() string {
	var out []string
	inorder(t.Root, &out)
	return strings.Join(out, " ")
}

func height(p *Node) int {
	if p == nil {
		return -1
	}
	return 1 + max(height(p.Left), height(p.Right))
}

func main() {
	var t BST
	for _, x := range []int{8, 3, 10, 1, 6, 14, 4, 7, 13} {
		t.Insert(x)
	}
	fmt.Println("inorder (rendezett):", t.Sorted())
	fmt.Println("min =", t.Min(), ", max =", t.Max(), ", magasság =", height(t.Root))
	fmt.Println("Contains(7) =", t.Contains(7), ", Contains(5) =", t.Contains(5))
	t.Delete(13)
	fmt.Println("Delete(13) [levél]:       ", t.Sorted())
	t.Delete(10)
	fmt.Println("Delete(10) [egy gyerek]:  ", t.Sorted())
	t.Delete(3)
	fmt.Println("Delete(3)  [két gyerek]:  ", t.Sorted(), ", a gyökér bal gyereke:", t.Root.Left.Key)

	var deg, rnd BST
	for x := 1; x <= 1000; x++ {
		deg.Insert(x)
	}
	r := rand.New(rand.NewSource(1))
	for i := 0; i < 1000; i++ {
		rnd.Insert(r.Intn(1_000_000))
	}
	fmt.Println("\n1000 elem rendezetten beszúrva: magasság =", height(deg.Root), "(lista!)")
	fmt.Println("1000 véletlen elem:             magasság =", height(rnd.Root))
}