JONY

二叉树节点的前驱后继

二叉树的特殊节点为方便后序讨论，这里继续定义如下的二叉树特殊节点，并给出寻找这些节点的步骤： 1) \(mostLeft(n)\)：其递归定义为“若\(n.left\)非空则返回\(mostLeft(n.left)\)，否则返回\(n\)”。等价于迭代步骤“每轮迭代若\(n.left\)非空则置\(n=n.left\)并继续迭代，否则退出迭代返回\(n\)”。直观上是以\(n\)为树根的子树的最左节点； 2) \(mostRight(n)\)：其递归定义为“若\(n.right\)非空则返回\(mostRight(n.right)\)，否则返回\(n\)”。等价于迭代步骤“每轮迭代若\(n.right\)非空则置\(n=n.right\)并继续迭代，否则退出迭代返回\(n\)”。直观上是以\(n\)为树根的子树的最右节点；… 阅读全文

线索二叉树与线索二叉树的迭代遍历

线索二叉树(Threaded Binary Tree) 在孩子表示法二叉树中，任何节点的左右孩子指针都可能为空，事实上总空指针数目满足如下规律： a) 设任意的孩子表示法二叉树有\(n\)个节点，该二叉树的空指针数目为\(n+1\)； 证明：设度为0,1,2的节点数为\(n_0,n_1,n_2\)，则空指针总数为\(x=2n_0+n_1\)。之前讨论二叉树性质时证明了\(n_0=n_2+1\)。由于二叉树节点数\(n=n_0+n_1+n_2\)，那么\(n=2n_0+n_1-1\)，所以\(x=n+1\)。 上述性质表明二叉树有大量空指针，若让空指针指向其他节点以记录额外信息，就能得到线索二叉树。线索二叉树节点需额外维护2个变量描述指针是否表示孩子，这里计为\(leftType,rightType\)。\(leftType=0\)表示指向原左孩子，\(leftType=1\)表示指向其他节点，此时的左孩子指针称为线索，\(rightType\)同理。将普通二叉树变成线索二叉树的过程称为线索化。一般来说线索二叉树特指“用线索记录节点在遍历序列前驱后继的线索二叉树”，所以本文讨论中/前/后序线索二叉树。中/前/后序线索二叉树可按如下方式通过原二叉树来定义，其中\(x\)是“原二叉树”任意节点：… 阅读全文

用栈实现二叉树的迭代遍历

