算法导论学习笔记

第12章 二叉查找树

查找树search tree

操作：search、minimum、maximum、predecessor、successor、insert和delete

可以用作字典，也可以用作优先队列

二叉查找树 binary search tree

执行基本操作的时间与树的高度成正比。n个节点的完全二叉树，最坏运行时间O(lgn)；n个节点的线性链，最坏运行时间O(n)；一棵随机构造的二叉树的期望高度是O(lgn)，从而操作的平均时间为O(lgn)。

12.1 二叉查找树

中序遍历（即根节点在中间）

【记忆：中序遍历的结果是递增有序的】

INORDER-TREE-WALK(x)
  if x!=NIL
    then INORDER-TREE-WALK(x.left)
    		 print x.key
    		 INORDER-TREE-WALK(x.right)

12.2 查询二叉查找树

TREE-SEARCH(x,k)
  if x = NIL or x.key = k
    then return x
  if k < x.key
    then return TREE-SEARCH(x.left,k)
    else return TREE-SEARCH(x.right,k)

最大关键字元素

TREE-MAXIMUM

沿着节点的right指针，直到NIL

最小关键字元素

TREE-MINIMUM

沿着节点的left指针，直到NIL

中序遍历下的前驱

和后继对称

如果节点x有左子树，返回左子树的TREE-MAXIMUM

如果没有左子树，向上找一个节点，该节点的右孩子是节点x的祖先

中序遍历下的后继

如果节点x有右子树，后继为这个右子树的最小关键字元素 （右子树的最左节点）

如果没有右子树，后继为节点向上寻找，找到某个节点，这个节点的左孩子是节点x的祖先

12.3 插入和删除

插入

沿根节点向下..

删除

1. 如果z没有子女，则将它删除（修改z的父节点，使NIL成为它的子女）
2. 如果z只有一个子女，则删除z（z.parent指向z.xChild）
3. 如果z有两个子女，则删除其后继y（可知，y至多有一个右孩子，否则左孩子比y小，y不会是后继；删除y，y.parent指向y.rightChild），把y的值赋给z

第13章 红黑树

13.1 红黑树的性质

1. 每个节点是红色的，或是黑色的
2. 根节点是黑色的
3. 每个叶子节点（Nil）是黑色的
4. 如果一个节点是红色的，则它的两个子节点是黑色的
5. 对每个节点，从该节点到其子孙节点的所有路径上包含相同个数的黑色节点。（红节点不能有红孩子）（从该节点出发的所有下降路径，有相同的黑节点个数）

13.2 旋转

左旋 x向左下垂

LEFT_ROTATE(T,x)

右旋 x向右上移

RIGHT_ROTATE(T,x)

13.3 插入

先按照二叉查找树插入，节点为红色，再调整颜色和旋转

调整颜色：

z一直指向一个红节点，如果p[z]也是红节点

1. 如果z的叔叔y，是红色

   那么，p[z]和y着黑色，p[p[z]]着红色，z指向p[p[z]]，循环继续

2. 如果叔叔y是黑色

   1. z是右孩子

      将z左旋，z指向z的左孩子，变成下面2的情况

   2. z是左孩子

      p[z]着黑色，p[p[z]]着红色，将p[z]右旋

      此时，z红色，p[z]黑色，退出循环

13.4 删除

先按照二叉查找树删除

如果删除的节点是黑色的，需要调整颜色和旋转