树结构

树与二叉树

树的定义树(Tree)默认指有根树(Rooted Tree)，无根树(Unrooted Tree)之后会在图结构(Graph)中讨论。树是种非线性结构，树中的元素一般称为树节点(Tree Node)，线性表元素的前驱后继是空或唯一的，一个树节点可以有不止一个“后继节点”，“前驱节点”是空或唯一的。给出树\(T\)的递归定义如下，递归定义法在算法中经常使用到： 1) \(T\)是由\(n\geq 0\)个节点(Node)组成的有限集合； 2) 当\(n=0\)时，\(T\)是空集称为空树； 3) 当\(n\geq 1\)时，\(T\)有且仅有1个节点被指定为\(T\)的树根(Root)； 4) 当\(n\geq 2\)时，\(T\)除树根外的所有节点被划入\(m\geq 1\)个不相交有限集合\(T_1,T_2…T_m\)(即它们的并集是\(T\)除树根外的所有节点，它们中任意2个的交集为空集)，并要求\(T_1,T_2…T_m\)都递归的满足树的定义，它们被称为\(T\)的子树(Subtree)；… 阅读全文

二叉树的性质

二叉树的高度如上图所示，可直观的把二叉树节点分层，也可以递归定义节点所在的层(Level)为“树根在第1层，其他节点的层数等于其父亲节点的层数加1”。树中层数最大的节点的层数称为树的深度(高度)。层数满足如下性质： a1) 二叉树在第\(k\)层的最大节点数为\(2^{k-1}\)； a2) 设二叉树的节点数为\(n\)，深度为\(m\)，则\(n\leq 2^m – 1\)； 有些教材会从0开始计层(level)或将单节点二叉树的高度计为0，所以之后文章里的高度可能和这里不同。   二叉树的形态直观上如果两个二叉树画出来后“重合”就称它们相似或形态相同，考虑将这种直观概念转化成严格定义，先用\(S(T_1,T_2)\)表示二叉树\(T_1,T_2\)是否相似，直观上如果两个二叉树的树根、左子树、右子树都分别“重合”，那么两个二叉树“重合”，基于这点可严格给出\(S(T_1,T_2)\)的递归定义为“若\(T_1,T_2\)的树根都为空则返回真，若\(T_1,T_2\)的树根只有1个为空则返回假，若\(T_1,T_2\)的树根都非空则返回\(S(L_1,L_2)\)且\(S(R_1,R_2)\)。其中\(L_1,L_2\)分别是\(T_1,T_2\)的左子树，\(R_1,R_2\)分别是\(T_1,T_2\)的右子树”。… 阅读全文

二叉树的遍历与重建

遍历算法之前在讨论线性表时，用遍历指代“按该线性表的序依次访问所有元素(节点)”，并未详细定义什么是“遍历”。这是因为线性表的遍历通常都是按线性表本身的序来遍历的，并且在日常编程中不太区分遍历、循环、枚举等概念。准确来说遍历(Traversal)是一类特定的算法，其能够按算法设计者所要求的次序，访问且仅访问一次数据结构中的所有元素。比如对于数组，遍历既能是简单的顺序遍历，也可以是更复杂的“先访问全部偶数索引、再访问全部奇数索引”，具体如上图。 对于大部分简单且常见的遍历算法，代价通常都是\(O(n)\)且仅需\(O(1)\)额外空间。但在遇到复杂的数据结构、或需要复杂的访问次序时，可能会有更高的代价和空间复杂度，比如之后会讨论的图遍历。原因之一是当元素间的关系更复杂时，会无法避免的多次“物理访问”同个节点，这时“仅访问一次”的要求就成了“负担”，需要额外的步骤或空间才能区分“仅访问一次”。… 阅读全文

二叉树节点的前驱后继

二叉树的特殊节点为方便后序讨论，这里继续定义如下的二叉树特殊节点，并给出寻找这些节点的步骤： 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,… 阅读全文

用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’… 阅读全文

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

二叉搜索树(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树是自平衡二叉树：… 阅读全文

红黑树

红黑树(Red-Black Tree)1972年德国学者R.Bayer提出平衡二叉B树，1978年Leo J. Guibas和Robert Sedgewick将其重新表述为更容易描述和实现的红黑树。红黑树基本是目前最流行的自平衡二叉树，很多程序语言的数据类型、操作系统的算法都是基于红黑树的。下面先定义松弛红黑树(relaxed red-black tree)，然后在松弛红黑树的基础上定义红黑树： 1) 松弛红黑树节点：额外包含一个布尔值的BST节点。为方便称其表示红或黑，对应的节点为红节点或黑节点； 2) 松弛红黑树：由松弛红黑树节点构成的BST，且满足如下性质： 2.1) 红节点如果有孩子，则孩子只能是黑节点； 2.2) 对于任意节点\(x\)，从\(x\)到\(x\)子树的所有叶节点的路径中，黑节点数必须相同； 3)… 阅读全文
滚动至顶部