rb

package

v0.2.0 Latest Latest Go to latest Published: Jan 4, 2024 License: MIT Imports: 3 Imported by: 0

Details

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

Repository

github.com/alexander-yu/stream

Links

Open Source Insights

Documentation ¶

Overview ¶

Package rb provides the implementation for a red black tree, which satisfies the ost package interfaces, as well as the order package interfaces.

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

This section is empty.

Types ¶

type Color ¶

type Color bool

Color represents the color of the node.

const (
	Red   Color = true
	Black Color = false
)

The only allowed colors are red and black.

func (Color) String ¶

func (c Color) String() string

type Node ¶

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

Node represents a node in a red black tree.

func NewNode ¶

func NewNode(val float64) *Node

NewNode instantiates a Node struct with a a provided value.

func (*Node) Color ¶

func (n *Node) Color() Color

Color returns the color of the node. By default, nil nodes are black.

func (*Node) Left ¶

func (n *Node) Left() (order.Node, error)

Left returns the left child of the node.

func (*Node) Rank ¶

func (n *Node) Rank(val float64) int

Rank returns the number of nodes strictly less than the value that are contained in the subtree rooted at the node.

func (*Node) Right ¶

func (n *Node) Right() (order.Node, error)

Right returns the right child of the node.

func (*Node) Select ¶

func (n *Node) Select(k int) order.Node

Select returns the node with the kth smallest value in the subtree rooted at the node..

func (*Node) Size ¶

func (n *Node) Size() int

Size returns the size of the subtree rooted at the node.

func (*Node) TreeString ¶

func (n *Node) TreeString() string

TreeString returns the string representation of the subtree rooted at the node.

func (*Node) Value ¶

func (n *Node) Value() float64

Value returns the value stored at the node.

type Tree ¶

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

Tree implements a red-black tree data structure, and also satisfies the st.Tree interface, as well as the order.Statistic interface.

func (*Tree) Add ¶

func (t *Tree) Add(val float64)

Add inserts a value into the tree.

func (*Tree) Clear ¶

func (t *Tree) Clear()

Clear resets the tree.

func (*Tree) Rank ¶

func (t *Tree) Rank(val float64) int

Rank returns the number of nodes strictly less than the value.

func (*Tree) Remove ¶

func (t *Tree) Remove(val float64)

Remove deletes a value from the tree.

func (*Tree) Select ¶

func (t *Tree) Select(k int) order.Node

Select returns the node with the kth smallest value in the tree.

func (*Tree) Size ¶

func (t *Tree) Size() int

Size returns the size of the tree.

func (*Tree) String ¶

func (t *Tree) String() string

String returns the string representation of the tree.

Source Files ¶

View all Source files

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