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

类型数据结构平均复杂度支持排序有序遍历说明
RedBlackTree红黑树O(log N)写入性能比较好
AVLTree高度平衡树O(log N)查找性能比较好
BTreeB树/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方法都非常类似,特点是需要在初始化时提供用于排序的方法。

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. 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

前序/后续遍历

  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