redblack

README

ReadBlack search tree

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

	for i := 0; i < 10; i++ {
		rb.Del(i)
	}
	v, ok = rb.Get(5)
	fmt.Printf("Size=%d Get(5)=(%v,%v)\n", rb.Size(), v, ok)
	rb.Print()
	fmt.Println("traversal in order:")
	rb.InOrder(func(n *Node[int, int]) bool {
		fmt.Printf("%v,", n.String())
		return true
	})

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

Documentation

Overview

Example

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

for i := 0; i < 10; i++ {
	rb.Del(i)
}
v, ok = rb.Get(5)
fmt.Printf("Size=%d Get(5)=(%v,%v)\n", rb.Size(), v, ok)
rb.Print()
fmt.Println("traversal in order:")
rb.InOrder(func(n *Node[int, int]) bool {
	fmt.Printf("%v,", n.String())
	return true
})

// Output (Why not match?):
// Size=20 Get(5)=(5,true)
//               (7)
//               / \
//              /   \
//             /     \
//            /       \
//           /         \
//          /           \
//         /             \
//      red[3]         red[11]
//       / \             / \
//      /   \           /   \
//     /     \         /     \
//   (1)     (5)      /       \
//   / \     / \    (9)      (15)
// (0) (2) (4) (6)  / \       / \
//                 /   \     /   \
//               (8)  (10)  /     \
//                         /       \
//                     red[13]   red[17]
//                       / \       / \
//                      /   \     /   \
//                    (12) (14) (16) (18)
//                                      \
//                                    red[19]
// Size=10 Get(5)=(0,false)
//         (15)
//          / \
//         /   \
//        /     \
//       /       \
//     (11)     (17)
//     / \       / \
//    /   \     /   \
//   /     \  (16) (18)
// (10)  red[13]      \
//         / \      red[19]
//        /   \
//      (12) (14)
// traversal in order:
// (10),(11),(12),red[13],(14),(15),(16),(17),(18),red[19],

Index

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

Examples

• Package

Types

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]) 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

type Tree

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

func New

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

func (*Tree[Ord, T]) Del

func (tree *Tree[Ord, T]) Del(key Ord)

func (*Tree[Ord, T]) Get

func (tree *Tree[Ord, T]) Get(key Ord) (T, bool)

func (*Tree[Ord, T]) InOrder

func (tree *Tree[Ord, T]) InOrder(fn func(*Node[Ord, T]) bool)

func (*Tree[Ord, T]) LevelOrder

func (tree *Tree[Ord, T]) LevelOrder(fn func(*Node[Ord, T]) bool)

func (*Tree[Ord, T]) PreOrder

func (tree *Tree[Ord, T]) PreOrder(fn func(*Node[Ord, T]) bool)

func (*Tree[Ord, T]) Print

func (tree *Tree[Ord, T]) Print()

func (*Tree[Ord, T]) Put

func (tree *Tree[Ord, T]) Put(key Ord, val T)

func (*Tree[Ord, T]) ReverseOrder

func (tree *Tree[Ord, T]) ReverseOrder(fn func(*Node[Ord, T]) bool)

func (*Tree[Ord, T]) Size

func (tree *Tree[Ord, T]) Size() uint

func (*Tree[Ord, T]) SufOrder

func (tree *Tree[Ord, T]) SufOrder(fn func(*Node[Ord, T]) bool)