gtree

支持并发安全开关特性的树形容器,树形数据结构的特点是支持有序遍历、内存占用低、复杂度稳定、适合大数据量存储。该模块包含多个数据结构的树形容器:RedBlackTreeAVLTreeBTree

类型 数据结构 平均复杂度 支持排序 有序遍历 说明
RedBlackTree 红黑树 O(log N) 写入性能比较好
AVLTree 高度平衡树 O(log N) 查找性能比较好
BTree B树/B-树 O(log N) 常用于外部存储

参考连接:https://en.wikipedia.org/wiki/Binary_tree

使用场景

关联数组场景、排序键值对场景、大数据量内存CURD场景等等。

使用方式

  1. import "github.com/gogf/gf/container/gtree"

接口文档

https://godoc.org/github.com/gogf/gf/container/gtree

几种容器的API方法都非常类似,特点是需要在初始化时提供用于排序的方法,以下是红黑树的方法列表。

  1. func NewRedBlackTree(comparator func(v1, v2 interface{}) int, unsafe ...bool) *RedBlackTree
  2. func NewRedBlackTreeFrom(comparator func(v1, v2 interface{}) int, data map[interface{}]interface{}, unsafe ...bool) *RedBlackTree
  3. func (tree *RedBlackTree) Ceiling(key interface{}) (ceiling *RedBlackTreeNode)
  4. func (tree *RedBlackTree) Clear()
  5. func (tree *RedBlackTree) Clone(unsafe ...bool) *RedBlackTree
  6. func (tree *RedBlackTree) Contains(key interface{}) bool
  7. func (tree *RedBlackTree) Flip(comparator ...func(v1, v2 interface{}) int)
  8. func (tree *RedBlackTree) Floor(key interface{}) (floor *RedBlackTreeNode)
  9. func (tree *RedBlackTree) Get(key interface{}) (value interface{})
  10. func (tree *RedBlackTree) GetOrSet(key interface{}, value interface{}) interface{}
  11. func (tree *RedBlackTree) GetOrSetFunc(key interface{}, f func() interface{}) interface{}
  12. func (tree *RedBlackTree) GetOrSetFuncLock(key interface{}, f func() interface{}) interface{}
  13. func (tree *RedBlackTree) GetVar(key interface{}) *gvar.Var
  14. func (tree *RedBlackTree) GetVarOrSet(key interface{}, value interface{}) *gvar.Var
  15. func (tree *RedBlackTree) GetVarOrSetFunc(key interface{}, f func() interface{}) *gvar.Var
  16. func (tree *RedBlackTree) GetVarOrSetFuncLock(key interface{}, f func() interface{}) *gvar.Var
  17. func (tree *RedBlackTree) IsEmpty() bool
  18. func (tree *RedBlackTree) Iterator(f func(key, value interface{}) bool)
  19. func (tree *RedBlackTree) IteratorAsc(f func(key, value interface{}) bool)
  20. func (tree *RedBlackTree) IteratorDesc(f func(key, value interface{}) bool)
  21. func (tree *RedBlackTree) Keys() []interface{}
  22. func (tree *RedBlackTree) Left() *RedBlackTreeNode
  23. func (tree *RedBlackTree) Map() map[interface{}]interface{}
  24. func (tree *RedBlackTree) Print()
  25. func (tree *RedBlackTree) Remove(key interface{}) (value interface{})
  26. func (tree *RedBlackTree) Removes(keys []interface{})
  27. func (tree *RedBlackTree) Right() *RedBlackTreeNode
  28. func (tree *RedBlackTree) Search(key interface{}) (value interface{}, found bool)
  29. func (tree *RedBlackTree) Set(key interface{}, value interface{})
  30. func (tree *RedBlackTree) SetIfNotExist(key interface{}, value interface{}) bool
  31. func (tree *RedBlackTree) SetIfNotExistFunc(key interface{}, f func() interface{}) bool
  32. func (tree *RedBlackTree) SetIfNotExistFuncLock(key interface{}, f func() interface{}) bool
  33. func (tree *RedBlackTree) Sets(data map[interface{}]interface{})
  34. func (tree *RedBlackTree) Size() int
  35. func (tree *RedBlackTree) String() string
  36. func (tree *RedBlackTree) Values() []interface{}

gutil模块中提供了常用的一些基本类型比较方法,可以直接在程序中直接使用,后续也有示例。

  1. func ComparatorByte(a, b interface{}) int
  2. func ComparatorFloat32(a, b interface{}) int
  3. func ComparatorFloat64(a, b interface{}) int
  4. func ComparatorInt(a, b interface{}) int
  5. func ComparatorInt16(a, b interface{}) int
  6. func ComparatorInt32(a, b interface{}) int
  7. func ComparatorInt64(a, b interface{}) int
  8. func ComparatorInt8(a, b interface{}) int
  9. func ComparatorRune(a, b interface{}) int
  10. func ComparatorString(a, b interface{}) int
  11. func ComparatorTime(a, b interface{}) int
  12. func ComparatorUint(a, b interface{}) int
  13. func ComparatorUint16(a, b interface{}) int
  14. func ComparatorUint32(a, b interface{}) int
  15. func ComparatorUint64(a, b interface{}) int
  16. func ComparatorUint8(a, b interface{}) int

使用示例

示例1,基本使用

  1. package main
  2. import (
  3. "fmt"
  4. "github.com/gogf/gf/container/gtree"
  5. "github.com/gogf/gf/util/gutil"
  6. )
  7. func main() {
  8. m := gtree.NewRedBlackTree(gutil.ComparatorInt)
  9. // 设置键值对
  10. for i := 0; i < 10; i++ {
  11. m.Set(i, i*10)
  12. }
  13. // 查询大小
  14. fmt.Println(m.Size())
  15. // 批量设置键值对(不同的数据类型对象参数不同)
  16. m.Sets(map[interface{}]interface{}{
  17. 10: 10,
  18. 11: 11,
  19. })
  20. fmt.Println(m.Size())
  21. // 查询是否存在
  22. fmt.Println(m.Contains(1))
  23. // 查询键值
  24. fmt.Println(m.Get(1))
  25. // 删除数据项
  26. m.Remove(9)
  27. fmt.Println(m.Size())
  28. // 批量删除
  29. m.Removes([]interface{}{10, 11})
  30. fmt.Println(m.Size())
  31. // 当前键名列表(随机排序)
  32. fmt.Println(m.Keys())
  33. // 当前键值列表(随机排序)
  34. fmt.Println(m.Values())
  35. // 查询键名,当键值不存在时,写入给定的默认值
  36. fmt.Println(m.GetOrSet(100, 100))
  37. // 删除键值对,并返回对应的键值
  38. fmt.Println(m.Remove(100))
  39. // 遍历map
  40. m.IteratorAsc(func(k interface{}, v interface{}) bool {
  41. fmt.Printf("%v:%v ", k, v)
  42. return true
  43. })
  44. fmt.Println()
  45. // 清空map
  46. m.Clear()
  47. // 判断map是否为空
  48. fmt.Println(m.IsEmpty())
  49. }

执行后,输出结果为:

  1. 10
  2. 12
  3. true
  4. 10
  5. 11
  6. 9
  7. [0 1 2 3 4 5 6 7 8]
  8. [0 10 20 30 40 50 60 70 80]
  9. 100
  10. 100
  11. 0:0 1:10 2:20 3:30 4:40 5:50 6:60 7:70 8:80
  12. true

示例2,前序/后续遍历

  1. package main
  2. import (
  3. "fmt"
  4. "github.com/gogf/gf/container/gtree"
  5. "github.com/gogf/gf/util/gutil"
  6. )
  7. func main() {
  8. tree := gtree.NewAVLTree(gutil.ComparatorInt)
  9. for i := 0; i < 10; i++ {
  10. tree.Set(i, i*10)
  11. }
  12. // 打印树形
  13. tree.Print()
  14. // 前序遍历
  15. fmt.Println("ASC:")
  16. tree.IteratorAsc(func(key, value interface{}) bool {
  17. fmt.Println(key, value)
  18. return true
  19. })
  20. // 后续遍历
  21. fmt.Println("DESC:")
  22. tree.IteratorDesc(func(key, value interface{}) bool {
  23. fmt.Println(key, value)
  24. return true
  25. })
  26. }

执行后,输出结果为:

  1. AVLTree
  2. │ ┌── 9
  3. │ ┌── 8
  4. │ ┌── 7
  5. │ │ │ ┌── 6
  6. │ │ └── 5
  7. │ │ └── 4
  8. └── 3
  9. │ ┌── 2
  10. └── 1
  11. └── 0
  12. ASC:
  13. 0 0
  14. 1 10
  15. 2 20
  16. 3 30
  17. 4 40
  18. 5 50
  19. 6 60
  20. 7 70
  21. 8 80
  22. 9 90
  23. DESC:
  24. 9 90
  25. 8 80
  26. 7 70
  27. 6 60
  28. 5 50
  29. 4 40
  30. 3 30
  31. 2 20
  32. 1 10
  33. 0 0