大家好，我是小小明，今天我将帶大家安裝pygraphviz，并通過它對紅黑樹這種資料結構進行可視化。
pygraphviz的安裝與紅黑樹的可視化
安裝graphviz
下載下傳位址：http://www.graphviz.org/download/
windows平台下可以選擇：
- Stable 2.38 Windows install packages
安裝完成後将bin目錄添加到環境變量中。
驗證安裝：
C:\Users\Administrator>dot -version
dot - graphviz version 2.38.0 (20140413.2041)
libdir = "D:\Program Files (x86)\Graphviz2.38\bin"
Activated plugin library: gvplugin_dot_layout.dll
Using layout: dot:dot_layout
Activated plugin library: gvplugin_core.dll
Using render: dot:core
Using device: dot:dot:core
The plugin configuration file:
D:\Program Files (x86)\Graphviz2.38\bin\config6
was successfully loaded.
render : cairo dot fig gd gdiplus map pic pov ps svg tk vml vrml xdot
layout : circo dot fdp neato nop nop1 nop2 osage patchwork sfdp twopi
textlayout : textlayout
device : bmp canon cmap cmapx cmapx_np dot emf emfplus eps fig gd gd2 gif gv ima
p imap_np ismap jpe jpeg jpg metafile pdf pic plain plain-ext png pov ps ps2 svg svgz tif
tiff tk vml vmlz vrml wbmp xdot xdot1.2 xdot1.4
loadimage : (lib) bmp eps gd gd2 gif jpe jpeg jpg png ps svg 出現類似上面的版本資訊，表示安裝成功。
安裝pygraphviz
下載下傳位址：https://github.com/CristiFati/Prebuilt-Binaries/tree/master/PyGraphviz
從上面位址下載下傳指定python版本的pygraphviz，我下載下傳的是64位系統python3.7版本：
https://github.com/CristiFati/Prebuilt-Binaries/raw/master/PyGraphviz/pygraphviz-1.5-cp37-cp37m-win_amd64.whl
然後在下載下傳目錄中運作以下指令即可安裝成功：
pip install pygraphviz-1.5-cp37-cp37m-win_amd64.whl 紅黑樹的概念
平衡二叉查找樹中“平衡”的意思，其實就是讓整棵樹左右看起來比較“對稱”、比較“平衡”，不要出現左子樹很高、右子樹很矮的情況。這樣就能讓整棵樹的高度相對來說低一些，相應的插入、删除、查找等操作的效率高一些。
平衡二叉查找樹的初衷，是為了解決二叉查找樹因為動态更新導緻的性能退化問題。
紅黑樹（Red-Black Tree，簡稱 R-B Tree）是最常用的平衡二叉查找樹，除此之外平衡二叉查找樹還有Splay Tree（伸展樹）、Treap（樹堆）等。它是一種不嚴格的平衡二叉查找樹，
紅黑樹中的節點，一類被标記為黑色，一類被标記為紅色。
紅黑樹滿足：
- 根節點是黑色的；
- 每個葉子節點都是黑色的空節點（NIL），葉子節點不存儲資料；
- 任何相鄰的節點都不能同時為紅色，紅色節點是被黑色節點隔開的；
- 每個節點，從該節點到達其可達葉子節點的所有路徑都包含相同數目的黑色節點；
如何比較輕松學會紅黑樹：
第一點，把紅黑樹的平衡調整的過程比作魔方複原，不要過于深究這個算法的正确性。隻需要明白，隻要按照固定的操作步驟，保持插入、删除的過程，不破壞平衡樹的定義就行了。
第二點，找準關注節點，不要搞丢、搞錯關注節點。因為每種操作規則，都是基于關注節點來做的，隻有弄對了關注節點，才能對應到正确的操作規則中。在疊代的調整過程中，關注節點在不停地改變，是以，這個過程一定要注意，不要弄丢了關注節點。
第三點，插入操作的平衡調整比較簡單，但是删除操作就比較複雜。針對删除操作，我們有兩次調整，第一次是針對要删除的節點做初步調整，讓調整後的紅黑樹繼續滿足第四條定義，“每個節點到可達葉子節點的路徑都包含相同個數的黑色節點”。但是這個時候，第三條定義就不滿足了，有可能會存在兩個紅色節點相鄰的情況。第二次調整就是解決這個問題，讓紅黑樹不存在相鄰的紅色節點。
紅黑樹的實作代碼（含可視化）
# -*- coding: UTF-8 -*-
from collections import deque
from typing import Optional
import pygraphviz as pgv
class TreeNode:
def __init__(self, data=None, color=None):
self.data = data
assert color in ['r', 'b']
self.color = 'red' if color == 'r' else 'black'
self.left = None
self.right = None
self.parent = None
def is_black(self) -> bool:
return self.color == 'black'
def is_red(self) -> bool:
return self.color == 'red'
def set_black(self):
self.color = 'black'
def set_red(self):
self.color = 'red'
class RedBlackTree:
def __init__(self, val_list=None):
self.tree: Optional[TreeNode] = None
self.black_leaf = TreeNode(color='b') # 共用的黑色葉子節點
if val_list is None:
val_list = []
for n in val_list:
self.insert(n)
def find(self, data) -> Optional[TreeNode]:
if self.tree is None:
return None
p = self.tree
while p != self.black_leaf:
if data < p.data:
p = p.left
elif data > p.data:
p = p.right
else:
return p
return None
def insert(self, data):
new_node = TreeNode(data, 'r') # 新插入的節點為紅色
# 根節點
if self.tree is None:
self.tree = new_node
else:
p = self.tree # 根節點
while p != self.black_leaf: # 黑色葉子節點
pp = p # pp表示插入點的父節點
if data < p.data:
p = p.left
elif data > p.data:
p = p.right
else:
# raise KeyError('val:{} already exists' % data) # 該值已存在，插入失敗
return
if data < pp.data:
pp.left = new_node
else:
pp.right = new_node
new_node.parent = pp
new_node.left = new_node.right = self.black_leaf
# 插入後調整
self._insert_fixup(new_node)
def _insert_fixup(self, node):
n: TreeNode = node # 關注節點
while n != self.tree and n.parent.is_red():
# 父p 叔u 祖父g
p = self.parent(n)
u = self.bro(p)
g = self.parent(p)
if u.is_red(): # case 1 叔叔節點是紅色
p.set_black() # 父節點設定成黑色
u.set_black() # 叔叔節點設定成黑色
g.set_red() # 祖父節點設定成紅色
n = g # 關注節點變成祖父節點
continue
# 往下走，說明叔叔節點是黑色
if p == g.left: # 父節點為祖父節點的左子結點
if n == p.right: # case 2 關注節點是其父節點的右子節點
self.rotate_l(p) # 圍繞關注節點的父節點左旋
n, p = p, n # 左旋後指針交換，關注節點設定為關注節點的父節點
# case 3 關注節點是其父節點的左子節點
p.set_black() # 關注節點的父節點設定為黑色
g.set_red() # 關注節點的祖父節點設定為紅色
self.rotate_r(g) # 圍繞關注節點的祖父節點右旋
else: # 父節點為祖父節點的右子結點
if n == p.left: # case 2 關注節點是其父節點的左子節點
self.rotate_r(p) # 圍繞關注節點的父節點右旋
n, p = p, n # 右旋後指針交換，關注節點設定為關注節點的父節點
# case 3 關注節點是其父節點的右子節點
p.set_black() # 關注節點的父節點設定為黑色
g.set_red() # 關注節點的祖父節點設定為紅色
self.rotate_l(g) # 圍繞關注節點的祖父節點左旋
# 根節點強制置黑，有兩種情況根節點是紅色：
# 1. 新插入時是紅色
# 2. 經過case 1調整過後變紅色
self.tree.color = 'black'
def delete(self, data):
n: TreeNode = self.find(data)
if n is None:
return
# n的子節點個數等于2
if self.children_count(n) == 2:
# 尋找n的後繼s
s = n.right
while s.left != self.black_leaf:
s = s.left
n.data = s.data
# 将删除n轉化為删除s
n = s
# n的子節點個數小于2
if n.left == self.black_leaf:
c = n.right
else:
c = n.left
self._transplant(n, c)
# 删除的節點是黑色，需要調整
if n.is_black():
self._delete_fixup(c)
return
def _delete_fixup(self, node):
n = node
while n != self.tree and n.is_black():
p = self.parent(n)
b = self.bro(n)
# 左右節點對稱
if p.left == n:
if not b.is_black():
b.set_black() # case 1
p.set_red() # case 1
self.rotate_l(p) # case 1
# new bro after rotate
b = self.bro(n) # case 1
if b.left.is_black() and b.right.is_black():
b.set_red() # case 2
n = p # case 2
else:
if b.right.is_black():
b.left.set_black() # case 3
b.set_red() # case 3
self.rotate_r(b) # case 3
# new bro after rotate
b = self.bro(n) # case 3
# 注意，因為p可能是紅或黑，是以不能直接指派顔色，隻能copy
b.color = p.color # case 4
p.set_black() # case 4
b.right.set_black() # case 4
self.rotate_l(p) # case 4
# trick, 調整結束跳出while
n = self.tree # case 4
else:
if not b.is_black():
b.set_black() # case 1
p.set_red() # case 1
self.rotate_r(p) # case 1
# new bro after rotate
b = self.bro(n) # case 1
if b.left.is_black() and b.right.is_black():
b.set_red() # case 2
n = p # case 2
else:
if b.left.is_black():
b.right.set_black() # case 3
b.set_red() # case 3
self.rotate_l(b) # case 3
# new bro after rotate
b = self.bro(n) # case 3
# 注意，因為p可能是紅或黑，是以不能直接指派顔色，隻能copy
b.color = p.color # case 4
p.set_black() # case 4
b.left.set_black() # case 4
self.rotate_r(p) # case 4
# trick, 調整結束跳出while
n = self.tree # case 4
# 将n設為黑色，從上面while循環跳出，情況有兩種
# 1. n是根節點，直接無視附加的黑色
# 2. n是紅色的節點，則染黑
n.set_black()
def _transplant(self, n1, n2):
"""
節點移植， n2 -> n1
:param n1: 原節點
:param n2: 移植節點
:return:
"""
if n1 == self.tree:
if n2 != self.black_leaf:
self.tree = n2
n2.parent = None
else:
self.tree = None # 隻有删除根節點時會進來
else:
p = self.parent(n1)
if p.left == n1:
p.left = n2
else:
p.right = n2
n2.parent = p
def rotate_l(self, node):
if node is None:
return
if node.right is self.black_leaf:
return
p = self.parent(node)
x = node
y = node.right
# node為根節點時，p為None，旋轉後要更新根節點指向
if p is not None:
if x == p.left:
p.left = y
else:
p.right = y
else:
self.tree = y
x.parent, y.parent = y, p
if y.left != self.black_leaf:
y.left.parent = x
x.right, y.left = y.left, x
def rotate_r(self, node):
if node is None:
return
if node.left is self.black_leaf:
return
p = self.parent(node)
x = node
y = node.left
# 同左旋
if p is not None:
if x == p.left:
p.left = y
else:
p.right = y
else:
self.tree = y
x.parent, y.parent = y, p
if y.right is not None:
y.right.parent = x
x.left, y.right = y.right, x
@staticmethod
def bro(node):
"""
擷取兄弟節點
"""
if node is None or node.parent is None:
return None
else:
p = node.parent
if node == p.left:
return p.right
else:
return p.left
@staticmethod
def parent(node):
"""
擷取父節點
"""
if node is None:
return None
else:
return node.parent
def children_count(self, node):
"""
擷取子節點個數
"""
return 2 - [node.left, node.right].count(self.black_leaf)
def draw_img(self, img_name='Red_Black_Tree.png'):
"""用pygraphviz畫紅黑樹"""
if self.tree is None:
return
tree = pgv.AGraph(directed=True, strict=True)
queue = deque([self.tree])
num = 0
while queue:
e = queue.popleft()
if e != self.black_leaf: # 黑色葉子的連線由各個節點自己畫
tree.add_node(e.data, color=e.color, fontcolor="white", style="filled",
fontname="Microsoft YaHei", shape="circle", margin=0)
for c in [e.left, e.right]:
queue.append(c)
if c != self.black_leaf:
tree.add_edge(e.data, c.data, color="blue")
else:
num += 1
tree.add_node("nil%s" % num, label="Nil", color="black", fontcolor="white", style="filled",
fontname="Microsoft YaHei", shape="circle", margin=0)
tree.add_edge(e.data, "nil%s" % num, color="blue")
tree.graph_attr['epsilon'] = '0.01'
tree.layout('dot')
tree.draw(img_name)
if __name__ == '__main__':
rbt = RedBlackTree()
nums = list(range(1, 20))
for num in nums:
rbt.insert(num)
search_num = 7
n = rbt.find(search_num)
if n:
print(n.data)
else:
print('node {} not found'.format(search_num))
rbt.delete(4)
rbt.draw_img() ![前端js——擷取元素的各級節點、子節點、父級節點[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)