# 第十一章

# 什么时候向一个二项队列进行连续 M 次撬入的花费少于 2M 个时间单位的时间？

当插入的数量多于之前当前树的数量。

# 设建立一个有 $N=2^k-1$ 个元素的二项队列，交替进行 M 对 Insert 和 DeleteMin 操作。显然，每次操作花费 $0(\log{N})$ 时简。为什么这与插入的 $\Theta (1)$ 摊还时间界不矛盾？

尽管每次插入操作花费 $\log{N}$ , 每次删除操作花费 $2\log{N}$ , 虽然这与线性摊还时间相悖，但当 $N$ 次插入和 $O(N\log{N})$ 后，实际操作时间界和摊还时间界一致。

# 通过给出系列导致一次合并需要 $\Theta(N)$ 时间的操作，证明对于课文中描述的斜堆操作的 $O(\log{N})$ 摊还界不能转换成最坏情形界。

在空斜堆中插入 $N,N+1,N-1,N+2,N-2,N+3,...1,2N$ 的序列时，平均每次操作花费 $\Omega(N)$ 的时间。

# 扩展斜堆以支持具有 $O(\log{N})$ 摊还时间的 DecrcaseKey 操作

实现步骤如下，当插入的值 $value$ 小于堆 $X$ ，我们把 $value$ 从父节点切下来，形成一个新堆 $H_1$ , 过去的 $X$ 成为 $H_2$ , 合并，因为合并操作时间为 $O(\log{N})$ , 所以这是 DecrcaseKey 操作时间为 $O(\log{N})$ 。

# 实现斐波那契堆并比较其与二叉堆在用于 Dikstra 算法时的性能

斐波那契堆源码。

# 证明一次一字形展开的摊还时间多为 $3(R_f(X)-R_i(X))$

一字型的总摊还时间为 $AT_{zig-zig} = 2+R_f(P)+R_f(G)-R_i(X)-R_i(P)-R_i(G)$ 。
因为 $R_f(X)=R_i(G)$ , $R_f(X)>R_f(P)$ , $R_i(X)<R_i(P)$
又因为 $S_i(X)+S_f(G)<S_f(X)$ , 所以化简得
$AT_{zig-zig}<3(R_f(X)-R_i(X))$ 。

# 第十二章

# 编写关于红黑树得删除过程

红黑树删除

	void RBtree_Delete(RedBlackTree T, ElementType Item) {
	if (T->Root == T->NullNode) return;

	// Find the node to be deleted
	RedBlackNode toDelete = T->Root;
	RedBlackNode X = T->NullNode;
	// find the node with value Item
	while (toDelete != T->NullNode && toDelete->Element != Item) {
	if (Item < toDelete->Element)
	toDelete = toDelete->Left;
	else if (Item > toDelete->Element)
	toDelete = toDelete->Right;
	}
	if (toDelete == T->NullNode) {
	printf("%d is not exists\n", Item);
	return ;
	}

	// If there are two children, find the smallest node in the right subtree,
	// replace it, and delete the node directly
	if (toDelete->Left != T->NullNode && toDelete->Right != T->NullNode) {
	RedBlackNode tmp = RBtree_FindMin(T, toDelete->Right);
	// Here only the value is copied, not the color,
	// so as not to destroy the nature of the red-black tree
	Item = toDelete->Element = tmp->Element;
	toDelete = tmp;
	}

	// If there is only one child node (only the left child or only the right child),
	// just use the child node to replace the node position
	// (this judgment statement is also used if there is no child node).
	if (toDelete->Left == T->NullNode) {
	X = toDelete->Right;
	RBtree_Transplant(T, toDelete, toDelete->Right);
	} else if (toDelete->Right == T->NullNode) {
	X = toDelete->Left;
	RBtree_Transplant(T, toDelete, toDelete->Left);
	}

	//Before deleting the node, it is necessary to judge the color of the node:
	//1. if it is red, delete it directly without destroying the red-black tree.
	//2. if it is black, it will destroy the fifth property of the red-black tree after deletion,
	// and the tree needs to be make adjustments.
	if (toDelete->Colors == BLACK)
	RBtree_Delete_Fixup(T, X);
	free(toDelete);
	}

