avlst

README

AVL Tree

package main

import (
	"fmt"

	"github.com/howz97/algorithm/search"
	"github.com/howz97/algorithm/search/avlst"
)

func main() {
	avl := avlst.New[int, int]()
	for i := 0; i < 20; i++ {
		avl.Put(i, i)
	}
	v, ok := avl.Get(5)
	fmt.Printf("Size=%d Get(5)=(%v,%v) \n", avl.Size(), v, ok)
	search.PrintBinaryTree(avl)

	for i := 0; i < 10; i++ {
		avl.Del(i)
	}
	v, ok = avl.Get(5)
	fmt.Printf("Size=%d Get(5)=(%v,%v) \n", avl.Size(), v, ok)
	search.PrintBinaryTree(avl)

	fmt.Println("traversal in order:")
	search.InOrder(avl, func(t search.ITraversal) bool {
		fmt.Printf("%v,", t.String())
		return true
	})

	// Size=20 Get(5)=(5,true)
	//            7
	//           / \
	//          /   \
	//         /     \
	//        /       \
	//       /         \
	//      3          15
	//     / \         / \
	//    /   \       /   \
	//   1     5     11   17
	//  / \   / \   / \   / \
	// 0   2 4   6 /   \ 16 18
	//            9    13     \
	//           / \   / \    19
	//          8  10 12 14
	// Size=10 Get(5)=(0,false)
	//     15
	//     / \
	//    /   \
	//   11   17
	//  / \   / \
	// 10 13 16 18
	//    / \     \
	//   12 14    19
	// traversal in order:
	// 10,11,12,13,14,15,16,17,18,19,
}

Documentation

Index

• type AVL
  • func New[Ord constraints.Ordered, T any]() *AVL[Ord, T]
  • func (avl *AVL[Ord, T]) Del(key Ord)
  • func (avl *AVL[Ord, T]) Get(key Ord) (T, bool)
  • func (avl *AVL[Ord, T]) GetMax() T
  • func (avl *AVL[Ord, T]) GetMin() T
  • func (avl *AVL[Ord, T]) InOrder(fn func(*Node[Ord, T]) bool)
  • func (avl *AVL[Ord, T]) IsNil() bool
  • func (avl *AVL[Ord, T]) Left() search.ITraversal
  • func (avl *AVL[Ord, T]) LevelOrder(fn func(*Node[Ord, T]) bool)
  • func (avl *AVL[Ord, T]) PreOrder(fn func(*Node[Ord, T]) bool)
  • func (avl *AVL[Ord, T]) Print()
  • func (avl *AVL[Ord, T]) Put(key Ord, val T)
  • func (avl *AVL[Ord, T]) ReverseOrder(fn func(*Node[Ord, T]) bool)
  • func (avl *AVL[Ord, T]) Right() search.ITraversal
  • func (avl *AVL[Ord, T]) Size() uint
  • func (avl *AVL[Ord, T]) String() string
  • func (avl *AVL[Ord, T]) SufOrder(fn func(*Node[Ord, T]) bool)
• type Node
  • func (n *Node[Ord, T]) IsNil() bool
  • func (n *Node[Ord, T]) Key() Ord
  • func (n *Node[Ord, T]) Left() search.ITraversal
  • func (n *Node[Ord, T]) Right() search.ITraversal
  • func (n *Node[Ord, T]) String() string

Types

type AVL

type AVL[Ord constraints.Ordered, T any] struct {
	// contains filtered or unexported fields
}

AVL is a strictly balanced binary search tree

func New

func New[Ord constraints.Ordered, T any]() *AVL[Ord, T]

func (*AVL[Ord, T]) Del

func (avl *AVL[Ord, T]) Del(key Ord)

func (*AVL[Ord, T]) Get

func (avl *AVL[Ord, T]) Get(key Ord) (T, bool)

func (*AVL[Ord, T]) GetMax

func (avl *AVL[Ord, T]) GetMax() T

func (*AVL[Ord, T]) GetMin

func (avl *AVL[Ord, T]) GetMin() T

func (*AVL[Ord, T]) InOrder

func (avl *AVL[Ord, T]) InOrder(fn func(*Node[Ord, T]) bool)

func (*AVL[Ord, T]) IsNil

func (avl *AVL[Ord, T]) IsNil() bool

IsNil implements search.ITraversal.

func (*AVL[Ord, T]) Left

func (avl *AVL[Ord, T]) Left() search.ITraversal

Left implements search.ITraversal.

func (*AVL[Ord, T]) LevelOrder

func (avl *AVL[Ord, T]) LevelOrder(fn func(*Node[Ord, T]) bool)

func (*AVL[Ord, T]) PreOrder

func (avl *AVL[Ord, T]) PreOrder(fn func(*Node[Ord, T]) bool)

func (*AVL[Ord, T]) Print

func (avl *AVL[Ord, T]) Print()

func (*AVL[Ord, T]) Put

func (avl *AVL[Ord, T]) Put(key Ord, val T)

func (*AVL[Ord, T]) ReverseOrder

func (avl *AVL[Ord, T]) ReverseOrder(fn func(*Node[Ord, T]) bool)

func (*AVL[Ord, T]) Right

func (avl *AVL[Ord, T]) Right() search.ITraversal

Right implements search.ITraversal.

func (*AVL[Ord, T]) Size

func (avl *AVL[Ord, T]) Size() uint

func (*AVL[Ord, T]) String

func (avl *AVL[Ord, T]) String() string

String implements search.ITraversal.

func (*AVL[Ord, T]) SufOrder

func (avl *AVL[Ord, T]) SufOrder(fn func(*Node[Ord, T]) bool)

type Node

type Node[Ord constraints.Ordered, T any] struct {
	// contains filtered or unexported fields
}

func (*Node[Ord, T]) IsNil

func (n *Node[Ord, T]) IsNil() bool

func (*Node[Ord, T]) Key

func (n *Node[Ord, T]) Key() Ord

func (*Node[Ord, T]) Left

func (n *Node[Ord, T]) Left() search.ITraversal

func (*Node[Ord, T]) Right

func (n *Node[Ord, T]) Right() search.ITraversal

func (*Node[Ord, T]) String

func (n *Node[Ord, T]) String() string