redblack

package module

v0.5.0 Latest Latest Go to latest Published: Oct 22, 2024 License: Unlicense Imports: 6 Imported by: 0

Details

Valid go.mod file
Redistributable license
Tagged version
Stable version
Learn more about best practices

Repository

github.com/gregorgebhardt/redblack

Links

Open Source Insights

README ¶

Red-Black Tree Implementation in Go

This repository contains an implementation of a Red-Black Tree in Go. A Red-Black Tree is a balanced binary search tree with additional properties that ensure the tree remains balanced during insertions and deletions.

Project Structure

node.go: Contains the definition and methods for the tree nodes.
print.go: Contains functions for printing the tree structure.
tree.go: Contains the main Red-Black Tree implementation.
tree_test.go: Contains unit tests for the Red-Black Tree implementation.
examples/: Contains example programs that demonstrate how to use the Red-Black Tree implementation.

Testing

To run the tests, use the go test command:

go test ./...

Examples

Some examples of how the module can be used are located in the examples subdirectory. You can run them using the go run command, for example:

go run examples/ints_and_strings

License

This project is licensed under the Unlicense - see the LICENSE file for details.

Documentation ¶

Index ¶

Constants
func Ordered[T constraints.Ordered](value T) ordered[T]
type Node
- func (n *Node[V, T]) Value() V
type Orderable
type RuneSet
type Tree
- func NewTree[V any, T Orderable[V]](items []T, ignore_duplicates bool) (*Tree[V, T], error)
type WalkOrder

Constants ¶

View Source

const (
	KeyExistsError       = keyError("Key already exists in tree.")
	KeyDoesNotExistError = keyError("Key not found.")
)

Variables ¶

This section is empty.

Functions ¶

func Ordered ¶

func Ordered[T constraints.Ordered](value T) ordered[T]

Types ¶

type Node ¶

type Node[V any, T Orderable[V]] struct {
	// contains filtered or unexported fields
}

func (*Node[V, T]) Value ¶

func (n *Node[V, T]) Value() V

type Orderable ¶

type Orderable[T any] interface {
	// returns a value < 0 if the receiver is less than other, 0 if they are equal, and > 0 if the receiver is greater than other
	CompareTo(other T) int
	Value() T
}

type RuneSet ¶

type RuneSet struct {
	// contains filtered or unexported fields
}

type Tree ¶

type Tree[V any, T Orderable[V]] struct {
	// contains filtered or unexported fields
}

func NewTree ¶

func NewTree[V any, T Orderable[V]](items []T, ignore_duplicates bool) (*Tree[V, T], error)

Creates a new red-black tree from a slice of Orderable items. If ignore_duplicates is true, duplicate items will be ignored otherwise a KeyExistsError will be returned.

func (*Tree[V, T]) Delete ¶

func (t *Tree[V, T]) Delete(v V) (success bool)

Delete removes a node from the tree if the key is found. Returns false if the key is not found.

func (*Tree[V, T]) DeleteMin ¶

func (t *Tree[V, T]) DeleteMin()

DeleteMin removes the node with the smallest key from the tree.

func (*Tree[V, T]) GetTreeLevels ¶

func (t *Tree[V, T]) GetTreeLevels() [][]*Node[V, T]

Returns each level of the tree as a slice of nodes. Ordered from root to leaves.

func (*Tree[V, T]) Height ¶

func (t *Tree[V, T]) Height() int

Height return the height of the tree. The height of a tree is the number of edges on the longest path between the root and a leaf.

func (*Tree[V, T]) Insert ¶

func (t *Tree[V, T]) Insert(item T) error

Insert adds a new node to the tree if the item is not a duplicate of another item in the tree. Returns KeyExistsError if the key already exists in the tree.

func (*Tree[V, T]) Len ¶

func (t *Tree[V, T]) Len() int

Len returns the number of nodes in the tree.

func (*Tree[V, T]) Max ¶

func (t *Tree[V, T]) Max() V

Max returns the largest key in the tree.

func (*Tree[V, T]) Min ¶

func (t *Tree[V, T]) Min() V

Min returns the smallest key in the tree.

func (*Tree[V, T]) Search ¶

func (t *Tree[V, T]) Search(k V) (bool, V)

Search returns true if the key is found in the tree and the value of the key. If the key is not found, the second return value is the key itself.

func (*Tree[V, T]) SearchLower ¶

func (t *Tree[V, T]) SearchLower(k V) (V, error)

SearchLower returns the value of the largest key in the tree that is less than or equal to the given key. Returns KeyDoesNotExistError if k < i for all i in the tree.

func (*Tree[V, T]) SearchUpper ¶

func (t *Tree[V, T]) SearchUpper(k V) (V, error)

SearchUpper returns the value of the smallest key in the tree that is greater than or equal to the given key. Returns KeyDoesNotExistError if k > i for all i in the tree.

func (Tree[V, T]) Sorted ¶

func (t Tree[V, T]) Sorted() iter.Seq[V]

Returns an iterator that yields the keys in the tree in sorted order.

func (Tree[V, T]) String ¶

func (t Tree[V, T]) String() string

String returns a string representation of the tree.

func (*Tree[V, T]) ToSortedSlice ¶

func (t *Tree[V, T]) ToSortedSlice() []V

Returns a sorted slice of the keys in the tree.

func (*Tree[V, T]) Walk ¶

func (t *Tree[V, T]) Walk(f func(*Node[V, T]) bool, order WalkOrder)

Walks the tree in the specified order and calls the given function for each node. If the function returns false, the walk is stopped. The order can be INORDER, PREORDER, POSTORDER or LEVELORDER.

type WalkOrder ¶

type WalkOrder int

WalkOrder specifies the order in which the nodes are visited when walking the tree.

const (
	// INORDER visits all left children (smaller keys), then the current node, then all right children (larger keys).
	// This results in keys being visited in ascending order.
	INORDER WalkOrder = iota
	// PREORDER visits the current node before its child nodes (left child before right child).
	PREORDER
	// POSTORDER visits the current node after its child nodes (left child before right child).
	POSTORDER
	// LEVELORDER visits the nodes level by level from left to right.
	LEVELORDER
)

Source Files ¶

View all Source files

Directories ¶

Path	Synopsis
examples
ints_and_strings command
strings_and_strings command

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL