btree.go

package btree

package btree

type Node interface {
	Size() int
	Sum() int64
	Min() int64
	Max() int64
	Find(value int64) *int64
}

type Leaf struct {
	Value int64
}

type Branch struct {
	Left Node
	Value int64
	Right Node
}

func (l Leaf) Size() int {
	return 1
}

func (b Branch) Size() int {
	return b.Left.Size() + 1 + b.Right.Size()
}

func (l Leaf) Sum() int64 {
	return l.Value
}

func (b Branch) Sum() int64 {
	return b.Left.Sum() + b.Value + b.Right.Sum()
}

func (l Leaf) Min() int64 {
	return l.Value
}

func (b Branch) Min() int64 {
	return b.Left.Min()
}

func (l Leaf) Max() int64 {
	return l.Value
}

func (b Branch) Max() int64 {
	return b.Right.Max()
}

func (l Leaf) Find(value int64) *int64 {
	if l.Value == value {
		return &l.Value
	} else {
		return nil
	}
}

func (b Branch) Find(value int64) *int64 {
	if b.Value == value {
		return &b.Value
	} else if b.Value > value {
		return b.Left.Find(value)
	} else if b.Value < value {
		return b.Right.Find(value)
	} else {
		return nil
	}
}