LLRBTree

Documentation

Index

• Constants
• type LLRBTNode
  • func MoveRedLeft(h *LLRBTNode) *LLRBTNode
  • func MoveRedRight(h *LLRBTNode) *LLRBTNode
  • func (node *LLRBTNode) ColorChange()
  • func (node *LLRBTNode) Delete(value int64) *LLRBTNode
  • func (node *LLRBTNode) DeleteMin() *LLRBTNode
  • func (node *LLRBTNode) Find(value int64) *LLRBTNode
  • func (node *LLRBTNode) FindMaxValue() *LLRBTNode
  • func (node *LLRBTNode) FindMinValue() *LLRBTNode
  • func (node *LLRBTNode) FixUp() *LLRBTNode
  • func (node *LLRBTNode) IsRed() bool
  • func (node *LLRBTNode) MidOrder()
  • func (node *LLRBTNode) RotateLeft() *LLRBTNode
  • func (node *LLRBTNode) RotateRight() *LLRBTNode
• type LLRBTree
  • func NewLLRBTree() *LLRBTree
  • func (tree *LLRBTree) Add(value int64)
  • func (tree *LLRBTree) Delete(value int64)
  • func (tree *LLRBTree) Find(value int64) *LLRBTNode
  • func (tree *LLRBTree) FindMaxValue() *LLRBTNode
  • func (tree *LLRBTree) FindMinValue() *LLRBTNode
  • func (tree *LLRBTree) MidOrder()

Constants

const (
	RED   = true
	BLACK = false
)

Types

type LLRBTNode

type LLRBTNode struct {
	Value int64      // 值
	Times int64      // 值出现的次数
	Left  *LLRBTNode // 左子树
	Right *LLRBTNode // 右子树
	Color bool       // 父亲指向该节点的链接颜色
}

LLRBTNode 左倾红黑树节点

func MoveRedLeft

func MoveRedLeft(h *LLRBTNode) *LLRBTNode

MoveRedLeft 红色左移 节点 h 是红节点，其左儿子和左儿子的左儿子都为黑节点，左移后使得其左儿子或左儿子的左儿子有 一个是红色节点

func MoveRedRight

func MoveRedRight(h *LLRBTNode) *LLRBTNode

MoveRedRight /*

func (*LLRBTNode) ColorChange

func (node *LLRBTNode) ColorChange()

ColorChange 调整颜色

func (*LLRBTNode) Delete

func (node *LLRBTNode) Delete(value int64) *LLRBTNode

Delete 对该节点所在的子树删除元素

func (*LLRBTNode) DeleteMin

func (node *LLRBTNode) DeleteMin() *LLRBTNode

DeleteMin 对该节点所在的子树删除最小元素

func (*LLRBTNode) Find

func (node *LLRBTNode) Find(value int64) *LLRBTNode

func (*LLRBTNode) FindMaxValue

func (node *LLRBTNode) FindMaxValue() *LLRBTNode

func (*LLRBTNode) FindMinValue

func (node *LLRBTNode) FindMinValue() *LLRBTNode

func (*LLRBTNode) FixUp

func (node *LLRBTNode) FixUp() *LLRBTNode

FixUp 恢复左倾红黑树特征

func (*LLRBTNode) IsRed

func (node *LLRBTNode) IsRed() bool

IsRed 节点颜色

func (*LLRBTNode) MidOrder

func (node *LLRBTNode) MidOrder()

func (*LLRBTNode) RotateLeft

func (node *LLRBTNode) RotateLeft() *LLRBTNode

RotateLeft 左旋

func (*LLRBTNode) RotateRight

func (node *LLRBTNode) RotateRight() *LLRBTNode

RotateRight 右旋

type LLRBTree

type LLRBTree struct {
	Root *LLRBTNode
}

LLRBTree 左倾红黑树

func NewLLRBTree

func NewLLRBTree() *LLRBTree

func (*LLRBTree) Add

func (tree *LLRBTree) Add(value int64)

func (*LLRBTree) Delete

func (tree *LLRBTree) Delete(value int64)

Delete 左倾红黑树删除元素

func (*LLRBTree) Find

func (tree *LLRBTree) Find(value int64) *LLRBTNode

Find 查找指定节点

func (*LLRBTree) FindMaxValue

func (tree *LLRBTree) FindMaxValue() *LLRBTNode

FindMaxValue 找出最大值的节点

func (*LLRBTree) FindMinValue

func (tree *LLRBTree) FindMinValue() *LLRBTNode

FindMinValue 找出最小值的节点

func (*LLRBTree) MidOrder

func (tree *LLRBTree) MidOrder()

MidOrder 中序遍历