用栈记录节点的祖先 在之前讨论节点前驱后继的文章中，通过节点上额外存储的\(parent\)指针实现了前中后序遍历的迭代算法，文章中为体现出通过“连续寻找后继”实现遍历，用多个函数组成了这3种算法，这些算法不能直接用于无\(parent\)指针的普通二叉树，本文讨论如何将这几种算法改造成适用于普通二叉树的，由于正序遍历和逆序遍历存在对称性，故不再讨论逆序遍历。先将上述算法通用的\(traverse\)函数改造为如下步骤，其仅多了创建空栈\(s\)并将其传入\(getFirst,getSuccessor\)的步骤： 1) \(traverse(root)\)：若树根\(root\)为空则直接返回，否则初始化空栈\(s\)，执行\(head=getFirst(root, s)\)，然后“访问”\(head\)，然后开始迭代，每轮迭代执行\(head=getSuccessor(head,… 阅读全文

时序逻辑单元

时序逻辑电路组合逻辑电路中没有“时间”，其当前时刻输出仅取决于当前时刻输入。而时序逻辑电路的当前时刻输出不仅仅取决于当前时刻输入，还与电路之前的状态(输入输出)有关，其可继续分为这两大类： 1) 同步时序逻辑：其特点是电路存在一个公共时钟信号，用于统一的控制协调各个单元的工作。时钟通常由晶振控制的，其会按固定时间间隔(计为\(t_1\))提供固定时间长度的脉冲(计为\(t_2\))。通常把\(t_1=t_2\)的时钟信号称为对称时钟，否则称为非对称时钟。有时为划分出更细粒度的时钟，会把时钟信号(\(C_1\))经过提供固定延迟的设备得到副时钟信号(\(C_2\))。这样在1个时间段里能区分出4个时间点，其分别为\(C_1\)上升、\(C_2\)上升、\(C_1\)下降、\(C_2\)下降。如果4个时间点不够，可继续增设更多得延迟时钟信号；… 阅读全文

流水线中的三种冒险

流水线中的三种冒险ISA指令的实现会包含阻碍流水线的因素，使程序不能完全流水式执行。上图给出了在5段流水线的机器中，指令“完全”流水执行和流水线被阻碍时的对比。这种为保证正确执行，而在流水线中插入的停顿称为气泡。可以发现如果在一个指令中插入了1个气泡，那么这个指令之后的步骤都会被推迟1个时钟周期，更糟糕的是这些步骤被推迟1个周期会导致相应硬件的占用被推迟1个周期，导致后面的指令也要相继推迟才能占用这些硬件。也就是1个气泡可能导致该指令后的所有指令晚1个周期结束。 阻碍流水线的因素被称为冒险(Hazard,和电路的冒险不是同个概念)。冒险可分如下几类： 1) 结构冒险：同时抢占同一硬件资源导致的。比如在一个周期里同时fetch内存； 2) 数据冒险：又称为相关，数据的前后依赖关系导致的。比如前面MIC-3讨论过微指令间的写后读相关，因为是在同一条指令内的相关，所以也比较容易直接解决。进入流水线的ISA指令间也有相关，比如在流水线中的2条指令，上条指令的数据在周期i尚未产生，但下条指令在周期i依赖该数据；… 阅读全文

内存电路与内存芯片

内存电路前面讨论过如何用多个D触发器构造8位或更多位的寄存器，而内存也是通过锁存器/除法器构造的，不过通常内存容量远远大于寄存器容量，需用用其他方式编排锁存器/除法器。上图给出了基于D触发器的12位内存电路，该电路虽然只有12位，但其方案本身是支持更大容量的。 该电路相对于之前讨论过的寄存器电路，其并未把每个D触发器的输入输出端作为管脚暴露，因为其对触发器进行了编址，该电路是按每3个位为1个字编址的，共包含4个字，其数据读写是以字为单位的。其中\(A_0,A_1\)是地址信号，其可接受4种0-1组合用于“定位”内存中待操作的字。\(I_0,I_1,I_2\)为需要写入内存某个字的输入数据信号。\(O_0,O_1,O_2\)为当前内存某个字的存储内容的输出数据信号。\(CS\)是片选信号、\(RD\)表示进行读或写、\(OE\)是输出的使能，这3者构成了这个内存的控制信号。… 阅读全文

用MORRIS方法实现二叉树的迭代遍历

中序遍历的Morris算法1968年Knuth在其著作TAOCP提出问题：“如何在不用额外空间、不在节点额外存储信息(比如像线索二叉树那样存储额外变量)的前提下\(O(n)\)的实现二叉树中序遍历”。只存储\(O(1)\)规模的“额外信息”是无法保证完成中序遍历的，比如对于所有节点都无右孩子的二叉树，中序遍历“访问”完其最左节点时，此刻算法必须要额外记录了该节点的所有祖先才能保证剩下的遍历过程的正确执行，而其祖先的数目是\(O(n)=O(h)\)，即最坏需\(O(n)\)规模的“额外信息”，所以该问题的难点在于如何存储这些信息。 1979年J.H.Morris在《Traversing Binary Trees Simply and Cheaply》中提出符合Knuth要求的中序遍历算法，算法执行时会动态将二叉树部分空右孩子指针指向其他节点，以临时记录遍历所需的“额外信息”，并在算法结束时还原二叉树。1988年的文章《Morris’… 阅读全文

CPU管脚信号与总线操作

