在计算机科学中,二分搜索(binary search),也称折半搜索(half-interval search)、对数搜索(logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

问题 1

给定一个有序的数组,查找 value 是否在数组中,不存在返回 -1。

例如:{ 1, 2, 3, 4, 5 } 找 3,返回下标 2(下标从 0 开始计算)。

/* 注意:题目保证数组不为空,且 n 大于等于 1 ,以下问题默认相同 */
int BinarySearch(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;
    // 如果这里是 int right = n 的话,那么下面有两处地方需要修改,以保证一一对应:
    // 1、下面循环的条件则是 while(left < right)
    // 2、循环内当 array[middle] > value 的时候,right = middle

    while (left <= right)  // 循环条件,适时而变
    {
        int middle = left + ((right - left) >> 1);  // 防止溢出,移位也更高效。同时,每次循环都需要更新。
        if (array[middle] > value)
            right = middle - 1;
        else if (array[middle] < value)
            left = middle + 1;
        else
            return middle;
        // 可能会有读者认为刚开始时就要判断相等,但毕竟数组中不相等的情况更多
        // 如果每次循环都判断一下是否相等,将耗费时间
    }
  
    return -1;
}

问题 2

给定一个有序的数组,查找第一个等于 value 的下标,找不到返回 -1。

例如:{ 1, 2, 2, 2, 4 } 找 2,返回下标 1(下标从 0 开始计算)。

int BinarySearch(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;

    while (left <= right)
    {
        int middle = left + ((right - left) >> 1);

        if (array[middle] >= value)  // 因为是找到最小的等值下标,所以等号放在这里
            right = middle - 1;
        else
            left = middle + 1;
    }

    if (left < n && array[left] == value)
        return left;

    return -1;
}

如果问题改为"查找 value 最后一个等于 value 的下标"呢?只需改动两个位置:

  1. if (array[middle] >= value)中的等号去掉;
  2. if (left < n && array[left] == value)
        return left;

    改为

    if (right >= 0 && array[right] == value)
        return right;

问题 3

给定一个有序的数组,查找第一个大于等于 value 的下标,都比 value 小则返回 -1。

也就是说如果有等于 value 的返回第一个等于 value 的下标,如果没有则返回第一个大于 value 的下标。

int BinarySearch(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;

    while (left <= right)  
    {
        int middle = left + ((right - left) >> 1);
      
        if (array[middle] >= value)
            right = middle - 1;
        else
            left = middle + 1;
    }
    
    return (left < n) ? left : -1;
}

如果问题改为"查找最后一个小于等于 value 的下标"呢?只需改动两个位置:

  1. if (array[middle] >= value)的等号去掉;
  2. return (left < n) ? left : -1改为return (right >= 0) ? right : -1

如何快速判断自己的二分程序是否正确

我们知道二分的思想就是每次取一半,想象一下,不管给我们的数组有多长,每次取一半,最终都会被压缩成长度为 1 的数组,然后在这个长度为 1 的数组里判断并返回,所以我们可以直接用长度为 1 的数组来测试程序。以上述的问题 3 为例。

  1. 若找不到。例如数组为 { 0 },value = 1,则 left = 1,right = 0,left 越界;
  2. 若可以找到;
    2.1. 找到等于 value 的。例如数组为 { 0 },value = 0,则 left = 0,right = -1,right 越界;
    2.2. 找到大于 value 的。例如数组为 { 0 },value = -1,则left = 0,right = -1,right 越界;

对比程序最后的返回语句return (left < n) ? left : -1,代码正确。

参考文献

本篇针对面试中常见的二叉树操作作个总结:

  1. 前序遍历,中序遍历,后序遍历;
  2. 层次遍历;
  3. 求树的结点数;
  4. 求树的叶子数;
  5. 求树的深度;
  6. 求二叉树第k层的结点个数;
  7. 判断两棵二叉树是否结构相同;
  8. 求二叉树的镜像;
  9. 求两个结点的最低公共祖先结点;
  10. 求任意两结点距离;
  11. 找出二叉树中某个结点的所有祖先结点;
  12. 不使用递归和栈遍历二叉树;
  13. 二叉树前序中序推后序;
  14. 判断二叉树是不是完全二叉树;
  15. 判断是否是二叉查找树的后序遍历结果;
  16. 给定一个二叉查找树中的结点,找出在中序遍历下它的后继和前驱;
  17. 二分查找树转化为排序的循环双链表;
  18. 有序链表转化为平衡的二分查找树;
  19. 判断是否是二叉查找树。

1 前序遍历,中序遍历,后序遍历;

1.1 前序遍历

对于当前结点,先输出该结点,然后输出它的左孩子,最后输出它的右孩子。以上图为例,递归的过程如下:

  1. 输出 1,接着左孩子;
  2. 输出 2,接着左孩子;
  3. 输出 4,左孩子为空,再接着右孩子;
  4. 输出 6,左孩子为空,再接着右孩子;
  5. 输出 7,左右孩子都为空,此时 2 的左子树全部输出,2 的右子树为空,此时 1 的左子树全部输出,接着 1 的右子树;
  6. 输出 3,接着左孩子;
  7. 输出 5,左右孩子为空,此时 3 的左子树全部输出,3 的右子树为空,至此 1 的右子树全部输出,结束。

而非递归版本只是利用 stack 模拟上述过程而已,递归的过程也就是出入栈的过程。注意加粗部分的理解。

/* 前序遍历递归版 */
void PreOrderRec(Node * node)
{
    if (node == nullptr)
        return;
  
    cout << node->data << " ";   // 先输出当前结点   
    PreOrderRec(node->left);     // 然后输出左孩子
    PreOrderRec(node->right);    // 最后输出右孩子
}

/* 前序遍历非递归版 */
void PreOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    stack<Node*> S;
    cout << node->data << " ";
    S.push(node);
    node = node->left;

    while (!S.empty() || node)
    {
        while (node)
        {
            cout << node->data << " "; // 先输出当前结点  
            S.push(node);
            node = node->left;         // 然后输出左孩子
        }                              // while 结束意味着左孩子已经全部输出

        node = S.top()->right;         // 最后输出右孩子
        S.pop();
    }
}

1.2 中序遍历

对于当前结点,先输出它的左孩子,然后输出该结点,最后输出它的右孩子。以(1.1)图为例:

  1. 1-->2-->4,4 的左孩子为空,输出 4,接着右孩子;
  2. 6 的左孩子为空,输出 6,接着右孩子;
  3. 7 的左孩子为空,输出 7,右孩子也为空,此时 2 的左子树全部输出,输出 2,2 的右孩子为空,此时 1 的左子树全部输出,输出 1,接着 1 的右孩子;
  4. 3-->5,5 左孩子为空,输出 5,右孩子也为空,此时 3 的左子树全部输出,而 3 的右孩子为空,至此 1 的右子树全部输出,结束。
/* 中序遍历递归版 */
void InOrderRec(Node * node)
{
    if (node == nullptr)
        return;
  
    InOrderRec(node->left);     // 先输出左孩子
    cout << node->data << " ";  // 然后输出当前结点
    InOrderRec(node->right);    // 最后输出右孩子
}

/* 前序遍历非递归版 */
void InOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    stack<Node*> S;
    S.push(node);
    node = node->left;

    while (!S.empty() || node)
    {
        while (node)
        {
            S.push(node);
            node = node->left;
        }                             // while 结束意味着左孩子为空

        cout << S.top()->data << " "; // 左孩子已经全部输出,接着输出当前结点
        node = S.top()->right;        // 左孩子全部输出,当前结点也输出后,最后输出右孩子
        S.pop();
    }
}

1.3 后序遍历

对于当前结点,先输出它的左孩子,然后输出它的右孩子,最后输出该结点。依旧以(1.1)图为例:

  1. 1->2->4->6->7,7 无左孩子,也无右孩子,输出 7,此时 6 无左孩子,而 6 的右子树也全部输出,输出 6,此时 4 无左子树,而 4 的右子树已全部输出,接着输出 4,此时 2 的左子树全部输出,且 2 无右子树,输出 2,此时 1 的左子树全部输出,接着转向右子树;
  2. 3->5,5 无左孩子,也无右孩子,输出 5,此时 3 的左子树全部输出,且 3 无右孩子,输出 3,此时 1 的右子树全部输出,输出 1,结束。

