发表于 | 更新于

发表于 | 更新于

不要用手机点哦…

发表于 | 更新于

但是进度有点慢，我应该打住了，先写一点别的。现在应该可以很快画出来了。

红黑树的性质

  1. 节点有颜色，红色或者是黑色
  2. 根节点是黑的，虽然这个性质用处不是很大，不影响大部分的分析
  3. 为了方便，节点有指向父节点的指针（除了左右子节点的指针之外）
  4. 红色节点的子节点都是黑色的
  5. 根节点到所有叶子节点的路径上黑色节点的数量都是相同的

我们根据上面的性质可以发现，红黑树可以保持一个比较平衡，但又不是完全平衡的状态。

根据性质5和性质4，我们可以发现红黑树最不平衡的状态也就是某些节点的实际深度是另一些的两倍。

而红黑树保持这样相对平衡的状态就可以使得我们可以像其他的平衡的二叉树一样在$O(\log{N})$的时间内完成查找。

实际上红黑树在插入和删除节点的时候消耗的时间也是$O(\log{N})$，这是红黑树的一个非常好的性质。

如果我们需要一个查找、插入、删除节点都很快的数据结构，我们可以选择它。

一些基本的操作

在我们的插入删除的过程中为了保持平衡，我们需要提取一些保持平衡过程中常用的步骤。除了找节点的各个亲戚之外就是树的旋转操作。

那么下面就是常见的操作和简短的代码，代码可能是错的但是不应该影阅响读。

找爸爸

1
2
3
function parent(node) {
    return node.parent;
}

找爷爷

1
2
3
4
5
6
7
function grandParent(node) {
    const parent = parent(node);
    if(parent) {
        return parent(parent);
    }
    return null;
}

找叔叔

1
2
3
4
5
6
7
8
9
10
function uncle(node) {
    const grandParent = grandParent(node);
    if(grandParent) {
        if(grandParent.left === parent(node)) {
            return grandParent.right;
        }
        return grandParent.left;
    }
    return null;
}

找兄弟

1
2
3
4
5
6
7
8
9
10
11
function sibling(node) {
    const parent = parent(node);
    if(parent) {
        if(parent.left == node) {
            return parent.right;
        }else {
            return parent.left;
        }
    }
    return null;
}

左旋

左旋操作应该说是逆时针旋转，把一个节点变成它的右子节点的左子节点，并且继承了右子节点的左子节点为自己的新的右子节点，同时还送出了自己的父亲。具体操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function rotateLeft(node) {
    const newNode = node.right;
    const pNode = parent(node);
    if(newNode) {
        node.right = newNode.left;
        node.right.parent = node;
        newNode.left = node;
        node.parent = newNode;
        if(pNode) {
            if(pNode.left === node) {
                pNode.left = newNode;
            }else {
                pNode.right = newNode;
            }
            newNode.parent = pNode;
        }else {
            newNode.parent = null;
        }
    }   
}

右旋

右旋操作，我也更喜欢说是顺时针旋转，如果树是从上往下的话。和左旋相反，是一个节点的左儿子变成自己的父亲的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function rotateRight(node) {
    const newNode = node.left;
    const pNode = node.parent;
    if(newNode) {
        node.left = newNode.right;
        node.left.parent = node;
        newNode.right = node;
        node.parent = newNode;
        if(pNode) {
            if(pNode.left === node) {
                pNode.left = newNode;
            }else {
                pNode.right = newNode;
            }
            newNode.parent = pNode;
        }else {
            newNode.parent = null;
        }
    }
}

发表于 | 更新于

graphviz

graphviz官网

(这是一个可以使用的软件，有一套DSL可以用来画图)

实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from graphviz import Digraph

dot = Digraph(comment='The Test Table', format='png')
dot.node('A', 'Dot A')
dot.node('B', 'Dot B')
dot.node('C', 'Dot C')
dot.node('D', 'Dot D')

dot.edges(['AB', 'BC', 'AB'])

dot.save('xxx.gv')
dot.render('xxx.gv')

dot.view()
阅读全文 »

发表于 | 更新于 | 分类于 ，

分析算法和问题：原理和例子

算法可解的

说一个问题是算法可解的，意味着：

可以编写一个计算机程序，在足够的时间和空间内，这个程序可以为任意输入处理出一个正确的结果。

算法

20世纪30年代，计算机出现之前，数学家们已经在积极地定义和研究算法的概念。

算法被解释成：

一套清楚的简单指令，按照这套指令可以解决某个问题和计算某个函数。

阅读全文 »

发表于 | 更新于

Docker命令相关

创建一个网络

1
docker network create --subnet=172.18.0.0/16 mynetwork

docker默认使用的网络是172.17.0.0/16，所以创建网络应该从内网的其他部分选取。

列出网络

1
docker network ls
阅读全文 »