CPU管脚信号如果不了解CPU的部分特性就很难分析总线，这里先了解CPU管脚信号，以及CPU同内存与IO设备的交互方式。CPU管脚信号同样可像内存那样分类为地址信号、数据信号、控制信号。 从内存取指令时可能是这样的流程：“CPU先将指令所在内存地址从自己的地址信号管脚发出，然后再从自己的管脚发出控制信号，用于通知内存自己想要读某个字，内存在收到通知后会把这个字的数据送到CPU的数据信号管脚，然后也发出控制信号，声明自己完成了任务，再然后CPU会收到内存发来的控制信号，接着从自己的数据信号管脚获取这个数据，最终完成从内存取指令的任务”。 CPU性能与数据信号和地址信号的管脚数有关，有\(m\)个地址信号管脚的CPU可以寻址\(2^m\)个地址(通常称为可寻址\(2^m\)的地址空间)，现代CPU常见的地址空间大小是16、32、64。类似的有\(n\)个数据信号管脚的CPU可“一次性”读写\(n\)位，现代CPU常见的\(n\)为8、32、64。当CPU数据信号管脚只有8个，那么其在读32位的字时就需要“4次操作”，所以32个数据信号管脚的CPU可能比8个的快很多。… 阅读全文

二叉搜索树与二叉搜索树的平衡性

二叉搜索树(Binary Search Tree)二叉搜索树也称二叉查找树、二叉排序树，简写为BST，是种基于二叉树的数据结构。下面给出其定义： 1) 二叉搜索树节点：额外包含一个关键字(\(key\))的二叉树节点； 2) 二叉搜索树：由二叉搜索树节点组成，要么是空树，要么左右子树都是二叉搜索树，并且若左子树非空，则左子树所有节点的\(key\)都不大于树根的\(key\)，若右子树非空，则右子树所有节点的\(key\)都不小于树根的\(key\)； 下面给出BST的关键性质，其也是另一种BST的等价定义，根据中序遍历的性质和BST的定义不难验证： a1) 由BST节点构成的二叉树是BST \(\Leftrightarrow\) 该二叉树的中序序列按\(key\)非严格递增； 上图是BST的例子，绘制BST时会把\(key\)标注在节点上。BST本身的功能是存储一组\(key\)，并提供查找\(key\)、插入\(key\)、删除\(key\)的能力。本文约定BST允许存储多个重复\(key\)，因为这符合BST的定义，但也有部分场景或教材会要求\(key\)不允许重复。下面给出本文对BST运算的定义，其中的额外要求是为了方便之后的文章讨论其他基于BST的数据结构：… 阅读全文

AVL树

AVL树(高度平衡二叉树)1962年苏联学者G. M. Adelson-Velsky和E. M. Landis提出AVL树，是计算机史上第一种自平衡二叉树。AVL树通常也被称为高度平衡二叉树，因为AVL树的形态受左右子树高度的约束。下面给出AVL树的定义： 1) AVL树：AVL树首先是BST，其要么是空树，要么左右子树都是AVL树且两者的高度差小于2； 通常称AVL树中任意节点\(x\)的左子树高度减右子树高度的差值为\(x\)的平衡因子(balance factor)。那么对于任何非空的AVL树，其树根的平衡因子只能取-1,0,1。下面给出AVL树的简单性质，其也可看作AVL树的非递归定义： a1) 一个BST是AVL树 \(\Leftrightarrow\) 该BST所有节点的左右子树高度差都小于2； 上图是AVL树形态的特例，其所有非叶子节点的平衡因子都为-1，直观上看其左右子树的规模差距并不太大。一般的自平衡二叉树仅仅是为了让BST运算的代价更低，故本文对其运算的定义和前文对BST运算的定义一致，但要额外保证每次运算前后二叉树是AVL树，且运算代价和BST运算一样以树高为上界，否则构造AVL树就失去意义。另外可发现BST的\(find\)不会改变树结构，符合AVL树运算的要求，故之后只需讨论另外2种运算的实现。下述性质将保证AVL树是自平衡二叉树：… 阅读全文
滚动至顶部