继上一篇《（23）Go实现红黑树-算法解析》的续：
https://www.jianshu.com/p/8c41d1e52c32
红黑树的定义和实现
const (
Red = true
Black = false
)
type node struct {
key int
value int
color bool
left *node
right *node
}
type redBlackTree struct {
size int
root *node
}
func newNode(key, val int) *node {
// 默认添加红节点
return &node{key, val, Red, nil, nil}
}
func NewRedBlackTree() *redBlackTree {
return new(redBlackTree)
}
func (nd *node) isRed() bool {
if nd == nil {
return Black
}
return nd.color
}
func (tree *redBlackTree) GetSize() int {
return tree.size
}
// 向红黑树中添加元素
func (tree *redBlackTree) Add(key, val int) {
isAdd, nd := tree.root.add(key, val)
tree.size += isAdd
tree.root = nd
tree.root.color = Black //根节点为黑色节点
}
// 递归写法:向树的root节点中插入key,val
// 返回1,代表加了节点
// 返回0,代表没有添加新节点,只更新key对应的value值
func (nd *node) add(key, val int) (int, *node) {
if nd == nil { // 默认插入红色节点
return 1, newNode(key, val)
}
isAdd := 0
if key < nd.key {
isAdd, nd.left = nd.left.add(key, val)
} else if key > nd.key {
isAdd, nd.right = nd.right.add(key, val)
} else { // nd.key == key
// 对value值更新,节点数量不增加,isAdd = 0
nd.value = val
}
// 维护红黑树
nd = nd.updateRedBlackTree(isAdd)
return isAdd, nd
}
// 红黑树维护
func (nd *node) updateRedBlackTree(isChange int) *node {
// 0说明无新节点,不必更新
if isChange == 0 {
return nd
}
// 维护
if nd.right.isRed() == Red && nd.left.isRed() != Red {
nd = nd.leftRotate()
}
if nd.left.isRed() == Red && nd.left.left.isRed() == Red {
nd = nd.rightRotate()
}
if nd.left.isRed() == Red && nd.right.isRed() == Red {
nd.flipColors()
}
return nd
}
// nd x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
func (nd *node) leftRotate() *node {
// 左旋转
retNode := nd.right
nd.right = retNode.left
retNode.left = nd
retNode.color = nd.color
nd.color = Red
return retNode
}
// nd x
// / \ 右旋转 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
func (nd *node) rightRotate() *node {
//右旋转
retNode := nd.left
nd.left = retNode.right
retNode.right = nd
retNode.color = nd.color
nd.color = Red
return retNode
}
// 颜色翻转
func (nd *node) flipColors() {
nd.color = Red
nd.left.color = Black
nd.right.color = Black
}
// 前序遍历打印出key,val,color
func (tree *redBlackTree) PrintPreOrder() {
resp := [][]interface{}{}
tree.root.printPreOrder(&resp)
fmt.Println(resp)
}
func (nd *node) printPreOrder(resp *[][]interface{}) {
if nd == nil {
return
}
*resp = append(*resp, []interface{}{nd.key, nd.value, nd.color})
nd.left.printPreOrder(resp)
nd.right.printPreOrder(resp)
}
测试代码
func main() {
const count = 10
redBlackTree := redblacktree1.NewRedBlackTree()
nums := []int{}
for i := 0; i < count; i++ {
nums = append(nums, rand.Intn(count))
}
fmt.Println("数据源:", nums)
t := time.Now()
for _, v := range nums {
redBlackTree.Add(v, v)
}
fmt.Println("redBlackTree:", t.Sub(time.Now()))
redBlackTree.PrintPreOrder()
fmt.Println("节点数量:", redBlackTree.GetSize())
}
测试结果
数据源: [1 7 7 9 1 8 5 0 6 0]
redBlackTree: -3.294µs
[[7 7 false] [1 1 true] [0 0 false] [6 6 false] [5 5 true] [9 9 false] [8 8 true]]
节点数量: 7
红黑树是保持“黑平衡”的二叉树，严格意义上讲红黑树不是平衡二叉树，他的最大高度为2*logn
二分搜索树，AVL树，红黑树对比：
1）对于完全随机的数据源，普通二分搜索树很好用，缺陷是在极端情况下容易退化成链表
2）对于查询较多的使用情况，AVL树很好用，因为他的高度一直保持h=logn
3）红黑树牺牲了平衡性，即h=2*logn，但在添加和删除操作中，红黑树比AVL树有优势
4）综合增删改查所有操作，红黑树的统计性能更优
红黑树和go自带map性能对比
const count = 1000000
redBlackTree := redblacktree1.NewRedBlackTree()
nums := []int{}
for i := 0; i < count; i++ {
nums = append(nums, rand.Intn(count))
}
t := time.Now()
for _, v := range nums {
redBlackTree.Add(v, v)
}
fmt.Println("redBlackTree:", t.Sub(time.Now()))
m := map[int]int{}
t = time.Now()
for _, v := range nums {
m[v] = v
}
fmt.Println("map:", t.Sub(time.Now()))
测试结果//
redBlackTree: -2.859348172s
map: -673.106001ms
map在速度上还是很大优势，劣势就是无法顺序遍历。
一种数据结构在某方面性能更优，往往是因为他多维护或少维护了某些东西，
如哈希表和红黑树对比，哈希表牺牲了顺序，赢得了速度，而红黑树赢了顺序，输了速度。
不存在说一定要使用某种数据结构，要具体问题具体分析。
有bug欢迎支持，转载请注明出处。
网友评论