堆

   数据结构与算法 / 数据结构 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-树的一些性质：

 
阅读更多  

 树状数组

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

树状数组

一、什么是树状数组

树状数组，其英文是 Binary Indexed Tree（简称 BIT），也称为 二叉索引树/二叉下标树。

  • 树状数组虽然名称后缀是数组，但实际上是一棵由数组实现的树

最基本的树状数组支持 2 种操作：

  • 单点修改：更新数组 nums 中任意单个元素值
  • 区间查询：求数组 nums 中任意区间的元素和
 
阅读更多  

 并查集

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

并查集

一、什么是并查集？

并查集是一种简单的集合表示。

它支持以下 3 种操作：

  • Initial(S)：将集合 S 中的所有元素初始化为一个个单元素集合
  • Union(S, Root1, Root2)：把集合 S 中的子集合 Root2 并入子集合 Root1 中
  • Find(S, x)：查找集合 S 中单元素 x 所在的子集合，并返回子集合的名字
 
阅读更多  

 散列表

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

散列表

一、什么是散列表？

1.1 定义

散列表（Hash Table），也称为哈希表，其定义如下：

  • 散列表是一种能够根据关键字，直接访问到值的数据结构
  • 散列表建立了关键字和存储地址之间的一种直接映射关系

其中，关键字称为 Key，对应的值称为 Value。

因此散列表也可以说是：

 
阅读更多  

 跳表

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

跳表

一、什么是跳表？

跳表，又叫做跳跃表、跳跃列表。

  • 是一种对有序链式线性表的优化
  • 在原始链表的基础上添加了多级索引链表
  • 分为多层，从下往上分别是原始链表、一级索引、二级索引…
  • 搜索时从上往下，实现了类似“二分查找”的功能
 
阅读更多  
  关注我

最新文章

归档

分类

×