KMP 算法

   数据结构与算法 / 字符串匹配 17 分钟读完 (大约2557个字)

KMP 算法

KMP 算法是一种字符串匹配算法，可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。

KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，全称是 Knuth-Morris-Pratt 算法。

一、暴力：一次滑一位

最简单的方式就是暴力逐位匹配，比如：

 
阅读更多  

 索引堆

   数据结构与算法 / 数据结构 11 分钟读完 (大约1613个字)

索引堆

一、什么是索引堆？

索引堆（Index Heap）是二叉堆的一个变种，是二叉堆的一种增强。

相比于二叉堆只能访问堆顶元素，索引堆可以通过索引访问堆中的任意元素。

比如下面的索引堆：

1
2
3
4
5
      1(30)      
   /        \   
4(28)       3(16)  
   \         /    
  5(22)    2(12)

除了可以直接访问堆顶元素 30，还可以通过索引访问其他元素：

 
阅读更多  

 堆

   数据结构与算法 / 数据结构 13 分钟读完 (大约1948个字)

堆

一、是什么？

在逻辑意义上，堆是一棵二叉树，类似这样：

1
2
3
4
5
6
7
  大值堆                    小值堆

    30                        14    
 /      \                  /      \ 
28      16                22      16
  \    /                 /       /  
  22  12                24      26

堆的特性：

  • 是一棵二叉树
  • 节点是局部有序的（不像 BST 那样整体有序）

局部有序的意思是：

 
阅读更多  

 红黑树

   数据结构与算法 / 数据结构 43 分钟读完 (大约6433个字)

红黑树

一、什么是红黑树？

红黑树是一棵只有红色节点和黑色节点的平衡二叉搜索树。

其结构类似这样：

1
2
3
4
5
6
7
      b4
   /      \  
  r2      r6
 /  \    /  \
b1  b3  b5  b7
              \
              r9

其中，b 表示黑色，r 表示红色。

1.1 红黑树的特性

在《算法导论》里，红黑树是这样定义的：

 
阅读更多  

 B+树

   数据结构与算法 / 数据结构 1 小时读完 (大约6818个字)

B+树

一、什么是 B+ 树？

B+ 树是 B-树的变种。

其结构类似这样：

1
2
3
4
5
6
7
8
9
10
11
12
                                             ____ ___ ___
                                            | 24 |   |   |
                                                   |
                             --------------------------------------------------------
                             |                                                      |
                       ____ ____ ___                                          ____ ___ ___
                      | 15 | 20 |   |                                        | 33 |   |   | 
                             |                                                      |
        --------------------------------------------                     -----------------------
        |                    |                     |                     |                     |
 ____ ____ ___         ____ ____ ___         ____ ____ ___         ____ ____ ___         ____ ____ ___
| 10 | 12 |   |  <=>  | 15 | 18 |   |  <=>  | 20 | 21 |   |  <=>  | 30 | 31 |   |  <=>  | 34 | 38 |   |

B+ 树和 B-树的主要区别在于：

 
阅读更多  

 B-树

   数据结构与算法 / 数据结构 35 分钟读完 (大约5291个字)

B-树

一、B-树是什么？

B-树是一棵所有叶子节点高度都相同的平衡多叉树。

其结构类似这样：

1
2
3
4
5
6
7
8
9
10
11
12
                                    ____ ___ ___
                                   | 24 |   |   |  
                                          |
                         ---------------------------------------------
                         |                                           |
                   ____ ____ ___                               ____ ___ ___
                  | 15 | 20 |   |                             | 33 |   |   | 
                         |                                           |
        -----------------------------------                 -------------------
        |                |                |                 |                 |
 ____ ____ ___     ____ ___ ___     ____ ____ ___     ____ ____ ___     ____ ___ ___
| 10 | 12 |   |   | 18 |   |   |   | 21 | 23 |   |   | 30 | 31 |   |   | 38 |   |   |

B-树的一些性质：

 
阅读更多  
  关注我

最新文章

归档

分类

×