算法导论基础-一些二叉树概念总结
--- 1 二叉搜索树 名称 概念 前趋 比当前节点小的最大节点 后继 比当前节点大的最小节点 祖先 该节点的父节点及以上 定理： 如果x是一个含有n个结点的子树的根，那么调用INORDER-TREE-WALK(中序遍历)需要时间$\theta(n)$ 在一棵高度为h的二叉搜索树上，动态集合上的操作SEARCH,MINIMUM,MAXMUN,SUCCESSOR(后继),PREDECESSOR（前趋）需要时间O(h) 在一棵高度为h的二叉搜索树上，实现动态集合INSERT（插入）和DELETE（删除）操作需要时间O(h) 2 红黑树红黑树四条性质：（红黑树中可以没有黑色，但有红色必须满足其性质）1.每个结点为红色或黑色。2.根节点和叶结点都是黑色的。3.每个红色节点的叶结点都是黑色的。4.从一个节点X到X的子孙叶结点，所有到子孙叶结点的路径，都有相等的黑结点数。5.红色结点的儿子必定是黑的。 一棵有n个内结点的红黑树高度至多为$2\lg（_{}{n+1}）$ 结点的秩是树中小于或等于该结点的结点数量。 从某个结点x出发（不含该结点），到达叶结点的...
算法导论基础-几种基本数据结构总结
--- 1 栈（后进先出）特点： 插入（insert）–压入（push），新元素总是在最顶层 删除（delete）–弹出（pop），新元素总是第一个删除 图示： 2 队列（先进先出）特点 插入（insert）–入队（ENQUEUE）,新元素总在最末尾 删除（delete）–出队（DEQUEUE）,弹出的元素总是最旧的那个 图示：注明：队列为卷绕型，若tail[Q]=length[Q],则tail[Q]=1； 上溢：对一个满序列插入一个新元素下溢：对一个空序列删除一个元素 3 链表双向链表：每一个元素都是一个对象，一个对象包含一个关键字域合两个指针域（next，prev） 图示： 双向循环链表：带有哨兵，用于简化边界条件的处理 图示： 4 指针和对象 prev,key,next在这里作为指针 1.对象的多数组表示（三个数组prev,key,next）2.对象的单数组表示3.对象的分配与释放 将多数组中剩余的对象（free）组成一个单链表，称为自由表 自由表类似于一个栈，可以通过栈操作PUSH和POP来对自由表实现分配（ALLOCAT...
算法导论基础-几种递归式解法总结
1 代换法求解步骤：1.猜测解的形式2.用数学归纳法求出解中的常数，并证明解是正确的。 2 递归树法 3 主方法(常用)递归通式：T(n)=aT(n/b)+f(n) 其中f(n)是非递归的,$a\ge1$,$b>1$f(n)渐进趋正（对于足够大的n，$f(n)\ge0$) 考虑 f(n) 与 $n^{\log_{b}{a}}$, 情况一：f(n)<$n^{\log_{b}{a}}$–>O($n^{\log_{b}{a}-\xi}$)($\xi>0$)$\therefore$ T(n)=$\theta$($n^{\log_{b}{a}}$)。 情况二：f(n)=$n^{\log_{b}{a}}$–>$\theta$($n^{\log_{b}{a}}\cdot (\lg_{}{n})^{k}$),$k\ge0$$\therefore$ T(n)=$\theta$($n^{\log_{b}{a}}\cdot (\lg_{}{n})^{k}$) 情况三：f(n)>$n^{\log_{b}{a...
算法导论基础-几种排序算法总结
--- 算法 最坏情况运行时间 平均情况/期望运行时间 插入排序 Θ(n²) Θ(n²) 归并排序 Θ(nlgn) Θ(nlgn) 堆排序 Θ(nlgn) —— 快速排序 Θ(n²) Θ(nlgn) 计数排序 Θ(n+k) Θ(n+k) 基数排序 Θ(d(n+k)) Θ(d(n+k)) 桶排序 Θ(n²) Θ(n) 1 插入排序算法插入排序示意图： 演示C代码： 1234567891011void insertionSort(int a[], int n) { for (int i = 1; i < n; ++i) { int value = a[i]; int j = i - 1; while (j >= 0 && a[j] > value) { a[j + 1] = a[j]; --j; } a[j + 1] = value; }} 2 归并排序算法（分治法）归并排序图示： 演...