起因

之前用 Rust 写了一个 AVL 树的实现，就很自然的想把树用可视化的图像画出来，在一波搜索过后，最后都指向了一位叫 Emden Gansner（ Graphviz 主要贡献者之一） 的大佬在 2010 年写的一段脚本，原作者是在邮件列表（链接1，链接2）中回复别人的问题时提供的这段脚本，由于这个邮件列表原来的存档网站已经无法访问，现在能搜到的基本上都是别人对这段脚本引用，比如： stackoverflow。

不过这个 gvpr 我实在是看不懂，所以我希望能够直接使用 dot 来绘制二叉树，这样在生成图像的时候就只需要使用 dot 命令行工具而不需要额外的脚本了。

尝试

但是事情看起来并没有那么简单，假如我们现在有一个文件 tree.dot：

digraph G {
    node [shape=circle]
    edge [arrowhead=vee]
    8 -> 4
    4 -> 2
    2 -> 1
    2 -> 3
    4 -> 6
    6 -> 5
    6 -> 7
    8 -> 10
    10 -> 9
    10 -> 12
    12 -> 11
}

- 阅读剩余部分 -

什么是 AVL 树以及 AVL 树的一些原理就不介绍了，我们直接讲如何用 Rust 来实现它。

结构体及 trait 定义

参考一般 AVL 树的实现，我定义了一个结构体 TreeNode 以及一个类型别名 AvlTreeNode：

pub type AvlTreeNode<T> = Option<Box<TreeNode<T>>>;

#[derive(Clone, Debug)]
pub struct TreeNode<T: PartialOrd> {
    val: T,
    height: i32,
    left: AvlTreeNode<T>,
    right: AvlTreeNode<T>,
}

使用类型别名可以了少打几个字母以及好看一点。

还定义了一个 trait AvlTree：

pub trait AvlTree<T: PartialOrd> {
    fn new(val: T) -> Self;
    fn height(&self) -> i32;
    fn insert(&mut self, val: T);
    fn delete(&mut self, val: T) -> Self;
}

- 阅读剩余部分 -

假设已经安装了 Rust 的工具链。

添加 x86_64-pc-windows-gnu target：

rustup target add x86_64-pc-windows-gnu

安装 mingw-w64 工具链：

pacman -S mingw-w64-crt mingw-w64-binutils mingw-w64-winpthreads mingw-w64-headers mingw-w64-gcc

设置链接器

在 ~/.cargo/config 中加入以下内容：

[target.x86_64-pc-windows-gnu]
linker = "x86_64-w64-mingw32-gcc"

[target.i686-pc-windows-gnu]
linker = "i686-w64-mingw32-gcc"

- 阅读剩余部分 -

例如我们想检出 https://github.com/openwrt/packages 项目下的 net/nginx 子目录，但是不想把整个项目克隆下来。

可以利用 svn 来实现， svn 支持 --depth 选项，具体有 empty/files/immediates/infinity 四种参数，含义如下：

      depth-empty ------>  Updates will not pull in any files or
                           subdirectories not already present.
   
      depth-files ------>  Updates will pull in any files not already
                           present, but not subdirectories.
   
      depth-immediates ->  Updates will pull in any files or
                           subdirectories not already present; those
                           subdirectories' this_dir entries will
                           have depth-empty.
   
      depth-infinity --->  Updates will pull in any files or
                           subdirectories not already present; those
                           subdirectories' this_dir entries will
                           have depth-infinity.  Equivalent to
                           today's default update behavior.

1) 检出项目

svn co --depth=empty https://github.com/openwrt/packages/trunk packages

- 阅读剩余部分 -

CRC 算法原理

CRC 算法的基本原理是将数据看作一个大数，与一个预定义的除数使用特殊的除法相除，所得的余数即为数据的 CRC 校验值。

生成多项式

算法的数学原理与多项式相关，用到的除法也基于多项式除法，预定义的除数也叫“生成多项式”，这里的多项式都是只有一个未知数并且各项系数只能是 0 或 1 的多项式（更多的信息可以参考维基百科：有限域算术，这里不多讲）。

我们以 CRC-4/ITU 为例，其生成多项式是 $x^4 + x + 1$，也即:

$$1x^4 + 0x^3 + 0x^2 + 1x^1 + 1x^0$$

如果我们令 $x = 2$，则多项式中每一项的系数可以看作一个二进制数的对应位，即 $(10011)_2$，是一个 5 位的二进制数，那么用它来做除数，最后可以得到 4 位的余数，也就是 CRC-4/ITU 中的 4。由此可见，生成多项式的首位必然是 1，在一般表示生成多项式的时候我们都省略最高位，再写成十六进制就是 0x03。

模二多项式除法

我们先看多项式乘法：

$$ (x^4 + x^1 + x^0) \times (x^4 + x^3 + x^0) = x^8 + x^7 + x^4 + x^5 + x^4 + x^1 + x^4 + x^3 + x^0 $$

这里我们没有合并同类项，如果按照常规的方式合并同类项，即

$$ x^8 + x^7 + x^5 + 3x^4 + x^3 + x^1 + x^0 $$

那就是普通的多项式乘法；对于 CRC 算法，加减法采用模二运算，也就是最后的系数除以 2 取余数，不产生进位，所以最后的结果是：

$$ x^8 + x^7 + x^5 + x^4 + x^3 + x^1 + x^0 $$

- 阅读剩余部分 -