非递归版本中,对于一个结点,如果我们要输出它,只有它既没有左孩子也没有右孩子或者它有孩子但是它的孩子已经被输出(由此设置 pre 变量)。若非上述两种情况,则将该结点的右孩子和左孩子依次入栈,这样就保证了每次取栈顶元素的时候,先依次遍历左子树和右子树。

/* 后序遍历递归版 */
void PostOrderRec(Node * node)
{
    if (node == nullptr)
        return;
  
    PostOrderRec(node->left);   // 先输出左孩子
    PostOrderRec(node->right);  // 然后输出右孩子
    cout << node->data << " ";  // 最后输出当前结点
}

/* 后序遍历非递归版 */
void PostOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    Node * pre = nullptr;
    stack<Node*> S;
    S.push(node);

    while (!S.empty())
    {
        node = S.top();

        if ((!node->left && !node->right) ||                    // 第一个输出的必是无左右孩子的叶子结点,只要第一个结点输出,
            (pre && (pre == node->left || pre == node->right))) // 以后的 pre 就不会是空。此处的判断语句加入一个 pre,只是用来
        {                                                       // 确保可以正确输出第一个结点。
            cout << node->data << " ";  // 左右孩子都全部输出,再输出当前结点
            pre = node;
            S.pop();
        }
        else
        {
            if (node->right)
                S.push(node->right);  // 先进右孩子,再进左孩子,取出来的才是左孩子
            if (node->left)
                S.push(node->left);
        }
    }
}

2 层次遍历

void LevelOrder(Node * node)
{
    Node * p = node;
    queue<Node*> Q;  // 队列
    Q.push(p);
  
    while (!Q.empty())
    {
        p = Q.front();
        cout << p->data << " ";
        Q.pop();
      
        if (p->left)
            Q.push(p->left);  // 注意顺序,先进左孩子
        if (p->right)
            Q.push(p->right);
    }
}

3 求树的结点数

int CountNodes(Node * node)
{
    if (node == nullptr)
        return 0;
  
    return CountNodes(node->left) + CountNodes(node->right) + 1;
}

4 求树的叶子数

int CountLeaves(Node * node)
{
    if (node == nullptr)
        return 0;
  
    if (!node->left && !node->right)
        return 1;
  
    return CountLeaves(node->left) + CountLeaves(node->right);
}

5 求树的深度

int GetDepth(Node * node)
{
    if (node == nullptr)
        return 0;
  
    int left_depth = GetDepth(node->left) + 1;
    int right_depth = GetDepth(node->right) + 1;
  
    return left_depth > right_depth ? left_depth : right_depth;
}

6 求二叉树第k层的结点个数

int GetKLevel(Node * node, int k)
{
    if (node == nullptr)
        return 0;
  
    if (k == 1)
        return 1;
  
    return GetKLevel(node->left, k - 1) + GetKLevel(node->right, k - 1);
}

7 判断两棵二叉树是否结构相同

不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。

bool StructureCmp(Node * node1, Node * node2)
{
    if (node1 == nullptr && node2 == nullptr)
        return true;
    else if (node1 == nullptr || node2 == nullptr)
        return false;
  
    return StructureCmp(node1->left, node2->left) && Str1uctureCmp(node1->right, node2->right);
}

8 求二叉树的镜像

对于每个结点,我们交换它的左右孩子即可。

void Mirror(Node * node)
{
    if (node == nullptr)
        return;
  
    Node * temp = node->left;
    node->left = node->right;
    node->right = temp;
  
    Mirror(node->left);
    Mirror(node->right);
}

9 求两个结点的最低公共祖先结点

最低公共祖先,即 LCA(Lowest Common Ancestor),见下图:

结点 3 和结点 4 的最近公共祖先是结点 2,即 LCA(3,4)=2。在此,需要注意到当两个结点在同一棵子树上的情况,如结点 3 和结点 2 的最近公共祖先为 2,即 LCA(3,2)=2。同理 LCA(5,6)=4,LCA(6,10)=1。

Node * FindLCA(Node * node, Node * target1, Node * target2)
{
    if (node == nullptr)
        return nullptr;
    if (node == target1 || node == target2)
        return node;
  
    Node * left = FindLCA(node->left, target1, target2);
    Node * right = FindLCA(node->right, target1, target2);
    if (left && right)  // 分别在左右子树
        return node;
  
    return left ? left : right;  // 都在左子树或右子树
}

10 求任意两结点距离

首先找到两个结点的 LCA,然后分别计算 LCA 与它们的距离,最后相加即可。

int FindLevel(Node * node, Node * target)
{
    if (node == nullptr)
        return -1;
    if (node == target)
        return 0;
  
    int level = FindLevel(node->left, target);  // 先在左子树找
    if (level == -1)
        level = FindLevel(node->right, target);  // 如果左子树没找到,在右子树找
  
    if (level != -1)  // 找到了,回溯
        return level + 1;
  
    return -1;  // 如果左右子树都没找到
}

int DistanceNodes(Node * node, Node * target1, Node * target2)
{
    Node * lca = FindLCA(node, target1, target2);  // 找到最低公共祖先结点
    int level1 = FindLevel(lca, target1); 
    int level2 = FindLevel(lca, target2);
  
    return level1 + level2;
}

11 找出二叉树中某个结点的所有祖先结点

如果给定结点 5,则其所有祖先结点为 4,2,1。

bool FindAllAncestors(Node * node, Node * target)
{
    if (node == nullptr)
        return false;
    if (node == target)
        return true;
  
    if (FindAllAncestors(node->left, target) || FindAllAncestors(node->right, target))  // 找到了
    {
        cout << node->data << " ";
        return true;  // 回溯
    }
  
    return false;  // 如果左右子树都没找到
}

12 不使用递归和栈遍历二叉树

