tree

Documentation

Index

• type Rbtree
  • func NewRbtree[K, T any](getKey func(T) K, lessthan func(K, K) bool) Rbtree[K, T]
• type RbtreeNode
  • func (n *RbtreeNode[T]) Next() *RbtreeNode[T]
  • func (n *RbtreeNode[T]) Prev() *RbtreeNode[T]

Types

type Rbtree

type Rbtree[K, T any] interface {
	Key(v T) K        //节点的key
	Less(l, r K) bool //节点排序规则
	Len() int
	Replace(v T) *RbtreeNode[T]          //插入节点，重复则替换
	Insert(v T) *RbtreeNode[T]           //插入节点，重复则忽视
	InsertRepeatable(v T) *RbtreeNode[T] //插入节点，允许数据重复
	Front() *RbtreeNode[T]               //查询有序节点的第一个节点
	Back() *RbtreeNode[T]                //查询有序节点的最后一个节点
	Find(key K) *RbtreeNode[T]           //查找节点，如果存在重复，则返回第一个找到的节点
	LowerBound(key K) *RbtreeNode[T]     //查找第一个不小于(>=)的节点
	UpperBound(key K) *RbtreeNode[T]     //查找第一个大于的节点
	Erase(n *RbtreeNode[T])              //删除节点
	Remove(key K) (T, bool)              //删除一个相同的节点
	RemoveAll(key K) []T                 //删除所有相同的节点
}

func NewRbtree

func NewRbtree[K, T any](getKey func(T) K, lessthan func(K, K) bool) Rbtree[K, T]

定义一个红黑树 getKey:获取value用于比较的key lessthan:定义key的排序规则

type RbtreeNode

type RbtreeNode[T any] struct {
	Value T //值
	// contains filtered or unexported fields
}

定义红黑树节点结构

func (*RbtreeNode[T]) Next

func (n *RbtreeNode[T]) Next() *RbtreeNode[T]

下一个最接近的节点

func (*RbtreeNode[T]) Prev

func (n *RbtreeNode[T]) Prev() *RbtreeNode[T]

前一个最接近的节点