如何使用 go 實(shí)現(xiàn)紅黑樹

本文介紹了使用 go 實(shí)現(xiàn)紅黑樹。

二叉搜索樹（二叉查找樹）

二叉查找樹也叫二叉搜索樹，也叫二叉排序樹，它具有以下特點(diǎn)：1. 如果左子樹不為空，則左子樹上的結(jié)點(diǎn)的值都小于根節(jié)點(diǎn)；2. 如果右子樹不為空，則右子樹上的結(jié)點(diǎn)的值都大于根節(jié)點(diǎn)；3. 子樹同樣也要遵循以上兩點(diǎn)。

二叉樹的遍歷方式

二叉樹的遍歷方式：前序遍歷、中序遍歷、后序遍歷和層序遍歷（MySql）。

只要一棵樹是二叉查找樹，那么它的中序遍歷（左根右輸出）一定是有序的。比如看下邊的一棵二叉樹：

它的前序遍歷（根左右）為：530468；
它的中序遍歷（左根右）為：034568；
它的后序遍歷（左右根）為：043865。

二叉搜索樹有哪些應(yīng)用？

既然是搜索樹，那么它肯定就是用在查找上。我們來分析下它的查找時(shí)間復(fù)雜度：

先來看下面兩顆二叉搜索樹：

查找時(shí)間復(fù)雜度其實(shí)就是樹的深度。

上圖一的時(shí)間復(fù)雜度：O(n)時(shí)間復(fù)雜度，表示需要查找 n 次，即循環(huán) n 遍，退化成鏈表的情況。

上圖二的時(shí)間復(fù)雜度（類似二分查找）：logn，即 => x= => logn。

那么為什么會出現(xiàn)退化成鏈表的情況（圖一）呢？我們該怎么處理才不會變成鏈表呢（怎么解決）？

當(dāng)插入的節(jié)點(diǎn)數(shù)值從小到大時(shí)，則就會出現(xiàn)二叉樹退化成鏈表的情況，那么有另一種樹可以解決這種情況，就是平衡二叉樹（AVL樹）。

AVL樹是一種追求極致平衡的二叉搜索樹，即將樹調(diào)整到最優(yōu)的情況，由于這種樹結(jié)構(gòu)比較苛刻、旋轉(zhuǎn)也比較多，這里就不重點(diǎn)展開講。

紅黑樹

紅黑樹的由來

今天需要重點(diǎn)講的是紅黑樹。紅黑樹的底層數(shù)據(jù)結(jié)構(gòu)其實(shí)就是二叉查找樹，也就是說紅黑樹是一顆特殊的二叉查找樹，也叫自平衡二叉查找樹。

紅黑樹出現(xiàn)的目的就是上所講到的，為了解決二叉樹退化成鏈表的情況。

紅黑樹的演進(jìn)過程

鏈表(暴力查處) -> 二叉樹 -> 二叉查找樹 -> 特殊的二叉查找樹(自平衡的二叉查找樹)

紅黑色講解

通過上面的例子以及兩個(gè)圖，我們發(fā)現(xiàn)二叉樹的結(jié)構(gòu)就決定了其搜索的效率及性能，那么我們需要怎么樣才讓二叉樹達(dá)到優(yōu)化的效果呢？

因此就有了紅黑樹了，我們看下圖（紅黑樹）：

紅黑樹的性質(zhì)：

每個(gè)節(jié)點(diǎn)不是紅色就是黑色（這里不一定要紅色和黑色，只要知道這里的紅色和黑色是什么意思即可）

一定沒有連在一起的紅色節(jié)點(diǎn)

根節(jié)點(diǎn)（第一個(gè)節(jié)點(diǎn)）是黑色 root

每個(gè)紅色節(jié)點(diǎn)的兩個(gè)字節(jié)點(diǎn)都是黑色

葉子結(jié)點(diǎn)都是黑色（上圖中其實(shí)還有為null的葉子結(jié)點(diǎn)沒有畫出來），如下圖所示：

根據(jù)以上性質(zhì)或者說滿足了以上性質(zhì)的樹，就可以達(dá)到近似平衡了。

怎么判斷一個(gè)節(jié)點(diǎn)是否為根結(jié)點(diǎn)？

沒有父節(jié)點(diǎn)

入度為0的節(jié)點(diǎn)

紅黑樹變換規(guī)則

要滿足這些性質(zhì)，需要對樹做什么操作呢？

