rbtree

Documentation

Index

• type Node
  • func (o *Node[K, V]) IsRed() bool
  • func (o *Node[K, V]) Key() K
  • func (o *Node[K, V]) KeyValue() (K, V)
  • func (o *Node[K, V]) Max() (node *Node[K, V])
  • func (o *Node[K, V]) Min() (node *Node[K, V])
  • func (o *Node[K, V]) Range(f func(o *Node[K, V]) bool)
  • func (o *Node[K, V]) Size() int
  • func (o *Node[K, V]) String() string
• type Option
  • func WithUpsert[K cmp.Ordered, V any](upsert func(old, new V) V) Option[K, V]
• type Tree
  • func NewIntTree[V any](opts ...Option[int, V]) *Tree[int, V]
  • func NewStringTree[V any](opts ...Option[string, V]) *Tree[string, V]
  • func NewTree[K cmp.Ordered, V any](opts ...Option[K, V]) *Tree[K, V]
  • func (t *Tree[K, V]) Between(left, right K, f func(o *Node[K, V]))
  • func (t *Tree[K, V]) Ceil(key K) (ceil *Node[K, V])
  • func (t *Tree[K, V]) Delete(key K)
  • func (t *Tree[K, V]) Floor(key K) (floor *Node[K, V])
  • func (t *Tree[K, V]) Get(key K) *Node[K, V]
  • func (t *Tree[K, V]) Keys() []K
  • func (t *Tree[K, V]) Max() *Node[K, V]
  • func (t *Tree[K, V]) Min() *Node[K, V]
  • func (t *Tree[K, V]) Put(key K, value V) (isNew bool)
  • func (t *Tree[K, V]) Range(f func(o *Node[K, V]) bool)
  • func (t *Tree[K, V]) Root() *Node[K, V]
  • func (t *Tree[K, V]) Size() int
  • func (t *Tree[K, V]) String() string
  • func (t *Tree[K, V]) Update(key K, value V)
  • func (t *Tree[K, V]) Values() []V

Types

type Node

type Node[K cmp.Ordered, V any] struct {
	Left  *Node[K, V]
	Right *Node[K, V]

	Value V
	// contains filtered or unexported fields
}

func (*Node[K, V]) IsRed

func (o *Node[K, V]) IsRed() bool

IsRed 返回节点是否为红色 如果结点为 nil，代表是叶子结点，那么为黑色，返回 false

func (*Node[K, V]) Key

func (o *Node[K, V]) Key() K

func (*Node[K, V]) KeyValue

func (o *Node[K, V]) KeyValue() (K, V)

func (*Node[K, V]) Max

func (o *Node[K, V]) Max() (node *Node[K, V])

func (*Node[K, V]) Min

func (o *Node[K, V]) Min() (node *Node[K, V])

func (*Node[K, V]) Range

func (o *Node[K, V]) Range(f func(o *Node[K, V]) bool)

Range 中序遍历红黑树，也就是升序遍历

func (*Node[K, V]) Size

func (o *Node[K, V]) Size() int

func (*Node[K, V]) String

func (o *Node[K, V]) String() string

type Option

type Option[K cmp.Ordered, V any] func(t *Tree[K, V])

Option 用于修改 Tree 的配置

func WithUpsert

func WithUpsert[K cmp.Ordered, V any](upsert func(old, new V) V) Option[K, V]

WithUpsert 配置 Put 操作时，如何更新已存在节点 Node.Value

type Tree

type Tree[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Tree 实现了左倾红黑树，左倾红黑树是 2-3树在二叉树上的转换，因此 2-3 树与左倾红黑树是等价的。

func NewIntTree

func NewIntTree[V any](opts ...Option[int, V]) *Tree[int, V]

NewIntTree 初始化 int 类型的左倾红黑树，参数 opts 用于修改红黑树的配置

目前可以修改的配置有 1. upsert 字段用于 Put 操作时，如何更新已存在节点的 Value，默认情况下会替换为输入的 value

func NewStringTree

func NewStringTree[V any](opts ...Option[string, V]) *Tree[string, V]

NewStringTree 初始化 string 类型的左倾红黑树，参数 opts 用于修改红黑树的配置

目前可以修改的配置有 1. upsert 字段用于 Put 操作时，如何更新已存在节点的 Value，默认情况下会替换为输入的 value

func NewTree

func NewTree[K cmp.Ordered, V any](opts ...Option[K, V]) *Tree[K, V]

NewTree 初始化左倾红黑树，参数 opts 用于修改红黑树的配置

目前可以修改的配置有 1. upsert 字段用于 Put 操作时，如何更新已存在节点的 Value，默认情况下会替换为输入的 value

func (*Tree[K, V]) Between

func (t *Tree[K, V]) Between(left, right K, f func(o *Node[K, V]))

func (*Tree[K, V]) Ceil

func (t *Tree[K, V]) Ceil(key K) (ceil *Node[K, V])

Ceil 寻找给定 key的 ceil 节点，ceil 节点定义为：在大于等于 key 节点中的最小值 如果 ceil 为 nil，则意味着树是空的，或者树中所有元素都小于 key

func (*Tree[K, V]) Delete

func (t *Tree[K, V]) Delete(key K)

Delete 从树中删除指定 key 的节点，如果节点不存在，那么什么也不做

func (*Tree[K, V]) Floor

func (t *Tree[K, V]) Floor(key K) (floor *Node[K, V])

Floor 寻找给定 key 的 floor 节点，floor 节点定义为：在小于等于 key 节点中的最大值， 如果 floor 为 nil，则意味着树是空的，或者树中所有元素都大于 key。

func (*Tree[K, V]) Get

func (t *Tree[K, V]) Get(key K) *Node[K, V]

Get 返回树中寻找指定 key 的节点，如果返回的是 nil, 则代表未找到

func (*Tree[K, V]) Keys

func (t *Tree[K, V]) Keys() []K

func (*Tree[K, V]) Max

func (t *Tree[K, V]) Max() *Node[K, V]

func (*Tree[K, V]) Min

func (t *Tree[K, V]) Min() *Node[K, V]

func (*Tree[K, V]) Put

func (t *Tree[K, V]) Put(key K, value V) (isNew bool)

Put 向树中插入新的节点，如果节点已存在，则按照 t.upsert 更新节点值 t.upsert 默认情况，节点 *Node.Value 会替换为输入的 value

func (*Tree[K, V]) Range

func (t *Tree[K, V]) Range(f func(o *Node[K, V]) bool)

Range 按照升序，遍历树中的节点

func (*Tree[K, V]) Root

func (t *Tree[K, V]) Root() *Node[K, V]

func (*Tree[K, V]) Size

func (t *Tree[K, V]) Size() int

func (*Tree[K, V]) String

func (t *Tree[K, V]) String() string

func (*Tree[K, V]) Update

func (t *Tree[K, V]) Update(key K, value V)

Update 更新树中指定 key 节点的 value，如果节点不存在，则什么都不做

func (*Tree[K, V]) Values

func (t *Tree[K, V]) Values() []V