1968 年,高德纳(Donald Knuth)提出一个问题:是否存在一个算法,它不使用栈也不破坏二叉树结构,但是可以完成对二叉树的遍历?随后 1979 年,James H. Morris 提出了二叉树线索化,解决了这个问题。(根据这个概念我们又提出了一个新的数据结构,即线索二叉树,因线索二叉树不是本文要介绍的内容,所以有兴趣的朋友请移步线索二叉树

前序,中序,后序遍历,不管是递归版本还是非递归版本,都用到了一个数据结构--栈,为何要用栈?那是因为其它的方式没法记录当前结点的 parent,而如果在每个结点的结构里面加个 parent 分量显然是不现实的,而线索化正好解决了这个问题,其含义就是利用结点的右孩子空指针,指向该结点在中序序列中的后继。下面具体来看看如何使用线索化来完成对二叉树的遍历。

先看前序遍历,步骤如下:

  1. 如果当前结点的左孩子为空,则输出当前结点并将其右孩子作为当前结点;
  2. 如果当前结点的左孩子不为空,在当前结点的左子树中找到当前结点在中序遍历下的前驱结点;
    2.1. 如果前驱结点的右孩子为空,将它的右孩子设置为当前结点,输出当前结点并把当前结点更新为当前结点的左孩子;
    2.2. 如果前驱结点的右孩子为当前结点,将它的右孩子重新设为空,当前结点更新为当前结点的右孩子;
  3. 重复以上步骤 1 和 2,直到当前结点为空。
/* 前序遍历 */
void PreOrderMorris(Node * root)
{
    Node * cur = root;
    Node * pre = nullptr;
  
    while (cur)
    {
        if (cur->left == nullptr)  // 步骤 1
        {
            cout << cur->data << " ";
            cur = cur->right;
        }
        else
        {
            pre = cur->left;
            while (pre->right && pre->right != cur)  // 步骤 2,找到 cur 的前驱结点
                pre = pre->right;

            if (pre->right == nullptr)  // 步骤 2.1,cur 未被访问,将 cur 结点作为其前驱结点的右孩子
            {
                cout << cur->data << " ";
                pre->right = cur;
                cur = cur->left;
            }
            else  // 步骤 2.2,cur 已被访问,恢复树的原有结构,更改 right 指针 
            {
                pre->right = nullptr;
                cur = cur->right;
            }
        }
    }
}

再来看中序遍历,和前序遍历相比只改动一句代码,步骤如下:

  1. 如果当前结点的左孩子为空,则输出当前结点并将其右孩子作为当前结点;
  2. 如果当前结点的左孩子不为空,在当前结点的左子树中找到当前结点在中序遍历下的前驱结点;
    2.1. 如果前驱结点的右孩子为空,将它的右孩子设置为当前结点,当前结点更新为当前结点的左孩子;
    2.2. 如果前驱结点的右孩子为当前结点,将它的右孩子重新设为空,输出当前结点,当前结点更新为当前结点的右孩子;
  3. 重复以上步骤 1 和 2,直到当前结点为空。
/* 中序遍历 */
void InOrderMorris(Node * root)
{
    Node * cur = root;
    Node * pre = nullptr;
  
    while (cur)
    {
        if (cur->left == nullptr)  //(1)
        {
            cout << cur->data << " ";
            cur = cur->right;
        }
        else
        {
            pre = cur->left;
            while (pre->right && pre->right != cur)  //(2),找到 cur 的前驱结点
                pre = pre->right;

            if (pre->right == nullptr)  //(2.1),cur 未被访问,将 cur 结点作为其前驱结点的右孩子
            {
                pre->right = cur;
                cur = cur->left;
            }
            else  //(2.2),cur 已被访问,恢复树的原有结构,更改 right 指针 
            {
                cout << cur->data << " ";
                pre->right = nullptr;
                cur = cur->right;
            }
        }
    }
}

最后看下后序遍历,后序遍历有点复杂,需要建立一个虚假根结点 dummy,令其左孩子是 root。并且还需要一个子过程,就是倒序输出某两个结点之间路径上的各个结点。

步骤如下:

  1. 如果当前结点的左孩子为空,则将其右孩子作为当前结点;
  2. 如果当前结点的左孩子不为空,在当前结点的左子树中找到当前结点在中序遍历下的前驱结点;
    2.1. 如果前驱结点的右孩子为空,将它的右孩子设置为当前结点,当前结点更新为当前结点的左孩子;
    2.2. 如果前驱结点的右孩子为当前结点,将它的右孩子重新设为空,倒序输出从当前结点的左孩子到该前驱结点这条路径上的所有结点,当前结点更新为当前结点的右孩子;
  3. 重复以上步骤 1 和 2,直到当前结点为空。
struct Node
{
    int data;
    Node * left;
    Node * right;
    Node(int  data_, Node * left_, Node * right_)
    {
        data = data_;
        left = left_;
        right = right_;
    }
};

void ReversePrint(Node * from, Node * to)
{
    if (from == to)
    {
        cout << from->data << " ";
        return;
    }
    ReversePrint(from->right, to);
    cout << from->data << " ";
}

void  PostOrderMorris(Node * root)
{
    Node * dummy = new Node(-1, root, nullptr);  // 一个虚假根结点
    Node * cur = dummy;
    Node * pre = nullptr;
  
    while (cur)
    {
        if (cur->left == nullptr)  // 步骤 1
            cur = cur->right;
        else
        {
            pre = cur->left;
            while (pre->right && pre->right != cur)  // 步骤 2,找到 cur 的前驱结点
                pre = pre->right;

            if (pre->right == nullptr)  // 步骤 2.1,cur 未被访问,将 cur 结点作为其前驱结点的右孩子
            {
                pre->right = cur;
                cur = cur->left;
            }
            else  // 步骤 2.2,cur 已被访问,恢复树的原有结构,更改 right 指针
            {
                pre->right = nullptr;
                ReversePrint(cur->left, pre);
                cur = cur->right;
            }
        }
    }
}

dummy 用的非常巧妙,建议读者配合上面的图模拟下算法流程。

13 二叉树前序中序推后序

方式序列
前序[1 2 4 7 3 5 8 9 6]
中序[4 7 2 1 8 5 9 3 6]
后序[7 4 2 8 9 5 6 3 1]

以上面图表为例,步骤如下:

  1. 根据前序可知根结点为1;
  2. 根据中序可知 4 7 2 为根结点 1 的左子树和 8 5 9 3 6 为根结点 1 的右子树;
  3. 递归实现,把 4 7 2 当做新的一棵树和 8 5 9 3 6 也当做新的一棵树;
  4. 在递归的过程中输出后序。
/* 前序遍历和中序遍历结果以长度为 n 的数组存储,pos1 为前序数组下标,pos2 为后序下标 */

int pre_order_arry[n];
int in_order_arry[n];

void PrintPostOrder(int pos1, int pos2, int n)
{
    if (n == 1)
    {
        cout << pre_order_arry[pos1];
        return;
    }
    if (n == 0)
        return;
  
    int i = 0;
    for (; pre_order_arry[pos1] != in_order_arry[pos2 + i]; i++)
        ;
  
    PrintPostOrder(pos1 + 1, pos2, i);
    PrintPostOrder(pos1 + i + 1, pos2 + i + 1, n - i - 1);
    cout << pre_order_arry[pos1];
}

当然我们也可以根据前序和中序构造出二叉树,进而求出后序。

/* 该函数返回二叉树的根结点 */
Node * Create(int pos1, int pos2, int n)
{
    Node * p = nullptr;
  
    for (int i = 0; i < n; i++)
    {
        if (pre_order_arry[pos1] == in_order_arry[pos2 + i])
        {
            p = new Node(pre_order_arry[pos1]);
            p->left = Create(pos1 + 1, pos2, i);
            p->right = Create(pos1 + i + 1, pos2 + i + 1, n - i - 1);
            return p;
        }
    }
  
    return p;
}

14 判断二叉树是不是完全二叉树

若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树(Complete Binary Tree)。如下图:

首先若一个结点只有右孩子,肯定不是完全二叉树;其次若只有左孩子或没有孩子,那么接下来的所有结点肯定都没有孩子,否则就不是完全二叉树,因此设置 flag 标记变量。

bool IsCBT(Node * node)
{
    bool flag = false;
    queue<Node*> Q;
    Q.push(node);
  
    while (!Q.empty())
    {
        Node * p = Q.front();
        Q.pop();
      
        if (flag)
        {
            if (p->left || p->right)
                return false;
        }
        else
        {
            if (p->left && p->right)
            {
                Q.push(p->left);
                Q.push(p->right);
            }
            else if (p->right)  // 只有右结点
                return false;
            else if (p->left)   // 只有左结点
            {
                Q.push(p->left);
                flag = true;
            }
            else  // 没有结点
                flag = true;
        }
    }
  
    return true;
}

15 判断是否是二叉查找树的后序遍历结果

在后续遍历得到的序列中,最后一个元素为树的根结点。从头开始扫描这个序列,比根结点小的元素都应该位于序列的左半部分;从第一个大于跟结点开始到跟结点前面的一个元素为止,所有元素都应该大于跟结点,因为这部分元素对应的是树的右子树。根据这样的划分,把序列划分为左右两部分,我们递归地确认序列的左、右两部分是不是都是二元查找树。

int array[n];  // 长度为 n 的序列,注意 begin 和 end 遵循的是左闭右闭原则

bool IsSequenceOfBST(int begin, int end)
{
    if (end - begin <= 0)
        return true;
  
    int root_data = array[end];  // 数组尾元素为根结点
  
    int i = begin;
    for (; array[i] < root_data; i++) // 取得左子树
        ;
  
    int j = i;
    for (; j < end; j++)
        if (array[j] < root_data)  // 此时右子树应该都大于根结点;若存在小于,直接 return false
            return false;
  
    return IsSequenceOfBST(begin, i - 1) && IsSequenceOfBST(i, end - 1);  // 左右子树是否都满足
}

16 给定一个二叉查找树中的结点(存在一个指向父亲结点的指针),找出在中序遍历下它的后继和前驱

一棵二叉查找树的中序遍历序列,正好是升序序列。假如根结点的父结点为 nullptr,则:

  1. 如果当前结点有右孩子,则后继结点为这个右孩子的最左孩子;
  2. 如果当前结点没有右孩子;
    2.1. 当前结点为根结点,返回 nullptr;
    2.2. 当前结点只是个普通结点,也就是存在父结点;
      2.2.1. 当前结点是父亲结点的左孩子,则父亲结点就是后继结点;
      2.2.2. 当前结点是父亲结点的右孩子,沿着父亲结点往上走,直到 n-1 代祖先是 n 代祖先的左孩子,则后继为 n 代祖先或遍历到根结点也没找到符合的,则当前结点就是中序遍历的最后一个结点,返回 nullptr。
/* 求后继结点 */
Node * Increment(Node * node)
{
    if (node->right)  // 步骤 1
    {
        node = node->right;
        while (node->left)
            node = node->left;
        return node;
    }
    else  // 步骤 2
    {
        if (node->parent == nullptr)  // 步骤 2.1
            return nullptr;
        Node * p = node->parent;  // 步骤 2.2
        if (p->left == node)  // 步骤 2.2.1
            return p;
        else  // 步骤 2.2.2
        {
            while (p->right == node)
            {
                node = p;
                p = p->parent;
                if (p == nullptr)
                    return nullptr;
            }
            return p;
        }
    }
}

仔细观察上述代码,总觉得有点啰嗦。比如,过多的 return,步骤 2 的层次太多。综合考虑所有情况,改进代码如下:

Node * Increment(Node * node)
{
    if (node->right)
    {
        node = node->right;
        while (node->left)
            node = node->left;
    }
    else
    {
        Node * p = node->parent;
        while (p && p->right == node)
        {
            node = p;
            p = p->parent;
        }
        node = p;
    }
  
    return node;
}

上述的代码是基于结点有 parent 指针的,若题意要求没有 parent 呢?网上也有人给出了答案,个人觉得没有什么价值,有兴趣的朋友可以到这里查看。

而求前驱结点的话,只需把上述代码的 left 与 right 互调即可,很简单。

17 二分查找树转化为排序的循环双链表

二分查找树的中序遍历即为升序排列,问题就在于如何在遍历的时候更改指针的指向。一种简单的方法时,遍历二分查找树,将遍历的结果放在一个数组中,之后再把该数组转化为双链表。如果题目要求只能使用 $O(1)$ 内存,则只能在遍历的同时构建双链表,即进行指针的替换。

我们需要用递归的方法来解决,假定每个递归调用都会返回构建好的双链表,可把问题分解为左右两个子树。由于左右子树都已经是有序的,当前结点作为中间的一个结点,把左右子树得到的链表连接起来即可。

/* 合并两个 a, b 两个循环双向链表 */
Node * Append(Node * a, Node * b)
{
    if (a == nullptr) return b;
    if (b == nullptr) return a;

    // 分别得到两个链表的最后一个元素
    Node * a_last = a->left;
    Node * b_last = b->left;

    // 将两个链表头尾相连  
    a_last->right = b;
    b->left = a_last;

    a->left = b_last;
    b_last->right = a;

    return a;
}

/* 递归的解决二叉树转换为双链表 */
Node * TreeToList(Node * node)
{
    if (node == nullptr) return nullptr;

    // 递归解决子树
    Node * left_list = TreeToList(node->left);
    Node * right_list = TreeToList(node->right);

    // 把根结点转换为一个结点的双链表,方便后面的链表合并  
    node->left = node;
    node->right = node;

    // 合并之后即为升序排列
    left_list = Append(left_list, node);
    left_list = Append(left_list, right_list);

    return left_list;
}

18 有序链表转化为平衡的二分查找树(Binary Search Tree)

我们可以采用自顶向下的方法。先找到中间结点作为根结点,然后递归左右两部分。所以我们需要先找到中间结点,对于单链表来说,必须要遍历一边,可以使用快慢指针加快查找速度。

struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode(int data_) { data = data_; left = right = nullptr; }
};