# 写出关于 1-2-3 确定性跳跃表得删除过程

	SkipList_123 SkipList_123_Remove(SkipList_123 L, SkipList_123_ElementType Item) {
	// If 1-2-3 Skip List can not remove
	if (IsEmpty(L))
	return NULL;

	// The current node, the previous node of the current node,
	// start marks the start of each level when the node goes down.
	// If previous finally equal to start means have not advanced toward right on this level.
	// next save the start position of the next level for current node.
	SkipList_123_Postion Current, Previous, Next, tmp;

	Current = L->Down;
	int NodeHeight = 0;
	while (1) { //loop and will return when curent->down == bottom
	Previous = NULL;
	while (Item > Current->Element) { //try advance toward right as far as possible
	Previous = Current;
	Current = Current->Right;
	}
	//NodeHeight will mark if a node is a height 1 node
	if (Current->Element == Item)
	NodeHeight++;

	//if on level 1 try to remove if possible and return
	if (Current->Down == Bottom) {
	if (NodeHeight == 0) {
	L = LowerHeadRemoveHelp(L); //can not find do not need to remove
	return NULL;
	} else { // Need to remove
	if (NodeHeight == 1) { //if node height == 1 just remove it.
	//delete need to consider down fild of the upper level.
	//so swap current and current->right.
	tmp = Current->Right; // to be deleted
	Current->Element = Current->Right->Element;
	Current->Right = tmp->Right;
	free(tmp);
	L = LowerHeadRemoveHelp(L); // Might need to lower the head
	} else {
	//if current node height > 1, swap the key with neighbour than delete the neighbour
	//here swap with left neigbour,notice we must have advaced right on
	//this level otherwise it must be a height 1 node.
	//we will find all the node with key value current->key and modify it
	//to previous->key.
	L = LowerHeadRemoveHelp(L); // need to make sure the sturcture correct first.
	L = FindAndModifyRemoveHelp(L, Current->Element, Previous->Element);
	Previous->Right = Current->Right;
	free(Current);
	}
	return L;
	}
	}

	//on other levels ,not level 1.
	//save the postion to go down on the lower level.
	Next = Current->Down; //the next level will be unchaged when dealing the current level.

	//Note: current->key == current->down->right->key
	// means the gap we want to down is of size only 1.
	if (Current->Element == Current->Down->Right->Element) {
	//the first gap case, consider current gap and the next
	if (Previous == NULL) { //have not advanced on this level
	//if the next gap has 2 or more one level lower element.
	//one element need to lower down,the other one need to raise one level,
	//just swap do not need to delte space.
	if (Current->Right->Element > Current->Right->Down->Right->Element) {
	Current->Element = Current->Right->Down->Element;
	Current->Right->Down = Current->Right->Down->Right;
	} else {
	//one element need to lower down,need to delete space.
	tmp = Current->Right;
	Current->Element = tmp->Element;
	Current->Right = tmp->Right;
	free(tmp);
	}
	} else { //not the first so consider the privious gap and the current
	if (Previous->Element > Previous->Down->Right->Element) {
	tmp = Previous->Down->Right;
	if (tmp->Right->Element != Previous->Element)
	tmp = tmp->Right;
	Previous->Element = tmp->Element;
	Current->Down = tmp->Right;
	} else {
	Previous->Element = Current->Element;
	Previous->Right = Current->Right;
	free(Current);
	}
	}
	}
	Current = Next; //go to the next level (one level lower).
	}
	}

# 使用一个 NullNode 节点标记实现配对堆

配对堆源码。

# 第十一章

# 什么时候向一个二项队列进行连续 M 次撬入的花费少于 2M 个时间单位的时间？

# 设建立一个有N=2k−1N=2^k-1N=2k−1 个元素的二项队列，交替进行 M 对 Insert 和 DeleteMin 操作。显然，每次操作花费0(log⁡N)0(\log{N})0(logN) 时简。为什么这与插入的Θ(1)\Theta (1)Θ(1) 摊还时间界不矛盾？

# 通过给出系列导致一次合并需要Θ(N)\Theta(N)Θ(N) 时间的操作，证明对于课文中描述的斜堆操作的O(log⁡N)O(\log{N})O(logN) 摊还界不能转换成最坏情形界。

# 扩展斜堆以支持具有O(log⁡N)O(\log{N})O(logN) 摊还时间的 DecrcaseKey 操作