算法知识点总结

发表于 | 分类于

算法知识点总结

排序算法

排序稳定性

  • 归并排序、冒泡排序、插入排序、基数排序是稳定的

  • 选择排序、快速排序、希尔排序、堆排序是不稳定的

时间复杂度

  • 冒泡 平均O(n2） 最大O(n2) 稳定 n小时较好
  • 选择 平均O(n2) 最大O(n2) 不稳定 n小时较好
  • 插入 平均O(n2) 最大O(n2) 稳定 大部分已排序时较好
  • 快速 平均小O(nlogn) 最大O(n2) 不稳定 n大时较好
  • 归并 平均小O(nlogn) 最大O(nlogn) 稳定 n大时较好
  • 堆 平均O(nlogn) 最大O(nlogn) 不稳定 n大时较好

排序思想

二叉树

二叉树的性质

性质1：二叉树第i层上的结点数目最多为2^(i-1)(i>=1)

性质2：深度为k的二叉树至多有2^k-1个结点（k>=1） 至少k个

性质3：包含n个结点的二叉树的高度至少为(log2n)+1

性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

性质5：如果一棵完全二叉树的结点总数为n，那么叶子结点等于n （当n为偶数时）或者(n+1)/2（当n为奇数时）

遍历

先序遍历：（1）访问根节点；（2）采用先序递归遍历左子树；（3）采用先序递归遍历右子树；

中序遍历：（1）采用中序遍历左子树；（2）访问根节点；（3）采用中序遍历右子树

后序遍历：（1）采用后序递归遍历左子树；（2）采用后序递归遍历右子树；（3）访问根节点；

二叉树构建

已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：

  1. 根据前序序列的第一个元素建立根结点；
  2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
  3. 在前序序列中确定左右子树的前序序列；
  4. 由左子树的前序序列和中序序列建立左子树；
  5. 由右子树的前序序列和中序序列建立右子树。

已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：

  1. 根据后序序列的最后一个元素建立根结点；
  2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
  3. 在后序序列中确定左右子树的后序序列；
  4. 由左子树的后序序列和中序序列建立左子树；
  5. 由右子树的后序序列和中序序列建立右子树。

只给出先序遍历和后序遍历不能唯一确定二叉树的例子

二叉排序树

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）二叉排序树中序遍历为从大到小的顺序；

二叉排序树

二叉排序树查找：
要在二叉树中找出查找最大最小元素是极简单的事情，从根节点一直往左走，直到无路可走就可得到最小值；从根节点一直往右走，直到无路可走，就可以得到最大值。

二叉排序树插入：
插入新元素时，可以从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到末端，就是插入点。

二叉排序树删除：
对于二叉排序树中的节点A，对它的删除分为两种情况：

  • 如果A只有一个子节点，就直接将A的子节点连至A的父节点上，并将A删除；

  • 如果A有两个子节点，我们就以右子树内的最小节点取代A

    二叉树分类

  • 满二叉树: 除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。

  • 完全二叉树: 除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。

完全二叉书<满二叉树

平衡二叉树

【平衡特性1】：左子树的深度和右子树的深度相差不能超过1

【平衡特性2】：它的左右子树也要是平衡二叉树

二叉线索树

结点结构图：

LChild  Ltag   Data  Rtag   RChild

如果有左孩子，则LChild继续指向左孩子，否则，指向该结点的前驱结点。

如果有右孩子，则RChild继续指向右孩子，否则，指向该结点的后继结点。

Ltag 用来标记是 左孩子（Ltag = 0）还是 前驱结点 （Ltag = 1）

Rtag 用来标记是 右孩子(Rtag = 0) 还是 后继结点 (Rtag = 1)

前驱节点

  • 若一个节点有左子树，那么该节点的前驱节点是其左子树中val值最大的节点
  • 若一个节点没有左子树，那么判断该节点和其父节点的关系
    • 若该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点。
    • 若该节点是其父节点的左边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右边孩子，那么Q就是该节点的前驱

后继节点（类比前驱结点）

  • 若一个节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点
  • 若一个节点没有右子树，那么判断该节点和其父节点的关系
    • 若该节点是其父节点的左边孩子，那么该节点的后继结点即为其父节点。
    • 若该节点是其父节点的右边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的左边孩子，那么Q就是该节点的后继节点

n结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个

递归

递归实现

递归是栈实现的。栈是先进后出,也就是上次递归调用的时候,保存在栈顶

递归思想

递归次数可使用多项式展开思想