struct ListNode
{
    int data;
    ListNode * next;
    ListNode(int data_) { data = data_; next = nullptr; }
};

TreeNode * SortedListToBST(ListNode *  list_node)
{
    if (!list_node) return nullptr;
    if (!list_node->next) return (new TreeNode(list_node->data));

    // 用快慢指针找到中间结点  
    ListNode * pre_slow = nullptr;  // 记录慢指针的前一个结点
    ListNode * slow = list_node;    // 慢指针
    ListNode * fast = list_node;    // 快指针
    while (fast && fast->next)
    {
        pre_slow = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    TreeNode * mid = new TreeNode(slow->data);

    // 分别递归左右两部分
    if (pre_slow)
    {
        pre_slow->next = nullptr;
        mid->left = SortedListToBST(list_node);
    }
    mid->right = SortedListToBST(slow->next);

    return mid;
}

由 $f(n)=2f(\frac n2)+\frac n2$ 得,所以上述算法的时间复杂度为 $O(nlogn)$。

不妨换个思路,采用自底向上的方法:

TreeNode * SortedListToBSTRec(ListNode *& list, int start, int end)
{
    if (start > end) return nullptr;

    int mid = start + (end - start) / 2;
    TreeNode * left_child = SortedListToBSTRec(list, start, mid - 1);  // 注意此处传入的是引用
    TreeNode * parent = new TreeNode(list->data);
    parent->left = left_child;
    list = list->next;
    parent->right = SortedListToBSTRec(list, mid + 1, end);
    return parent;
}

TreeNode * SortedListToBST(ListNode * node)
{
    int n = 0;
    ListNode * p = node;
    while (p)
    {
        n++;
        p = p->next;
    }
  
    return SortedListToBSTRec(node, 0, n - 1);
}

如此,时间复杂度降为 $O(n)$。

19 判断是否是二叉查找树

我们假定二叉树没有重复元素,即对于每个结点,其左右孩子都是严格的小于和大于。

下面给出两个方法:

方法 1:

bool IsBST(Node * node, int min, int max)
{
    if (node == nullptr)
        return true;
    if (node->data <= min || node->data >= max)
        return false;
  
    return IsBST(node->left, min, node->data) && IsBST(node->right, node->data, max);
}

IsBST(node, INT_MIN, INT_MAX);

方法 2:

利用二叉查找树中序遍历时元素递增来判断。

bool IsBST(Node * node)
{
    static int pre = INT_MIN;

    if (node == nullptr)
        return true;
        
    if (!IsBST(node->left))
        return false;
        
    if (node->data < pre)
        return false;
    pre = node->data;
    
    return IsBST(node->right);
}

一:背景

线索二叉树的定义为:一个二叉树通过如下的方法“穿起来”:所有应该为空的右孩子指针指向该结点在中序序列中的后继,所有应该为空的左孩子指针指向该结点的中序序列的前驱。

那么在有 N 个结点的二叉树中共有 N+1 个空指针,这些空指针就叫做“线索”。(提示:在一个有 N 个结点的二叉树中,每个结点有 2 个指针,所以一共有 2N 个指针,将这 N 个结点连接起来需要 N-1 条线,即使用了 N-1 个指针。所以剩下 2N-(N-1)=N+1 个空指针。)

那线索二叉树有何用处呢?由于巧妙地利用了空指针,所以它可以快速地查找到二叉树中某结点的前驱和后继。接下来具体介绍这个数据结构。

在进行下文之前,约定如下:

struct Node
{
    bool left_thread;
    bool right_thread;
    char data;
    Node * left;
    Node * right;

    Node()
    {
        left_thread = right_thread = false;
        data = 0;
        left = right = nullptr;
    }
};

class ThreadedBinaryTree
{
public:
    ThreadedBinaryTree();
    ~ThreadedBinaryTree();
    void formLoop();                         // 构环
    void in_order_print();                   // 中序遍历
private:
    Node * create();
    void destroy(Node * node);
    void threaded(Node * cur, Node *& pre);  // 线索化
    Node * get_successor(Node * node);       // 返回后继结点
    Node * get_precursor(Node * node);       // 返回前驱结点
private:
    Node * header;  // 头结点
    Node * root;    // 二叉树根结点
};

请注意,在决定 left 是指向左孩子还是前驱,right 是指向右孩子还是后继,我们是需要一个区分标志的。因此我们在 Node 结构体中增设两个布尔变量 left_thread 和 right_thread,其中:
(1):left_thread 为 true 时指向前驱,为 false 时指向该结点的左子树;
(2):right_thread 为true 时指向后继,为 false 时指向该结点的右子树。

二:具体实现与代码分析

2.1 构造二叉树

ThreadedBinaryTree::ThreadedBinaryTree()
{
    header = new Node;
    root = create();
}

Node * ThreadedBinaryTree::create()
{
    Node * p = nullptr;
    char ch;
    cin >> ch;
  
    if (ch == '.')  // 结束输入
        p = nullptr;
    else
    {
        p = new Node;
        p->data = ch;
        p->left = create();
        p->right = create();
    }
  
    return p;
}

2.2 线索化及二叉树构环

void ThreadedBinaryTree::threaded(Node * cur, Node *& pre)
{
    if (cur == nullptr)
        return;
    else
    {
        // 按照中序遍历方向,先处理左子树
        threaded(cur->left, pre);

        // 再处理当前结点
        if (cur->left == nullptr)
        {
            cur->left_thread = true;
            cur->left = pre;
        }
        if (cur->right == nullptr)
            cur->right_thread = true;
        if (pre->right_thread)
            pre->right = cur;
        pre = cur;

        // 最后处理右子树
        threaded(cur->right, pre);
    }
}

void ThreadedBinaryTree::formLoop()
{
    header = new Node;  // 创建头结点,并完成初始化
    header->left_thread = true;
    header->right_thread = true;
    header->left = header->right = header;

    Node * pre = header;  // 记录中序遍历的前一个结点
    threaded(root, pre);  // 进行线索化

    pre->right_thread = true;  // 线索化完后,把中序遍历的最后一个结点即 pre,指向 header
    pre->right = header;
    header->left = pre;  // 注意,header 的左指针指向中序遍历的最后一个
}

header 结点的作用就是把线索化后的二叉树串起来,形成一个环。header 的左孩子指向中序遍历序列的最后一个结点,右孩子指向中序遍历序列的第一个结点,如下图:

2.3 后继和前驱

Node * ThreadedBinaryTree::get_successor(Node * node)
{
    if (node->right_thread)
        return node->right;
  
    Node * p = node->right;
    while (p->left_thread == false)  // 已线索化,故此处只能用 left_thread 来判断左子树的情况
        p = p->left;
  
    return p;
}

Node * ThreadedBinaryTree::get_precursor(Node * node)
{
    if (node->left_thread)
        return node->left;
  
    Node * p = node->left;
    while (p->right_thread == false)  // 已线索化,故此处只能用 right_thread 来判断右子树的情况
        p = p->right;
  
    return p;
}

2.4 中序遍历

void ThreadedBinaryTree::in_order_print()
{
    cout << "中序遍历为:";
    Node * p = header->right;  // header 的右结点指向二叉树中序遍历的第一个结点
  
    while (p != header)
    {
        cout << p->data << " ";
        p = get_successor(p);
    }
  
    cout << endl;
}

三:完整代码

#include <iostream>

using namespace std;

struct Node
{
    bool left_thread;
    bool right_thread;
    char data;
    Node * left;
    Node * right;

    Node()
    {
        left_thread = right_thread = false;
        data = 0;
        left = right = nullptr;
    }
};

class ThreadedBinaryTree
{
public:
    ThreadedBinaryTree();
    ~ThreadedBinaryTree();
    void formLoop();                         // 构环
    void in_order_print();                   // 中序遍历
private:
    Node * create();
    void destroy(Node * node);
    void threaded(Node * cur, Node *& pre);  // 线索化
    Node * get_successor(Node * node);       // 返回后继结点
    Node * get_precursor(Node * node);       // 返回前驱结点
private:
    Node * header;  // 头结点
    Node * root;    // 二叉树根结点
};

int main()
{

    ThreadedBinaryTree my_tree;
    my_tree.formLoop();
    my_tree.in_order_print();

    return 0;
}

ThreadedBinaryTree::ThreadedBinaryTree()
{
    header = new Node;
    root = create();
}

ThreadedBinaryTree::~ThreadedBinaryTree()
{
    destroy(root);
    delete header;
    header = root = nullptr;
}

Node * ThreadedBinaryTree::create()
{
    Node * p = nullptr;
    char ch;
    cin >> ch;

    if (ch == '.')  // 结束输入
        p = nullptr;
    else
    {
        p = new Node;
        p->data = ch;
        p->left = create();
        p->right = create();
    }

    return p;
}

void ThreadedBinaryTree::destroy(Node * node)
{
    if (node == nullptr)
        return;

    if (!node->left_thread)
        destroy(node->left);
    if (!node->right_thread)
        destroy(node->right);

    delete node;
}

/* pre 是 cur 的中序遍历序列中的前一个结点 */
void ThreadedBinaryTree::threaded(Node * cur, Node *& pre)
{
    if (cur == nullptr)
        return;
    else
    {
        // 按照中序遍历方向,先处理左子树
        threaded(cur->left, pre);

        // 再处理当前结点
        if (cur->left == nullptr)
        {
            cur->left_thread = true;
            cur->left = pre;
        }
        if (cur->right == nullptr)
            cur->right_thread = true;
        if (pre->right_thread)
            pre->right = cur;
        pre = cur;

        // 最后处理右子树
        threaded(cur->right, pre);
    }
}

void ThreadedBinaryTree::formLoop()
{
    header->left_thread = true;
    header->right_thread = true;
    header->left = header->right = header;

    Node * pre = header;   // 记录中序遍历的前一个结点
    threaded(root, pre);   // 进行线索化

    pre->right_thread = true;  // 线索化完后,把中序遍历的最后一个结点即 pre,指向 header
    pre->right = header;
    header->left = pre;  // 注意,header 的左指针指向中序遍历的最后一个
}

Node * ThreadedBinaryTree::get_successor(Node * node)
{
    if (node->right_thread)
        return node->right;

    Node * p = node->right;
    while (p->left_thread == false)  // 已线索化,故此处只能用 left_thread 来判断左子树的情况
        p = p->left;

    return p;
}

Node * ThreadedBinaryTree::get_precursor(Node * node)
{
    if (node->left_thread)
        return node->left;

    Node * p = node->left;
    while (p->right_thread == false)  // 已线索化,故此处只能用 right_thread 来判断右子树的情况
        p = p->right;

    return p;
}

void ThreadedBinaryTree::in_order_print()
{
    cout << "中序遍历为:";
    Node * p = header->right;  // header 的右结点指向二叉树中序遍历的第一个结点

    while (p != header)
    {
        cout << p->data << " ";
        p = get_successor(p);
    }

    cout << endl;
}

以(2.2)中的图为例,输入数据及测试结果为:

124.
6.7..
.
35..
.
中序遍历为:4 6 7 2 1 5 3

一:渐近符号

算法复杂度的表示通常用三种渐进符号:$O, Ω, Θ$。我们平时常见的都是第一个,后面两个多见于教科书。下面先介绍下这三种符号的含义和性质。

符号 $O$

$O$,读作“大 O”,非正式来说,$O(g(n))$ 是增长次数小于等于 $g(n)$ 及其常数倍($n$ 趋向于无穷大)的函数集合。

教科书上的定义:如果函数 $f(n)$ 包含在 $O(g(n))$ 中,记作 $f(n)∈O(g(n))$(平时使用为了方便书写,我们通常使用 $f(n)=O(g(n))$ 代替)。它的成立条件是:对于所有足够大的 $n$,$f(n)$ 的上界由 $g(n)$ 的常数倍所确定,也就是说,存在大于 $0$ 的常数 $c$ 和非负整数 $n_0$,使得对于所有的 $n≥n_0$ 来说,$f(n)≤c⋅g(n)$。

下图说明了这个定义:

下面给出几个例子:

$$ \begin{align} n&=O(n^2)\\ 100n+5&=O(n^2)\\ \frac 12n(n-1)&=O(n^2)\\ n^3&≠O(n^2)\\ 0.00001n^3&≠O(n^2) \end{align} $$

符号 $Ω$

$Ω$,读作“omega”,$Ω(g(n))$ 是增长次数大于等于 $g(n)$ 及其常数倍($n$ 趋向于无穷大)的函数集合。

教科书上的定义:如果函数 $f(n)$ 包含在 $Ω(g(n))$中,记作 $f(n)=Ω(g(n))$。它的成立条件是:对于所有足够大的 $n$,$f(n)$ 的下界由 $g(n)$ 的常数倍所确定,也就是说,存在大于 $0$ 的常数 $c$ 和非负整数 $n_0$,使得对于所有的 $n≥n_0$ 来说,$f(n)≥c⋅g(n)$。

下图说明了这个定义:

下面给出几个例子:

$$ \begin{align} n^3&=Ω(n^2)\\ \frac 12n(n-1)&=Ω(n^2)\\ 100n+5&≠Ω(n^2) \end{align} $$

符号 $Θ$

读作“theta”。

教科书上的定义:如果函数 $f(n)$ 包含在 $Θ(g(n))$ 中,记作 $f(n)=Θ(g(n))$。它的成立条件是:对于所有足够大的 $n$,$f(n)$ 的上界和下界由 $g(n)$ 的常数倍所确定,也就是说,存在大于 $0$ 的常数 $c_1, c_2$ 和非负整数 $n_0$,使得对于所有的 $n≥n_0$ 来说,$c_1⋅g(n)≤f(n)≤c_2⋅g(n)$。

下图说明了这个定义:

下面给出几个例子:

$$ \begin{align} \frac 12n(n-1)&=Θ(n^2)\tag{$c_1=\frac 14,c_2=\frac 12,n_0=2$}\\ 6n^3&≠Θ(n^2) \end{align} $$

三种符号的性质

性质 如果 $t_1(n)=O(g_1(n))$ 并且 $t_2(n)=O(g_2(n))$,则

$$ t_1(n)+t_2(n)=O(\max\{g_1(n),g_2(n)\}) $$

上面的公式对于 $Ω$ 和 $Θ$ 符号,同样成立。

证明 增长次数的证明是基于以下简单事实:对于 $4$ 个任意实数 $a_1,b_1,a_2,b_2$,如果 $a_1≤b_1$ 并且 $a_2≤b_2$,则 $a_1+a_2≤2\max\{b_1,b_2\}$。

因为 $t_1(n)=O(g_1(n))$,且存在正常量 $c_1$ 和非负整数 $n_1$,使得对于所有的 $n≥n_1$,有 $t_1(n)≤c_1g_1(n)$。同理,因为 $t_2(n)=O(g_2(n))$,对于所有的 $n≥n_2$,亦有 $t_2(n)≤c_2g_2(n)$。

假设 $c_3=\max\{c_1,c_2\}$ 并且 $n≥\max\{n_1,n_2\}$,就可以利用两个不等式的结论将其相加,得出以下结论:

$$ \begin{align} t_1(n)+t_2(n)&≤c_1g_1(n)+c_2g_2(n)\\ &≤c_3g_1(n)+c_3g_2(n)=c_3[g_1(n)+g_2(n)]\\ &≤c_3⋅2\max\{g_1(n),g_2(n)\} \end{align} $$

也就是说,对于两个连续执行部分组成的算法,它的整体效率是由具有较大增长次数的部分所决定的,即效率较差的部分决定

二:计算复杂度

对于一个普通函数(即非递归函数),其时间复杂度自然易求。下面我们主要谈谈如何求解递归函数的时间复杂度。

递归函数通常会有以下的方程式:

$$ T(n)=aT(\frac nb)+f(n)\tag{2.1} $$

其中,$a≥1,b>1$,且都是常数,$f(n)$ 是渐近正函数。递归式 $(2.1)$ 描述的是这样一种算法的运行时间:它将规模为 $n$ 的问题分解为 $a$ 个子问题,每个子问题规模为 $\frac nb$,其中 $a≥1,b>1$。$a$ 个子问题递归地求解,每个花费时间 $T(\frac nb)$。函数 $f(n)$ 包含了问题分解和子问题解合并的代价。

解决上述方程式常用的方法有两种:主定理分治法

主定理(Master Theorem)

令 $a≥1,b>1$,且都是常数,$f(n)$ 是一个函数,$T(n)$ 是定义在非负整数上的递归式,即:

$$ T(n)=aT(\frac nb)+f(n) $$

其中我们将 $\frac nb$ 解释为 $⌊\frac nb⌋$ 或 $⌈\frac nb⌉$。那么 $T(n)$ 有如下渐近界:

(Case 1)如果 $f(n)=O(n^c)$,其中 $c<log_ba$,则:

$$ T(n)=Θ(n^{log_ba}) $$

(Case 2)如果存在常数 $k≥0$,使 $f(n)=Θ(n^clog^{k}n)$,其中 $c=log_ba$,则:

$$ T(n)=Θ(n^clog^{k+1}n) $$

(Case 3)如果 $f(n)=Ω(n^c)$,其中 $c>log_ba$,并且对某个常数 $k<1$ 和所有足够大的 $n$ 有 $af(\frac nb)≤kf(n)$,则:

$$ T(n)=Θ(f(n)) $$

算法导论已有关于这个定理的证明,篇幅较长,故此处省略,有兴趣的读者可以自己去翻阅下。

分治法

分治法先把给定的实例划分为若干个较小的实例,对每个实例递归求解,然后如果有必要,再把较小实例的解合并成给定实例的一个解。假设所有较小实例的规模都为 $\frac nb$,其中 $a$ 个实例需要实际求解,对于 $n=b^k,k=1,2,3...$,其中 $a≥1,b>1$,得到以下结果:

$$ \begin{align} T(n)&=aT(\frac nb)+f(n)\tag{($2.1$) 递归方程式}\\ T(b^k)&=aT(b^{k-1})+f(b^k)\\\ &=a[aT(b^{k-2})+f(b^{k-1})]+f(b^k)=a^2T(b^{k-2})+af(b^{k-1})+f(b^k)\\ &=a^3T(b^{k-3})+a^2f(b^{k-2})+af(b^{k-1})+f(b^k)\\ &=...\\ &=a^kT(1)+a^{k-1}f(b^1)+a^{k-2}f(b^2)+...+a^0f(b^k)\\ &=a^k[T(1)+\sum_{j=1}^{k} {\frac {f(b^j)}{a^j}}]\tag{2.2.7} \end{align} $$

由于 $a^k=a^{log_bn}=n^{log_ba}$,当 $n=b^k$ 时,对于式 $(2.2.7)$ 我们可以推出下式:

$$ T(n)=n^{log_ba}[T(1)+\sum_{j=1}^{log_bn}{\frac {f(b^j)}{a^j}}]\tag{2.2.8} $$

显然,$T(n)$ 的增长次数取决于常数 $a$ 和 $b$ 的值以及函数 $f(n)$ 的增长次数。

三:常见的定理

以下是常用的的两条定理,它们依旧建立在递归方程式中,即:

$$ T(n)=aT(\frac nb)+f(n)\tag{$a≥1,b>1$} $$

根据以上的方程式有以下两个定理:

定理 1

定理 1 对于 $(2.1)$ 递归方程式,若 $a=1,b>1,f(n)=c,c$ 为某个常数,即:

$$ T(n)=T(\frac nb)+c $$

则:

$$ T(n)=Θ(logn) $$

证明 应用主定理 Case 2,其中 $c=log_ba=log_b1=0$,再使 $k=0$,则 $f(n)=Θ(n^clog^kn)=Θ(1)$,这里的 $f(n)$ 即等于常数 $c$,证明成立。

定理 2

定理 2 对于 $(2.1)$ 递归方程式,若 $a=1,b>1,f(n)=kn+p$,其中 $k>0,p>0$ 且为某个常数(也就是 $f(n)$ 是一个线性直线方程),即:

$$ T(n)=T(\frac nb)+(kn+p)\tag{$b>1,k>0,p$ 为某个常数} $$

则:

$$ T(n)=Θ(n) $$

证明 应用分治法中 $(2.2.8)$:

$$ \begin{align} T(n)&=n^{log_ba}[T(1)+\sum_{j=1}^{log_bn}{\frac {f(b^j)}{a^j}}]\\ &=\sum_{j=1}^{log_bn}{(kb^j+p)}\\ &=plog_bn+\frac {kb}{b-1}(n-1)\tag{$k>0,p>0,b>1$}\\ &<pn+\frac {kb}{b-1}(n-1)\\ &=cn-\frac {kb}{b-1}\tag{$c>0$ 且为某个常数}\\ &=Θ(n) \end{align} $$

证明成立。

四:参考文献

  • 算法设计与分析基础
  • 维基百科. 主定理

一:背景

给定一个主串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,此即串的模式匹配问题。

Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在 1974 年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于 1977 年联合发表。

在继续下面的内容之前,有必要在这里介绍下两个概念:真前缀真后缀

由上图所得, "真前缀"指除了自身以外,一个字符串的全部头部组合;"真后缀"指除了自身以外,一个字符串的全部尾部组合。(网上很多博客,应该说是几乎所有的博客,也包括我以前写的,都是“前缀”。严格来说,“真前缀”和“前缀”是不同的,既然不同,还是不要混为一谈的好!)

二:朴素字符串匹配算法

初遇串的模式匹配问题,我们脑海中的第一反应,就是朴素字符串匹配(即所谓的暴力匹配),代码如下:

/* 字符串下标始于 0 */
int NaiveStringSearch(string S, string P)
{
    int i = 0;    // S 的下标
    int j = 0;    // P 的下标
    int s_len = S.size();
    int p_len = P.size();

    while (i < s_len && j < p_len)
    {
        if (S[i] == P[j])  // 若相等,都前进一步
        {
            i++;
            j++;
        }
        else               // 不相等
        {
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == p_len)        // 匹配成功
        return i - j;

    return -1;
}

暴力匹配的时间复杂度为 $O(nm)$,其中 $n$ 为 S 的长度,$m$ 为 P 的长度。很明显,这样的时间复杂度很难满足我们的需求。

接下来进入正题:时间复杂度为 $Θ(n+m)$ 的 KMP 算法。

三:KMP字符串匹配算法

3.1 算法流程

以下摘自阮一峰的字符串匹配的KMP算法,并作稍微修改。

(1)

首先,主串"BBC ABCDAB ABCDABCDABDE"的第一个字符与模式串"ABCDABD"的第一个字符,进行比较。因为 B 与 A 不匹配,所以模式串后移一位。

(2)

因为 B 与 A 又不匹配,模式串再往后移。

(3)

就这样,直到主串有一个字符,与模式串的第一个字符相同为止。

(4)

接着比较主串和模式串的下一个字符,还是相同。

(5)

直到主串有一个字符,与模式串对应的字符不相同为止。

(6)

这时,最自然的反应是,将模式串整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。

(7)

一个基本事实是,当空格与 D 不匹配时,你其实是已经知道前面六个字符是"ABCDAB"。KMP 算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,而是继续把它向后移,这样就提高了效率。

(8)

i01234567
模式串ABCDABD'\0'
next[i]-10000120

怎么做到这一点呢?可以针对模式串,设置一个跳转数组int next[],这个数组是怎么计算出来的,后面再介绍,这里只要会用就可以了。

(9)

已知空格与 D 不匹配时,前面六个字符"ABCDAB"是匹配的。根据跳转数组可知,不匹配处 D 的 next 值为 2,因此接下来从模式串下标为 2 的位置开始匹配

(10)

因为空格与 C 不匹配,C 处的 next 值为 0,因此接下来模式串从下标为 0 处开始匹配。

(11)

因为空格与 A 不匹配,此处 next 值为 -1,表示模式串的第一个字符就不匹配,那么直接往后移一位。

(12)

逐位比较,直到发现 C 与 D 不匹配。于是,下一步从下标为 2 的地方开始匹配。

(13)

逐位比较,直到模式串的最后一位,发现完全匹配,于是搜索完成。

3.2 next 数组是如何求出的

next 数组的求解基于“真前缀”和“真后缀”,即next[i]等于P[0]...P[i - 1]最长的相同真前后缀的长度(请暂时忽视 i 等于 0 时的情况,下面会有解释)。我们依旧以上述的表格为例,为了方便阅读,我复制在下方了。

i01234567
模式串ABCDABD'\0'
next[ i ]-10000120
  1. i = 0,对于模式串的首字符,我们统一为next[0] = -1
  2. i = 1,前面的字符串为A,其最长相同真前后缀长度为 0,即next[1] = 0
  3. i = 2,前面的字符串为AB,其最长相同真前后缀长度为 0,即next[2] = 0
  4. i = 3,前面的字符串为ABC,其最长相同真前后缀长度为 0,即next[3] = 0
  5. i = 4,前面的字符串为ABCD,其最长相同真前后缀长度为 0,即next[4] = 0
  6. i = 5,前面的字符串为ABCDA,其最长相同真前后缀为A,即next[5] = 1
  7. i = 6,前面的字符串为ABCDAB,其最长相同真前后缀为AB,即next[6] = 2
  8. i = 7,前面的字符串为ABCDABD,其最长相同真前后缀长度为 0,即next[7] = 0

那么,为什么根据最长相同真前后缀的长度就可以实现在不匹配情况下的跳转呢?举个代表性的例子:假如i = 6时不匹配,此时我们是知道其位置前的字符串为ABCDAB,仔细观察这个字符串,首尾都有一个AB,既然在i = 6处的 D 不匹配,我们为何不直接把i = 2处的 C 拿过来继续比较呢,因为都有一个AB啊,而这个AB就是ABCDAB的最长相同真前后缀,其长度 2 正好是跳转的下标位置。

有的读者可能存在疑问,若在i = 5时匹配失败,按照我讲解的思路,此时应该把i = 1处的字符拿过来继续比较,但是这两个位置的字符是一样的啊,都是B,既然一样,拿过来比较不就是无用功了么?其实不是我讲解的有问题,也不是这个算法有问题,而是这个算法还未优化,关于这个问题在下面会详细说明,不过建议读者不要在这里纠结,跳过这个,下面你自然会恍然大悟。

思路如此简单,接下来就是代码实现了,如下:

/* P 为模式串,下标从 0 开始 */
void GetNext(string P, int next[])
{
    int p_len = P.size();
    int i = 0;   // P 的下标
    int j = -1;  
    next[0] = -1;

    while (i < p_len)
    {
        if (j == -1 || P[i] == P[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

一脸懵逼,是不是。。。上述代码就是用来求解模式串中每个位置的next[]值。

下面具体分析,我把代码分为两部分来讲:

(1):i 和 j 的作用是什么?

i 和 j 就像是两个”指针“,一前一后,通过移动它们来找到最长的相同真前后缀。

(2):if...else...语句里做了什么?

假设 i 和 j 的位置如上图,由next[i] = j得,也就是对于位置 i 来说,区段 [0, i - 1] 的最长相同真前后缀分别是 [0, j - 1] 和 [i - j, i - 1],即这两区段内容相同

按照算法流程,if (P[i] == P[j]),则i++; j++; next[i] = j;;若不等,则j = next[j],见下图:

next[j]代表 [0, j - 1] 区段中最长相同真前后缀的长度。如图,用左侧两个椭圆来表示这个最长相同真前后缀,即这两个椭圆代表的区段内容相同;同理,右侧也有相同的两个椭圆。所以 else 语句就是利用第一个椭圆和第四个椭圆内容相同来加快得到 [0, i - 1] 区段的相同真前后缀的长度。

细心的朋友会问 if 语句中j == -1存在的意义是何?第一,程序刚运行时,j 是被初始为 -1,直接进行P[i] == P[j]判断无疑会边界溢出;第二,else 语句中j = next[j],j 是不断后退的,若 j 在后退中被赋值为 -1(也就是j = next[0]),在P[i] == P[j]判断也会边界溢出。综上两点,其意义就是为了特殊边界判断。

四:完整代码

#include <iostream>
#include <string>

using namespace std;

/* P 为模式串,下标从 0 开始 */
void GetNext(string P, int next[])
{
    int p_len = P.size();
    int i = 0;   // P 的下标
    int j = -1;  
    next[0] = -1;

    while (i < p_len)
    {
        if (j == -1 || P[i] == P[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

/* 在 S 中找到 P 第一次出现的位置 */
int KMP(string S, string P, int next[])
{
    GetNext(P, next);

    int i = 0;  // S 的下标
    int j = 0;  // P 的下标
    int s_len = S.size();
    int p_len = P.size();

    while (i < s_len && j < p_len) // 因为末尾 '\0' 的存在,所以不会越界
    {
        if (j == -1 || S[i] == P[j])  // P 的第一个字符不匹配或 S[i] == P[j]
        {
            i++;
            j++;
        }
        else
            j = next[j];  // 当前字符匹配失败,进行跳转
    }

    if (j == p_len)  // 匹配成功
        return i - j;
    
    return -1;
}

int main()
{
    int next[100] = { 0 };

    cout << KMP("bbc abcdab abcdabcdabde", "abcdabd", next) << endl; // 15
    
    return 0;
}

五:KMP优化

i01234567
模式串ABCDABD'\0'
next[i]-10000120

以 3.2 的表格为例(已复制在上方),若在i = 5时匹配失败,按照 3.2 的代码,此时应该把i = 1处的字符拿过来继续比较,但是这两个位置的字符是一样的,都是B,既然一样,拿过来比较不就是无用功了么?这我在 3.2 已经解释过,之所以会这样是因为 KMP 还未优化。那怎么改写就可以解决这个问题呢?很简单。

/* P 为模式串,下标从 0 开始 */
void GetNextval(string P, int nextval[])
{
    int p_len = P.size();
    int i = 0;   // P 的下标
    int j = -1;  
    nextval[0] = -1;

    while (i < p_len)
    {
        if (j == -1 || P[i] == P[j])
        {
            i++;
            j++;
          
            if (P[i] != P[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];  // 既然相同就继续往前找真前缀
        }
        else
            j = nextval[j];
    }
}

六:参考文献

一:背景

给定一个字符串,求出其最长回文子串。例如:

  1. s="abcd",最长回文长度为 1;
  2. s="ababa",最长回文长度为 5;
  3. s="abccb",最长回文长度为 4,即 bccb。

以上问题的传统思路大概是,遍历每一个字符,以该字符为中心向两边查找。其时间复杂度为 $O(n^2)$,效率很差。

1975 年,一个叫 Manacher 的人发明了一个算法,Manacher 算法(中文名:马拉车算法),该算法可以把时间复杂度提升到 $O(n)$。下面来看看马拉车算法是如何工作的。

二:算法过程分析

由于回文分为偶回文(比如 bccb)和奇回文(比如 bcacb),而在处理奇偶问题上会比较繁琐,所以这里我们使用一个技巧,具体做法是:在字符串首尾,及各字符间各插入一个字符(前提这个字符未出现在串里)。

举个例子:s="abbahopxpo",转换为s_new="$#a#b#b#a#h#o#p#x#p#o#"(这里的字符 $ 只是为了防止越界,下面代码会有说明),如此,s 里起初有一个偶回文abba和一个奇回文opxpo,被转换为#a#b#b#a##o#p#x#p#o#,长度都转换成了奇数

定义一个辅助数组int p[],其中p[i]表示以 i 为中心的最长回文的半径,例如:

i012345678910111213141516171819
s_new[i]$#a#b#b#a#h#o#p#x#p#
p[i] 1212521212121214121

可以看出,p[i] - 1正好是原字符串中最长回文串的长度。

接下来的重点就是求解 p 数组,如下图:

设置两个变量,mx 和 id 。mx 代表以 id 为中心的最长回文的右边界,也就是mx = id + p[id]

假设我们现在求p[i],也就是以 i 为中心的最长回文半径,如果i < mx,如上图,那么:

if (i < mx)  
    p[i] = min(p[2 * id - i], mx - i);

2 * id - i为 i 关于 id 的对称点,即上图的 j 点,而p[j]表示以 j 为中心的最长回文半径,因此我们可以利用p[j]来加快查找。

三:代码

#include <iostream>  
#include <cstring>
#include <algorithm>  

using namespace std;

char s[1000];
char s_new[2000];
int p[2000];

int Init()
{
    int len = strlen(s);
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;

    for (int i = 0; i < len; i++)
    {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }

    s_new[j] = '\0';  // 别忘了哦
    
    return j;  // 返回 s_new 的长度
}

int Manacher()
{
    int len = Init();  // 取得新字符串长度并完成向 s_new 的转换
    int max_len = -1;  // 最长回文长度

    int id;
    int mx = 0;

    for (int i = 1; i < len; i++)
    {
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i);  // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
        else
            p[i] = 1;

        while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断,因为左有'$',右有'\0'
            p[i]++;

        // 我们每走一步 i,都要和 mx 比较,我们希望 mx 尽可能的远,这样才能更有机会执行 if (i < mx)这句代码,从而提高效率
        if (mx < i + p[i])
        {
            id = i;
            mx = i + p[i];
        }

        max_len = max(max_len, p[i] - 1);
    }

    return max_len;
}

int main()
{
    while (printf("请输入字符串:\n"))
    {
        scanf("%s", s);
        printf("最长回文长度为 %d\n\n", Manacher());
    }
    return 0;
}

四:算法复杂度分析

文章开头已经提及,Manacher 算法为线性算法,即使最差情况下其时间复杂度亦为 $O(n)$,在进行证明之前,我们还需要更加深入地理解上述算法过程。

根据回文的性质,p[i]的值基于以下三种情况得出:

(1):j 的回文串有一部分在 id 的之外,如下图:

上图中,黑线为 id 的回文,i 与 j 关于 id 对称,红线为 j 的回文。那么根据代码此时p[i] = mx - i,即紫线。那么p[i]还可以更大么?答案是不可能!见下图:

假设右侧新增的紫色部分是p[i]可以增加的部分,那么根据回文的性质,a 等于 d ,也就是说 id 的回文不仅仅是黑线,而是黑线+两条紫线,矛盾,所以假设不成立,故p[i] = mx - i,不可以再增加一分。

(2):j 回文串全部在 id 的内部,如下图:

根据代码,此时p[i] = p[j],那么p[i]还可以更大么?答案亦是不可能!见下图:

假设右侧新增的红色部分是p[i]可以增加的部分,那么根据回文的性质,a 等于 b ,也就是说 j 的回文应该再加上 a 和 b ,矛盾,所以假设不成立,故p[i] = p[j],也不可以再增加一分。

(3):j 回文串左端正好与 id 的回文串左端重合,见下图:

根据代码,此时p[i] = p[j]p[i] = mx - i,并且p[i]还可以继续增加,所以需要

while (s_new[i - p[i]] == s_new[i + p[i]]) 
    p[i]++;

根据(1)(2)(3),很容易推出 Manacher 算法的最坏情况,即为字符串内全是相同字符的时候。在这里我们重点研究 Manacher() 中的 for 语句,推算发现 for 语句内平均访问每个字符 5 次,即时间复杂度为:$T_{worst}(n)=O(n)$。

同理,我们也很容易知道最佳情况下的时间复杂度,即字符串内字符各不相同的时候。推算得平均访问每个字符 4 次,即时间复杂度为:$T_{best}(n)=O(n)$。

综上,Manacher 算法的时间复杂度为 $O(n)$

前面我们说,Dijkstra 算法不能处理存在负权回路的图,其实,如果一个图仅仅存在负权边,那么 Dijkstra 算法也可能是无法处理的,例如下图,若 A 作为源点,在第一轮循环后,B 被标记数组标记,但我们发现在第二轮循环中,B 还可以通过 C 点继续进行更新。

Dijkstra 算法在实际工程项目中可以说是经常使用的,主要是因为其高效又稳定的时间复杂度。当使用二叉堆作优先队列时,时间复杂度为 $O((m+n)logn)$。

Bellman_Ford 算法可以处理存在负权边的图,也可以判断有无负权回路。它的时间复杂度很稳定,但同时也很高,为 $O(nm)$,在一些实际项目中往往无法让人接受。

SPFA 算法和 Bellman_Ford 算法一样,既可以处理存在负权边的图,也可以判断有无负权回路。但与 Dijkstra 和 Bellman_Ford 算法都不同的是,它的时间复杂度很不稳定,最佳时间复杂度为 $O(n)$,最差时间复杂度为 $O(n^3)$。

总结起来就是下面的表格:

时间复杂度是否可以处理负权边是否可以判断负权回路
Dijkstra 算法$O((m+n)logn)$不可以不可以
Bellman_Ford 算法$O(nm)$可以可以
SPFA 算法$[O(n),O(n^3)]$可以可以