為了紅黑可以滿足這些性質(zhì)，因此出現(xiàn)了旋轉(zhuǎn)，那么紅黑樹有幾種變換規(guī)則呢？

有三種變換規(guī)則：

變色：紅變黑 黑變紅

左旋轉(zhuǎn)

右旋轉(zhuǎn)

左旋轉(zhuǎn)示例：

旋轉(zhuǎn)和顏色變換規(guī)則：所有插入的點(diǎn)默認(rèn)為紅色； 1. 變顏色的情況：如果插入的節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)為紅色，則：1）把父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)設(shè)為黑色；2）把爺爺(祖父)節(jié)點(diǎn)設(shè)為紅色；3）把指針定位到爺爺節(jié)點(diǎn)作為當(dāng)前需要操作的節(jié)點(diǎn)，再根據(jù)變換規(guī)則來進(jìn)行判斷操作。2. 左旋：如果當(dāng)前父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，而且當(dāng)前的節(jié)點(diǎn)是右子樹時(shí)，則需要以父節(jié)點(diǎn)作為左旋轉(zhuǎn)。3. 右旋：當(dāng)前父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前的節(jié)點(diǎn)是左子樹時(shí)，則：1）把父節(jié)點(diǎn)變?yōu)楹谏?）把爺爺節(jié)點(diǎn)變?yōu)榧t色；3）以父節(jié)點(diǎn)右旋轉(zhuǎn)。

比如要往上圖中插入數(shù)字6，則這顆紅黑色的演變過程如下：

step1: 插入6節(jié)點(diǎn)后如下圖，它的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)均是紅色，則需要根據(jù)變換規(guī)則來操作，到step2了。

step2: 根據(jù)變換規(guī)則，需要將插入節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)均變?yōu)楹谏瑺敔敼?jié)點(diǎn)變?yōu)榧t色，然后將指針定位到爺爺節(jié)點(diǎn)(藍(lán)色圈)。將指針定位到爺爺節(jié)點(diǎn)(12)后，此時(shí)做為當(dāng)前需要操作的節(jié)點(diǎn)，再根據(jù)變換規(guī)則來判斷，可以看到下圖的當(dāng)前節(jié)點(diǎn)(12)的叔叔節(jié)點(diǎn)是黑色的，則不能用變顏色規(guī)則的情況了，進(jìn)行step3，此時(shí)需要進(jìn)行左旋或右旋了。

step3: 根據(jù)上圖情況可以知道此時(shí)是符合左旋規(guī)則的：當(dāng)前節(jié)點(diǎn)(12)的父節(jié)點(diǎn)(5)是紅色，叔叔節(jié)點(diǎn)(3)是黑色，而且當(dāng)前的節(jié)點(diǎn)是右子樹。接下來需要進(jìn)行左旋變換(三步走)：

step4：左旋變換后，可以看到當(dāng)前節(jié)點(diǎn)(5)的父節(jié)點(diǎn)(12)為紅色，叔叔節(jié)點(diǎn)(30)為黑色，而且當(dāng)前節(jié)點(diǎn)為左子樹，符合右旋的規(guī)則。接下來就是進(jìn)行右旋的變換操作了：1）把父節(jié)點(diǎn)(12)變?yōu)楹谏?）把爺爺節(jié)點(diǎn)(29)變?yōu)榧t色；3）以父節(jié)點(diǎn)(12)右旋轉(zhuǎn)

小結(jié)

到這里，可以看到經(jīng)過多次旋轉(zhuǎn)后，這棵樹是符合紅黑色的性質(zhì)。

Golang代碼實(shí)現(xiàn)紅黑樹

直接上代碼，如下：

packagemain

import(
"fmt"
"math/rand"
"time"
)

const(
REDbool=true
BLACKbool=false
)

typeNodestruct{
keyint
valueinterface{}

left*Node
right*Node
//parent*Node

colorbool
}

typeRedBlackTreestruct{
sizeint
root*Node
}

funcNewNode(key,valint)*Node{
//默認(rèn)添加紅節(jié)點(diǎn)
return&Node{
key:key,
value:val,
left:nil,
right:nil,
//parent:nil,
color:RED,
}
}

funcNewRedBlackTree()*RedBlackTree{
return&RedBlackTree{}
}

func(n*Node)IsRed()bool{
ifn==nil{
returnBLACK
}
returnn.color
}

func(tree*RedBlackTree)GetTreeSize()int{
returntree.size
}

