大家好，我是小小明，今天我将带大家安装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\config6was successfully loaded.render      :  cairo dot fig gd gdiplus map pic pov ps svg tk vml vrml xdotlayout      :  circo dot fdp neato nop nop1 nop2 osage patchwork sfdp twopitextlayout  :  textlayoutdevice      :  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.4loadimage   :  (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 Optionalimport pygraphviz as pgvclass TreeNode:def __init__(self, data=None, color=None):self.data = dataassert color in ['r', 'b']self.color = 'red' if color == 'r' else 'black'self.left = Noneself.right = Noneself.parent = Nonedef 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] = Noneself.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 Nonep = self.treewhile p != self.black_leaf:if data < p.data:p = p.leftelif data > p.data:p = p.rightelse:return preturn Nonedef insert(self, data):new_node = TreeNode(data, 'r')  # 新插入的节点为红色# 根节点if self.tree is None:self.tree = new_nodeelse:p = self.tree  # 根节点while p != self.black_leaf:  # 黑色叶子节点pp = p  # pp表示插入点的父节点if data < p.data:p = p.leftelif data > p.data:p = p.rightelse:# raise KeyError('val:{} already exists' % data)  # 该值已存在，插入失败returnif data < pp.data:pp.left = new_nodeelse:pp.right = new_nodenew_node.parent = ppnew_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 祖父gp = 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的子节点个数等于2if self.children_count(n) == 2:# 寻找n的后继ss = n.rightwhile s.left != self.black_leaf:s = s.leftn.data = s.data# 将删除n转化为删除sn = s# n的子节点个数小于2if n.left == self.black_leaf:c = n.rightelse:c = n.leftself._transplant(n, c)# 删除的节点是黑色，需要调整if n.is_black():self._delete_fixup(c)returndef _delete_fixup(self, node):n = nodewhile 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 1p.set_red()  # case 1self.rotate_l(p)  # case 1# new bro after rotateb = self.bro(n)  # case 1if b.left.is_black() and b.right.is_black():b.set_red()  # case 2n = p  # case 2else:if b.right.is_black():b.left.set_black()  # case 3b.set_red()  # case 3self.rotate_r(b)  # case 3# new bro after rotateb = self.bro(n)  # case 3# 注意，因为p可能是红或黑，所以不能直接赋值颜色，只能copyb.color = p.color  # case 4p.set_black()  # case 4b.right.set_black()  # case 4self.rotate_l(p)  # case 4# trick, 调整结束跳出whilen = self.tree  # case 4else:if not b.is_black():b.set_black()  # case 1p.set_red()  # case 1self.rotate_r(p)  # case 1# new bro after rotateb = self.bro(n)  # case 1if b.left.is_black() and b.right.is_black():b.set_red()  # case 2n = p  # case 2else:if b.left.is_black():b.right.set_black()  # case 3b.set_red()  # case 3self.rotate_l(b)  # case 3# new bro after rotateb = self.bro(n)  # case 3# 注意，因为p可能是红或黑，所以不能直接赋值颜色，只能copyb.color = p.color  # case 4p.set_black()  # case 4b.left.set_black()  # case 4self.rotate_r(p)  # case 4# trick, 调整结束跳出whilen = 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 = n2n2.parent = Noneelse:self.tree = None  # 只有删除根节点时会进来else:p = self.parent(n1)if p.left == n1:p.left = n2else:p.right = n2n2.parent = pdef rotate_l(self, node):if node is None:returnif node.right is self.black_leaf:returnp = self.parent(node)x = nodey = node.right# node为根节点时，p为None，旋转后要更新根节点指向if p is not None:if x == p.left:p.left = yelse:p.right = yelse:self.tree = yx.parent, y.parent = y, pif y.left != self.black_leaf:y.left.parent = xx.right, y.left = y.left, xdef rotate_r(self, node):if node is None:returnif node.left is self.black_leaf:returnp = self.parent(node)x = nodey = node.left# 同左旋if p is not None:if x == p.left:p.left = yelse:p.right = yelse:self.tree = yx.parent, y.parent = y, pif y.right is not None:y.right.parent = xx.left, y.right = y.right, x@staticmethoddef bro(node):"""获取兄弟节点"""if node is None or node.parent is None:return Noneelse:p = node.parentif node == p.left:return p.rightelse:return p.left@staticmethoddef parent(node):"""获取父节点"""if node is None:return Noneelse:return node.parentdef 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:returntree = pgv.AGraph(directed=True, strict=True)queue = deque([self.tree])num = 0while 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 += 1tree.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 = 7n = rbt.find(search_num)if n:print(n.data)else:print('node {} not found'.format(search_num))rbt.delete(4)rbt.draw_img()

红黑树可视化效果

至此我们就完成了红黑树的可视化。