利用 graphviz 输出红黑树

瞳人


发布于 Feb. 17, 2017, 6:06 p.m.

0 个评论

Algorithm Python


因为当时没有好好学算法,所以现在开始补习算法。看到红黑树的时候,觉得可视化红黑树能够帮助我们更直观地了解其结构,于是在网上搜索之后,发现可以使用 graphviz 配合python 接口 pygraphviz 来实现。

安装

需要注意,使用 brew 安装 graphviz 之后,需要对 pip 指定参数来安装 pygraphvix

1
2
brew install graphviz
pip install --install-option="--include-path=/usr/local/include/" --install-option="--library-path=/usr/local/lib/" pygraphviz

代码

红黑树代码略。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# coding=utf-8
import pygraphviz as pgv
import itertools

class Node:
    def __init__(self, key=None, left=None, right=None, parent=None, color=RED):
        self.key = key
        self.left = left
        self.right = right
        self.parent = parent
        self.color = color

NIL = Node(color=BLACK)

class Tree:
    def __init__(self):
        self.nil = NIL
        self.root = NIL

    # other methods are omitted ...

    def draw(self, filename='tree.png', draw_nil=0):
        if self.root == self.nil:
            return
        graph = pgv.AGraph(strict=False, directed=True)
        graph.node_attr.update({
            'shape':     'circle',
            'style':     'filled',
            'fontcolor': 'white',
        })
        graph.add_node(self.root.key, color=self.root.color)
        if draw_nil == 0:
            self.draw_subtree(self.root, graph)
        elif draw_nil == 1:
            # use one nil node for leaves and parent of root
            graph.add_node('nil1', color='black', label='nil')
            graph.add_edge('nil1', self.root.key)
            self.draw_subtree(self.root, graph, draw_nil)
        else:
            # use different nil nodes for leaves and parent of root
            graph.add_node('nil1', color='black', label='nil')
            graph.add_edge('nil1', self.root.key)
            self.draw_subtree(self.root, graph, draw_nil, counter=itertools.count(2))
        # print(graph.string())
        graph.draw(filename, prog='dot')

    def draw_subtree(self, node, graph, draw_nil=0, counter=None):
        if node == self.nil:
            return
        if node.left != self.nil:
            graph.add_node(node.left.key, color=node.left.color)
            graph.add_edge(node.key, node.left.key, tailport='sw')
            self.draw_subtree(node.left, graph, draw_nil, counter)
        elif draw_nil == 1:
            graph.add_edge(node.key, 'nil1', tailport='sw')
        elif draw_nil == 2 and counter is not None:
            nil_id = 'nil%d' % next(counter)
            graph.add_node(nil_id, color='black', label='nil')
            graph.add_edge(node.key, nil_id, tailport='sw')

        if node.right != self.nil:
            graph.add_node(node.right.key, color=node.right.color)
            graph.add_edge(node.key, node.right.key, tailport='se')
            self.draw_subtree(node.right, graph, draw_nil, counter)
        elif draw_nil == 1:
            graph.add_edge(node.key, 'nil1', tailport='se')
        elif draw_nil == 2 and counter is not None:
            nil_id = 'nil%d' % next(counter)
            graph.add_node(nil_id, color='black', label='nil')
            graph.add_edge(node.key, nil_id, tailport='se')


if __name__ == '__main__':
    tree = Tree()
    values = [41, 38, 31, 12, 19, 8]
    for x in values:
        tree.rb_insert(Node(x))
    tree.draw(filename='tree_nil_0.png', draw_nil=0)
    tree.draw(filename='tree_nil_1.png', draw_nil=1)
    tree.draw(filename='tree_nil_2.png', draw_nil=2)

draw 方法的 draw_nil 参数默认为 0(不画 nil 结点),设置为 1 则叶子和根父亲共用一个 nil 结点,其他值则叶子和根父亲有各自的 nil 结点。下图分别为上述代码执行后的 tree_nil_0.png,tree_nil_1.png 和 tree_nil_2.png。

不画 nil 结点的红黑树

共用一个 nil 结点的红黑树

具有单独 nil 结点的红黑树

参考链接

  1. 二叉树可视化--Graphviz
  2. Cannot install pygraphviz on Mac OS 10.11.6
  3. Node, Edge and Graph Attributes

哎呦, 不错哦!

0 Comments


Leave a Comment:

博客搜索

友情链接

公告

本博客代码已经公布在 Github 上,欢迎交流指正。

QQ 邮箱对 mailgun 不太友好, 所以使用 QQ 邮箱的评论, 可能会无法及时收到邮件。我会尽快寻找其他解决方案的。

本人现在独自使用 linode vps, 20 美元/月, 感觉压力大, 如果有意一起合租, 可以联系我. 在我的任意一篇文章下面留言即可. 关于使用方式, 现在倾向于使用 docker.