//nodex
///左旋轉(zhuǎn)/
//T1x--------->nodeT3
////
//T2T3T1T2
func(n*Node)leftRotate()*Node{
//左旋轉(zhuǎn)
retNode:=n.right
n.right=retNode.left

retNode.left=n
retNode.color=n.color
n.color=RED

returnretNode
}

//nodex
///右旋轉(zhuǎn)/
//xT2------->ynode
////
//yT1T1T2
func(n*Node)rightRotate()*Node{
//右旋轉(zhuǎn)
retNode:=n.left
n.left=retNode.right

retNode.right=n
retNode.color=n.color
n.color=RED

returnretNode
}

//顏色變換
func(n*Node)flipColors(){
n.color=RED
n.left.color=BLACK
n.right.color=BLACK
}

//維護(hù)紅黑樹
func(n*Node)updateRedBlackTree(isAddint)*Node{
//isAdd=0說明沒有新節(jié)點(diǎn)，無需維護(hù)
ifisAdd==0{
returnn
}

//需要維護(hù)
ifn.right.IsRed()==RED&&n.left.IsRed()!=RED{
n=n.leftRotate()
}

//判斷是否為情形3，是需要右旋轉(zhuǎn)
ifn.left.IsRed()==RED&&n.left.left.IsRed()==RED{
n=n.rightRotate()
}

//判斷是否為情形4，是需要顏色翻轉(zhuǎn)
ifn.left.IsRed()==RED&&n.right.IsRed()==RED{
n.flipColors()
}

returnn
}

//遞歸寫法:向樹的root節(jié)點(diǎn)中插入key,val
//返回1,代表加了節(jié)點(diǎn)
//返回0,代表沒有添加新節(jié)點(diǎn),只更新key對應(yīng)的value值
func(n*Node)add(key,valint)(int,*Node){
ifn==nil{//默認(rèn)插入紅色節(jié)點(diǎn)
return1,NewNode(key,val)
}

isAdd:=0
ifkeyn.key{
isAdd,n.right=n.right.add(key,val)
}else{
//對value值更新,節(jié)點(diǎn)數(shù)量不增加,isAdd=0
n.value=val
}

//維護(hù)紅黑樹
n=n.updateRedBlackTree(isAdd)

returnisAdd,n
}

func(tree*RedBlackTree)Add(key,valint){
isAdd,nd:=tree.root.add(key,val)
tree.size+=isAdd
tree.root=nd
tree.root.color=BLACK//根節(jié)點(diǎn)為黑色節(jié)點(diǎn)
}

//前序遍歷打印出key,val,color
func(tree*RedBlackTree)PrintPreOrder(){
resp:=make([][]interface{},0)
tree.root.printPreOrder(&resp)
fmt.Println(resp)
}

func(n*Node)printPreOrder(resp*[][]interface{}){
ifn==nil{
return
}
*resp=append(*resp,[]interface{}{n.key,n.value,n.color})
n.left.printPreOrder(resp)
n.right.printPreOrder(resp)
}


//測試紅黑樹代碼
funcmain(){
count:=10
redBlackTree:=NewRedBlackTree()
nums:=make([]int,0)
fori:=0;i

	

	測試輸出結(jié)果如下：

	
datasource:[1779185060]
redBlackTree:-2.136μs
[[77false][11true][00false][66false][55true][99false][88true]]
節(jié)點(diǎn)數(shù)量:7


	

	總結(jié)

	紅黑樹是保持近似平衡的二叉樹，從另一種角度上來說紅黑樹不是平衡二叉樹，它的最大高度為2*logn。

	二分搜索樹，AVL樹，紅黑樹對比：1. 對于完全隨機(jī)的數(shù)據(jù)源，普通二分搜索樹很好用，缺陷是在極端情況下容易退化成鏈表 2. 對于查詢較多的使用情況，AVL樹很好用，因?yàn)樗母叨纫恢北３謍=logn 3. 紅黑樹犧牲了平衡性，即h=2*logn，但在添加和刪除操作中，紅黑樹比AVL樹有優(yōu)勢 4. 綜合增刪改查所有操作，紅黑樹的統(tǒng)計(jì)性能更優(yōu)

	原文標(biāo)題：二叉樹、紅黑樹以及Golang實(shí)現(xiàn)紅黑樹

	文章出處：【微信公眾號：Linux愛好者】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

	審核編輯：彭菁