204512-53/lecture2

BIG O

• function f(n) = O(g(n)) ถ้าให้ c คือค่าคงที่
• จะได้ f(n) <= c.g(n) โดยที่ n >= n₀

Red-Black Trees

• เป็น Binary tree
• Assume ว่าทุก node จบลงที่ Nil Node(All leaf node is Nil)

เงื่อนไข

• Node ใดๆจะเป็นสีแดงไม่ก็ดำ
• Root เป็นสีดำ
• Leaf เป็นสีดำ
• Node ใดเป็น Red Node Child ของ Node นั้นจะต้องเป็น Black Node
• จาก Node u ใดๆทุกๆ Path จาก Node ดังกล่าวไปยัง Leaf ของมันจะต้องมี Node ที่เป็นสีดำเท่ากันทั้งหมด

Lemma

Red-Black tree ที่มี n internal nodes จะมีความสูงไม่เกิน 2log(n+1)

Proof

นิยาม ที่ Node u ใดๆ bh(u) (black height ของ u) จะเท่ากับจำนวน Black Node จาก u ไป Node Leaf ใดๆ(ไม่นับ u))

Claim

สำหรับ internal node u ใดๆจำนวน internal node ใน sub-tree ใดๆที่ u เป็น rootจะมีค่าไม่น้อยกว่า 2^bh(u) -1

Proof (By induction)

ให้ w = u.left และ h = u.right

     bh(w) ≥ bh(u) – 1

     bh(x) ≥ bh(u) – 1

โดย Induction

     Sub-tree ของ w มี internal node ≥ 2^bh(w) -1 ≥ 2^(bh(u)-1)  -1

     Sub-tree ของ x มี internal node ≥ 2^bh(x) -1 ≥ 2^(bh(u)-1)  -1

ดังนั้น internal node ของ u = 1 + 2^(bh(u)-1) -1 + 2^(bh(u)-1) -1 = 2^bh(u) -1

พิจารณา Red-Black Tree ใดๆสูง h

bh(h) ≥ h/2 (เนื่องจาก Red Node จะต้องตามด้วย Black Node เสมอ)

จะได้ Internal node (n)

     n 	≥ 2^bh(h) -1

     n 	≥ 2^(h/2)-1

     n+1       ≥ 2^(h/2)

     log(n+1)  ≤ h/2

     h	       ≤2log(n+1)