恋上数据结构与算法(精简版)

1,559 阅读8分钟

标题解析

通过标题就知道当前文档的学习来自哪里,挺棒的学习资源,学习之后受益匪浅。
Pascal 之父 Nicklaus Wirth 凭借一个公式获得了图灵奖:算法 + 数据结构 = 程序。

0x00 复杂度

用于衡量其算法:正确性、可读性、健壮性(对不合理输入的反应能力与处理能力)。
时间复杂度(time complexity):估算程序指令的执行次数(执行时间)
空间复杂度(space complexity):估算所需占用的存储空间

所以我们在敲代码的时候,需要有复杂度的考虑,不以结果而结果。比如 斐波那契数列 的算法可以是以下三种实现:

/// 斐波那契数列 -> 递归
func fib_recarsive(data:Int) -> Int {
    if data <= 1 {
        return data
    }
    return fib_recarsive(data: (data-1)) + fib_recarsive(data: (data-2))
}

/// 斐波那契数列 -> 优化
func fib_optimize(data:Int) -> Int {
    if data <= 1 {
        return data
    }
    
    var first = 0
    var second = 1
    for _ in 0...(data-2) {
        let sum = first + second
        first = second
        second = sum
    }
    
    return second
}

/// 斐波那契数列 -> 优化 (减少了一个变量的开销)
func fib_optimize_best(data:Int) -> Int {
    if data <= 1 {
        return data
    }
    
    var first = 0
    var second = 1
    
    // Swift 可以这么玩
    var data = data
    
    repeat {
        second += first
        first = second - first
        data -= 1
    } while data > 1
    
    return second
}

以上三种方式都能实现 斐波那契数列, 但是其执行效率如下所示:

图中的结论是通过自定义 Instruments 实现,更多细节可以参考:Xcode 中自定义 Instruments

通过图中显示,使用递归是效率最低的,在相同条件下使用了 5.48s,而另外两种实现都不到 1s 的时间。

0x01 动态数组(Array)

数组、一个很常规的线性数据结构。在数组中又分成两种,比如 OC 中有不可变数组与可变数组。这里所谈到的动态数组的实现,类似可变数组。故需要考虑这些方面的实现:

  • 1、元素数量
  • 2、是否为空
  • 3、是否包含
  • 4、设置/添加元素(末尾与指定的 index)
  • 5、删除元素
  • 6、查看与清空元素

在实现动态数组的过程中,需要考虑的是 扩/缩容 与及 添加/删除时元素位置移动 的问题。

0x02 链表(Link)

与数组类似、也是线性数据结构,其优点是节省内存空间、不像数组需要有预留内存空间。

  • 1、单项链表
  • 2、双向链表 相关实现接口与动态数组类似。

0x03 栈(Stack)

相对特殊的线性结构,仅在一端(栈顶)进行操作。

  • 1、添加元素:入栈(push)
  • 2、移除元素:出站(pop)、弹出顶端元素
  • 3、获取顶端元素(不出栈):top

原则:后进先出(Last In First Out、LIFO)
内部实现可以借助:链表与动态数组。
应用场景: 浏览器前进/后退、撤销/后退、括号有效性判断、逆波兰表示法、等等。

0x04 队列(Queue)

只能在 头尾 两端进行操作。

  • 1、队尾(rear):添加元素、叫入队(enQueue)
  • 2、对头(front):移除元素、叫出队(deQueue)

原则:先进先出(First In First Out, FIFO)
内部实现可以借助:链表与动态数组。
思考:用栈实现队列,准备两个栈(inStack、outStack)

双端队列(deque = double ended queue): 能在头尾 添加/删除
循环队列: 使用动态数组方可实现,添加一个对头指针(front)。
循环双端队列: 两端可以进行添加/删除的循环队列。

0x05 树

概念(一)

节点、根节点、父节点、子节点、兄弟节点与子树、左子树、右子树。
节点的度(degree):子树的个数
树的度:所有节点度中的最大值
叶子节点(leaf):度为 0 的节点
非叶子节点:度 > 0 的节点

概念(二)

层数(level):根节点在第一层,跟节点的子节点在第二层,以此类推
节点的深度(depth):从跟节点到当前节点的唯一节点总数
节点的高度(height):从当前节点到最远叶子节点的路劲上的节点数
树的深度:所有节点深度中的最大值
树的高度:所有节点高度的最大值
树的深度 = 树的高度

概念(三)

有序树
无需树、也称 自由树
森林

0x06 二叉树(Binary Tree)

