bst

Documentation

Index

• type Ord
• type Tree
  • func NewBst[V Ord](vals ...V) *Tree[V]
  • func (root *Tree[V]) Delete(val V) *Tree[V]
  • func (root *Tree[V]) Enumerate(start int, seq iter.Seq[V]) iter.Seq2[int, V]
  • func (root *Tree[V]) Inorder() iter.Seq[V]
  • func (root *Tree[V]) Insert(val V) *Tree[V]
  • func (root *Tree[V]) Levelorder() iter.Seq[V]
  • func (root *Tree[V]) Postorder() iter.Seq[V]
  • func (root *Tree[V]) Preorder() iter.Seq[V]
  • func (root *Tree[V]) Search(val V) bool
  • func (root *Tree[V]) String() string
  • func (root *Tree[V]) StringSeq(seq iter.Seq[V]) string

Examples

• NewBst
• Tree.Delete
• Tree.Enumerate
• Tree.Inorder
• Tree.Insert
• Tree.Levelorder
• Tree.Postorder
• Tree.Preorder
• Tree.Search
• Tree.String
• Tree.StringSeq

Types

type Ord

type Ord constraints.Ordered

type Tree

type Tree[V Ord] struct {
	Val    V
	Left   *Tree[V]
	Right  *Tree[V]
	Height int
}

Tree is an AVL tree implementation

func NewBst

func NewBst[V Ord](vals ...V) *Tree[V]

NewBst creates a new AVL tree. If vals are provided, they are added to the tree, and the tree is initialized.

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 1, 4, 5)
	fmt.Println(b)
}

Output:

/\[1 2 3 4 5]

func (*Tree[V]) Delete

func (root *Tree[V]) Delete(val V) *Tree[V]

Delete deletes a value from the AVL tree and returns the new root

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 1, 4, 5)
	b.Delete(3)
	fmt.Println(b)
}

Output:

/\[1 2 4 5]

func (*Tree[V]) Enumerate

func (root *Tree[V]) Enumerate(start int, seq iter.Seq[V]) iter.Seq2[int, V]

Enumerate returns an iter.Seq2[int, V] that traverses the tree in the given order

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 1, 4, 5)
	for i, v := range b.Enumerate(0, b.Inorder()) {
		fmt.Println(i, v)
	}
}

Output:

0 1
1 2
2 3
3 4
4 5

func (*Tree[V]) Inorder

func (root *Tree[V]) Inorder() iter.Seq[V]

Inorder returns an iter.Seq[V] that traverses the tree in inorder

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 1, 4, 5)
	fmt.Print(b.StringSeq(b.Inorder()))
}

Output:

/\[1 2 3 4 5]

func (*Tree[V]) Insert

func (root *Tree[V]) Insert(val V) *Tree[V]

Insert inserts a value into the AVL tree and returns the new root

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 1, 4, 5)
	b.Insert(0)
	fmt.Println(b)
}

Output:

/\[0 1 2 3 4 5]

func (*Tree[V]) Levelorder

func (root *Tree[V]) Levelorder() iter.Seq[V]

Levelorder returns an iter.Seq[V] that traverses the tree in levelorder

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 4, 1, 5)
	fmt.Print(b.StringSeq(b.Levelorder()))
}

Output:

/\[3 2 4 1 5]

func (*Tree[V]) Postorder

func (root *Tree[V]) Postorder() iter.Seq[V]

Postorder returns an iter.Seq[V] that traverses the tree in postorder

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 4, 1, 5)
	fmt.Print(b.StringSeq(b.Postorder()))
}

Output:

/\[1 2 5 4 3]

func (*Tree[V]) Preorder

func (root *Tree[V]) Preorder() iter.Seq[V]

Preorder returns an iter.Seq[V] that traverses the tree in preorder

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 4, 1, 5)
	fmt.Print(b.StringSeq(b.Preorder()))
}

Output:

/\[3 2 1 4 5]

func (*Tree[V]) Search

func (root *Tree[V]) Search(val V) bool

Search searches for a value in the AVL tree and returns true if it is found

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 1, 4, 5)
	fmt.Println(b.Search(3))
}

Output:

true

func (*Tree[V]) String

func (root *Tree[V]) String() string

String returns a string representation of the tree in inorder

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 1, 4, 5)
	fmt.Println(b)
}

Output:

/\[1 2 3 4 5]

func (*Tree[V]) StringSeq

func (root *Tree[V]) StringSeq(seq iter.Seq[V]) string

StringOrder returns a string representation of the tree in the specified order (preorder, inorder, postorder, levelorder)

Example

package main

import (
	"fmt"

	bt "github.com/elordeiro/go/container/bst"
)

func main() {
	b := bt.NewBst(3, 2, 1, 4, 5)
	fmt.Println(b.StringSeq(b.Inorder()))
}

Output:

/\[1 2 3 4 5]