Jul 28

算法与数据结构学习笔记(4)

1、二叉查找树

  • 时间复杂度(插入、查找、删除):O(log N)(平衡状态) ~ O(N)(不平衡状态)
  • 访问方法:前序、中序、后序遍历法
  • 删除有两个子节点的节点的方法:使用Inorder successor(这个词不知道怎么翻译。。。orz)替换该节点
  • 使用数组存储二叉树:左子节点索引=i * 2 + 1;右子节点索引=i * 2 + 2;父节点索引=(i -1) / 2

2、霍夫曼编码

  • 基本原理:在一段信息中,最常出现的字符使用最少的位(bit)表示,最少出现的字符使用最多的位表示,以达到压缩信息的目的
  • 编码步骤:
    1. 统计信息中各字符出现的次数
    2. 把所有字符放进一个优先队列,以次数为优先级
    3. 从优先队列取出两个元素组成一个二叉树节点,再以两元素的优先级相加作为新的优先级放回优先队列,重复直到队列里只剩下一个元素,该元素即为霍夫曼树
    4. 遍历霍夫曼树建立码表,节点的左叶表示为0,右叶表示为1
    5. 使用码表编码信息
  • 解码步骤:
    1. 定位到霍夫曼树的根部
    2. 逐位读取编码后的信息,遇到0定位到左叶,遇到1定位到右页
    3. 如到达树底部的字符节点,把该字符写入输出,重新定位到树的根部
    4. 重复2、3直到读取完所有信息

3、红黑树

红黑树为一种特殊二叉查找树,可把插入、删除、查找的时间复杂度保持在O(log N)。

性质:

1、所有节点要么是红色,要么是黑色

2、根节点一定是黑色

3、红色节点的子节点是黑色

4、所有从根节点到子节点或空节点(空节点定义为黑色)的路径,必须包含同等数量的黑色节点

在插入及删除节点时将对一些节点进行旋转及改变颜色,以保持4个性质。

节点的旋转:

以节点A为顶点进行左(右)旋转,即使用A的右(左)子节点代替A,A移至新节点的左(右)子节点。如新节点已存在左(右)子节点,则把它移至A的右(左)子节点。

  A          C

  /\          /\

 B C   --〉      A E

   /\         /\

  D E       B D

注:经过旋转后的节点仍然符合二叉查找树的特征

插入步骤:

1、将新节点设置为红色

2、查找插入点

  *)查找时如遇到黑色节点的两个子节点都为红色的情况,则改变这三个节点的颜色(例外情况:如果该节点为根节点,则仍然为黑色),然后修复红红冲突。

3、插入节点,如新节点为根,则把颜色改为黑色

4、插入后,如遇到红红冲突,则进行以下步骤:

  1. 如当前节点为内侧节点(即节点的方向与父节点不同)则进行旋转以转换为外侧节点,继续2
  2. 把祖父节点和父节点(如在2中进行过旋转,则为新节点)的颜色翻转,然后向父节点的反方向旋转

  G          G         N

  /          /          /\

 P   --〉    N    --〉  P G

  \         /

  N       P

 (1)       (2)

注:因为性质1,祖父节点必然存在;因为性质3,其必然为黑色。

删除步骤:

http://en.wikipedia.org/wiki/Red-black_tree#Removal

(不想打了。。。太复杂了。。。orz

Jul 17

算法与数据结构学习笔记(3)

1、归并排序(Merge Sort)

  • 时间复杂度:O(N log N)
  • 空间复杂度:O(N)
  • 比较次数比快速排序少,但移动次数比快速排序多

2、希尔排序(Shell Sort)

  • 时间复杂度:O(N log2 N)
  • 空间复杂度:O(1)
  • 选择好的间隔能极大提高性能,目前已知最好的间隔为:1, 4, 10, 23, 57, 132, 301, 701,(2.3hn-1)

3、快速排序(Quick Sort)

  • 时间复杂度:O(N log N)
  • 空间复杂度:O(1)
  • 通常情况下为最快的通用排序算法之一,但某些时候复杂度会提升到O(N2)
  • 预先排序第一个、中间及最后一个元素能减少复杂度为O(N2)的概率

Update 7.17:

4、基数排序(Radix Sort)

  • 时间复杂度:O(N)(?)
  • 空间复杂度:O(N)
  • 速度很快,但是只能排序数值类型
Jul 04

算法与数据结构学习笔记(2)

1、链表

  • 简单链表
  • 双端链表
  • 双向链表

2、抽象数据类型(ADT)

抽象数据类型描述了数据的储存形式及可对数据实现的操作,其具体实现可以有多种形式。

3、迭代器

迭代器用于遍历数据结构内的数据,并可对其进行某些操作。

Jul 03

算法与数据结构学习笔记(1)

学了4章才想起来做笔记。。。orz

1、无序数组

运算复杂度:

插入:O(1)

删除:O(N)

查找:O(N)

2、有序数组

运算复杂度:

插入:O(N)

删除:O(N)

查找:O(N)(线性搜索),O(log N)(二分搜索)

3、大O表示法(Big O notation,是这样译没错吧囧)

复杂度排序:O(1) < O(log N) < O(N) < O(N log N) < O(N2)

4、二分搜索

运算复杂度:O(log N)

5、简单排序算法

  • 冒泡排序
  • 选择排序
  • 插入排序

运算复杂度:均为O(N2)

空间复杂度:O(1)

效率比较:冒泡 < 选择 < 插入

6、栈、队列

特性:

栈:后入先出(LIFO)

队列:先入先出(FIFO)

 

运算复杂度:插入和删除均为O(1)

7、优先队列

运算复杂度(数组实现):

插入:O(N)(线性搜索),O(log N)(二分搜索)

删除:O(1)

8、逆波兰表达式