Golang中的redblacktree()

一、红黑树

1.红黑树是一种自平衡的二叉搜索树,也是一种高效的查找树。红黑树的应用很广泛,如Java中的TreeMap、JDK1.8中的HashMap等均是基于红黑树实现的。

二、第三方包redblacktree

1.Dataviz是一个数据结构可视化库,通过对 Graphviz的可视化功能用golang来重新打包,已实现在golang中实现基本数据结构的可视化。实现红黑树的地址:

https://github.com/Arafatk/DataViz/tree/master/trees/redblacktree。

2.源码分析:

(1)红黑树的树中结点:redblacktree.Node。在源码中,结构体Node内部包含存放的结点值Key、Key对应的Value、代表的颜色color、结点索引nodeIndex、左右节点Left或Right、父节点Parent等。

(2)红黑树对象类型:redblacktree.Tree。在源码中,结构体Tree内部包含一个类型为*Node的变量Root、大小size、以及一个用于给Tree中的Key排序的Comparator(比较器)变量。

(3)Comparator类型:func(o1, o2 interface{}) int。在源码中,type Comparator被定义为上述的函数结构。具体的Comparator包括IntComparator和StringComparator。

(4)创建红黑树对象:

  ① redblacktree.NewWith(c Comparator):该方法需要传入一个Comparator对象。

  ② redblacktree.NewWithIntComparator() / redblacktree.NewWithStringComparator() :这类方法可通过特定的Comparator创建红黑树对象。

(5)常用操作:(为便于演示,此处创建Tree对象:tree := redblacktree.NewTree())

  ① 根据key值获取value值:val, b := tree.Get(key)。返回值b为bool类型,表示获取成功或失败;val为tree中结点值为key对应的value值。

  ② 加入键值对key-value:tree.Put(key, value)。

  ③ 获取tree中的结点数目:tree.Size()。返回值为int型。

  ④ 根据key删除某结点:tree.Remove(key)。

  ⑤ 获取tree中最小/最大的key对应的结点:tree.Left()。返回值为Node类型,通过tree.Left().Key可得到该Node对象存放的key值(interface{}类型),若此前定义过Comparator的类型为int或string,可

通过断言获取实际key值:如通过tree.Left().Key.(int)可获取到类型为int的key值,而非interface{}。Left()获取最小key值对应的Node,Right()获取最大key值对应的Node。

  ⑥ 获取tree中小于key的最大key对应的Node:floor, b := tree.Floor()。floor为*Node类型,b为bool类型。

  ⑦ 获取tree中大于key的最小key对应的Node:ceiling, b := tree.Ceiling()。ceiling为*Node类型,b为bool类型。

————————

一、红黑树

1.红黑树是一种自平衡的二叉搜索树,也是一种高效的查找树。红黑树的应用很广泛,如Java中的TreeMap、JDK1.8中的HashMap等均是基于红黑树实现的。

二、第三方包redblacktree

1.Dataviz是一个数据结构可视化库,通过对 Graphviz的可视化功能用golang来重新打包,已实现在golang中实现基本数据结构的可视化。实现红黑树的地址:

https://github.com/Arafatk/DataViz/tree/master/trees/redblacktree。

2.源码分析:

(1)红黑树的树中结点:redblacktree.Node。在源码中,结构体Node内部包含存放的结点值Key、Key对应的Value、代表的颜色color、结点索引nodeIndex、左右节点Left或Right、父节点Parent等。

(2)红黑树对象类型:redblacktree.Tree。在源码中,结构体Tree内部包含一个类型为*Node的变量Root、大小size、以及一个用于给Tree中的Key排序的Comparator(比较器)变量。

(3)Comparator类型:func(o1, o2 interface{}) int。在源码中,type Comparator被定义为上述的函数结构。具体的Comparator包括IntComparator和StringComparator。

(4)创建红黑树对象:

  ① redblacktree.NewWith(c Comparator):该方法需要传入一个Comparator对象。

  ② redblacktree.NewWithIntComparator() / redblacktree.NewWithStringComparator() :这类方法可通过特定的Comparator创建红黑树对象。

(5)常用操作:(为便于演示,此处创建Tree对象:tree := redblacktree.NewTree())

  ① 根据key值获取value值:val, b := tree.Get(key)。返回值b为bool类型,表示获取成功或失败;val为tree中结点值为key对应的value值。

  ② 加入键值对key-value:tree.Put(key, value)。

  ③ 获取tree中的结点数目:tree.Size()。返回值为int型。

  ④ 根据key删除某结点:tree.Remove(key)。

  ⑤ 获取tree中最小/最大的key对应的结点:tree.Left()。返回值为Node类型,通过tree.Left().Key可得到该Node对象存放的key值(interface{}类型),若此前定义过Comparator的类型为int或string,可

通过断言获取实际key值:如通过tree.Left().Key.(int)可获取到类型为int的key值,而非interface{}。Left()获取最小key值对应的Node,Right()获取最大key值对应的Node。

  ⑥ 获取tree中小于key的最大key对应的Node:floor, b := tree.Floor()。floor为*Node类型,b为bool类型。

  ⑦ 获取tree中大于key的最小key对应的Node:ceiling, b := tree.Ceiling()。ceiling为*Node类型,b为bool类型。