rbtree

README

rbtree

Doc

use

func main() {
	tree := NewRbTree(cmp, false)

	keyList := []int{10, 3, 17, 7, 1, 0, 10, 12, 4, 5}

	for _, key := range keyList {
		tree.Insert(key, key*2)
	}
	for i := len(keyList) - 1; i >= 0; i-- {
		tree.DeleteByKey(keyList[i])
	}
}

test

➜  rbtree git:(main) ✗ go test -v -count=1 
=== RUN   TestRbTree
=========== INSERT: [10 3 17 7 1 0 10 12 4 5] ===========
level:	1	2	3	4	5	6	7	8	...
			17
		12
			10
	10
				7
			5
				4
		3
			1
				0
=========== DELETE: 5 ===========
level:	1	2	3	4	5	6	7	8	...
			17
		12
			10
	10
			7
				4
		3
			1
				0
=========== DELETE: 4 ===========
level:	1	2	3	4	5	6	7	8	...
			17
		12
			10
	10
			7
		3
			1
				0
=========== DELETE: 12 ===========
level:	1	2	3	4	5	6	7	8	...
		17
			10
	10
			7
		3
			1
				0
=========== DELETE: 10 ===========
level:	1	2	3	4	5	6	7	8	...
	17
			7
		3
			1
				0
=========== DELETE: 0 ===========
level:	1	2	3	4	5	6	7	8	...
	17
			7
		3
			1
=========== DELETE: 1 ===========
level:	1	2	3	4	5	6	7	8	...
	17
			7
		3
=========== DELETE: 7 ===========
level:	1	2	3	4	5	6	7	8	...
	17
		3
=========== DELETE: 17 ===========
level:	1	2	3	4	5	6	7	8	...
	3
=========== DELETE: 3 ===========
level:	1	2	3	4	5	6	7	8	...
=========== DELETE: 10 ===========
level:	1	2	3	4	5	6	7	8	...
--- PASS: TestRbTree (0.00s)
PASS
ok  	rbtree	0.441s

Documentation

Index

• type CompareCmd
• type RbNode
• type RbTree
  • func NewRbTree(cmp CompareCmd, unique bool) *RbTree
  • func (rb *RbTree) DeleteByKey(key interface{})
  • func (rb *RbTree) DeleteByNode(z *RbNode)
  • func (rb *RbTree) Find(key interface{}) []*RbNode
  • func (rb *RbTree) First() *RbNode
  • func (rb *RbTree) Insert(key, value interface{})
  • func (rb *RbTree) Last() *RbNode
  • func (rb *RbTree) Next(node *RbNode) *RbNode
  • func (rb *RbTree) Prev(node *RbNode) *RbNode
  • func (rb *RbTree) Size() int

Types

type CompareCmd

type CompareCmd func(interface{}, interface{}) int

CompareCmd

-1: less
 0: equal
 1: more

type RbNode

type RbNode struct {
	K, V interface{}
	// contains filtered or unexported fields
}

RbNode the red-black tree node

type RbTree

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

RbTree the structure of red-black tree

func NewRbTree

func NewRbTree(cmp CompareCmd, unique bool) *RbTree

NewRbTree new

cmp:  method of key comparison
unique: whether to allow duplicate keys

func (*RbTree) DeleteByKey

func (rb *RbTree) DeleteByKey(key interface{})

DeleteByKey delete nodes by key. If unique is false, there may be multiple deleted nodes.

func (*RbTree) DeleteByNode

func (rb *RbTree) DeleteByNode(z *RbNode)

DeleteByNode delete the node directly.

func (*RbTree) Find

func (rb *RbTree) Find(key interface{}) []*RbNode

Find find nodes by key

func (*RbTree) First

func (rb *RbTree) First() *RbNode

First returns the first node (in sort order) of the tree.

func (*RbTree) Insert

func (rb *RbTree) Insert(key, value interface{})

Insert insert

func (*RbTree) Last

func (rb *RbTree) Last() *RbNode

Last returns the last node (in sort order) of the tree.

func (*RbTree) Next

func (rb *RbTree) Next(node *RbNode) *RbNode

Next returns the next node (in sort order) of the tree.

func (*RbTree) Prev

func (rb *RbTree) Prev(node *RbNode) *RbNode

Prev returns the previous node (in sort order) of the tree.

func (*RbTree) Size

func (rb *RbTree) Size() int

Size number of nodes