特点:有序树、节点的度最大为 2(左子树与右子树)、即使只有一个子树也需要区分左右子树。
真二叉树(Proper Binary Tree): 所有节点的度,要么为 0、要么为 2。
满二叉树(Full Binary Tree): 最后一层节点的度都为 0,其它节点度都为 2。

满二叉树一定是真二叉树,同样高度的二叉树中,满二叉树的节点最多。

完全二叉树(Complete Binary Tree): 对节点从上至下、从左至右开始编号,其所有编号都能与满二叉树对应。

度为 1 的节点只有左子树
度为 1 的节点,要么有 1 个、要么是 0 个
同样节点数量的二叉树、完全二叉树的高度最小
二叉树的高度为 h(h>1),节点数为[2h-1, 2h -1]
总节点数为 n,则:2h-1 ≤ n < 2h,h-1 ≤ \log_2 n < h,h = floor(\log_2 n) + 1
i 为节点编号、i=1 为根节点,如果 i>1,父节点编号为 floor(i/2),如果 2i ≤ 它的左子节点编号为 2i,如果 2i > n 则没有左子节点,如果 2i+1 ≤ n 则右子节点编号为 2i+1,2i+1 > n 则无由子节点
公式:n0 = n2 + 1

遍历(Traversal): 把所有数据结构中的元素都访问一遍。
线性遍历:正序与逆序。
二叉树遍历:
前序(Preorder):根、左、右
中序(Inorder):左、根、右
后序(Postorder):左、右、根
层序(Levelorder):从上至下
二叉树的唯一性:
前序 + 中序
后续 + 中序
两个节点:
前驱节点(predecessor):中序遍历的前一个节点
后继节点(successor):中序遍历的后一个节点

0x07 二叉搜索树(Binary Search Tree)

简称 BST,又名二叉查找、二叉排序树。其特点:
1、任意一个节点的值都大于左子树所有节点的值
2、任意一个节点的值都小于右子树所有节点的值

故此树的节点必须要具有 可比性 。接口设计:
1、size 与 clear
2、添加与删除
3、包含(node 与内容)

0x08 平衡二叉搜索树(Binary Search Tree)

为了防止二叉搜索树退化成 “链表” 的形式,故再来研究一个 平衡二叉搜索树。目的是让二叉搜索树的高度控制到最矮,相比其它二叉树,在修改(添加/删除)节点之后,恢复搜索二叉树,让其更加平衡(Balance),故称为 平衡二叉搜索树,简称 BBST。
经典的平衡二叉搜索树有:AVL 树与红黑树,也称他们为自平衡二叉树。

0x09 AVL 树

一个与之对应的概念,叫平航因子(Balance Factor):某节点的左右子树的高度差。
AV 的特点:

每个节点的平衡因子只可能是 1、0、-1
每个节点的左右子树高度差不超过 1
搜索、添加与删除的时间复杂度度是 O(\log n)

理解的难点是恢复平衡:右旋转、左旋转、左右旋转

0x10 B 树(B-Tree)

是一种平衡的多路(多叉)搜索树、多使用于文件系统、数据库的实现。
特点:

1 个节点可以存储超过 2 个元素,可以拥有超过 2 个子节点
拥有二叉搜索树的一些性质
平衡、每个节点的所有子树高度一致
比较矮

如果这个 B 数中一个节点最多能存储 3 个元素,就是最多有 4 个子树,那称为 4阶B树
4 阶 B 树、也称 2-3-4 树。关于 B 树,相对比较复杂的,主要还是在于恢复平衡,相继引出了 上溢、下溢 的概念。

0x11 红黑树(Red Black Tree)

也称自平衡二叉搜索树、也叫平衡二叉B树,仅看概念就知道这是一颗有颜色的树。
性质:

1、节点的颜色是 RED 或者 BLACK
2、根节点都是 BLACK
3、叶子节点(外部节点、空节点)都是 BLACK
4、RED 节点的子节点都是 BLACK : RED 节点的 parent 都是 BLACK, 根节点到叶子节点的所有路劲上不能有两个连续的 RED 节点
5、从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点

红黑树依旧是在恢复平衡的处理上很复杂,与 4 阶 B 树有着千丝万缕的关系(在研究 红黑树的时候、心中一定要有一点 B 数)。其过程中需要知道的几个概念:
parent:父节点
sibling:兄弟节点
uncle:叔父节点
grand:祖父节点

红黑树的实现很复杂,但是性能方面是相对较优的,应用也比较广泛。比如这些:

  • 1、C++ STL(比如 map、set...)
  • 2、Java 的 TreeMap、TreeSet、HashMap、HashSet
  • 3、Linux 的进度调度
  • 4、Ngix 的 timer 管理