算法与数据结构学习笔记(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

Leave a Reply

Your email address will not be published. Required fields are marked *