Archive for November, 2007

Red-Black Tree

上周实现了一下RB Tree,其实并不是想象中的那么麻烦(split和join暂缺,主要是模板类结构没规划好,
顺便orz一下它的发明者R.Bayer(发现者?奇怪的是,paper中大都说xx discover了xx算法)。

  1. 每个节点只需要一个bit的用于平衡的额外空间,而AVL需要记录高度。
  2. 每次作Fixup的时候,RBTree的Rotate次数是O(1)的,而AVL是O(lgN)的。
  3. 虽然RBTree作Fixup时Recolor的操作是O(lgN)的,但是其均摊复杂度确是O(1)的!这个意味着,N个插入删除操作的代价是O(N)的。(参见CLRS习题)

不过,ms AVL树更平衡,因为兄弟子树高度差不超过1,而RBTree一棵子树的实际高度可能是其兄弟子树的2倍。

Read Full Post »

A graph can be D+1 edge colored, where D is its maximum vertex degree.
Furthermore, a bipartite can be D edge colored.
The D+1 edge coloring algorithm below can also be considered as a proof.
First, for any bipartite there always exists a maximum match so that
the remaining bipartite’s D drops exact 1, if the match edges are removed.
It’s trivial to prove it by augment path.
So it just implies that bipartite is D edge-colorable.
For any graph G with maximum degree D,
we can divide the vertices of G into two groups V1 and V2
so that the degree of each vertex of induced bipartite G(V1,V2) is at least
half of original degree in G. Then the induced graphs G(V1), G(V2) have maximum
degree floor(D/2) and can be colored with 1+floor(D/2) respectively by induction assumption.
Meanwhile bipartite G(V1,V2) with maximum D-floor(D/2) can be colored with D-floor(D/2) colors.
Sum them up, G can be colored with D+1 colors.

Edge-coloring for bipartite graph.
It’s can be proven that there always exists a  maximum match in which every vertex in the graph
with maximum degree is matched. So just color the edges in the match with same color.

Read Full Post »