204512-53/lecture3

Red-Black Tree (Cont.)

• Tree ใดๆ จะเป็น Red-Black Tree ได้ต้องมีคุณสมบัติ 5 ข้อ ได้แก่

1. โหนดเป็นได้ 2 สี คือ แดง กับ ดำ
2. Root ต้องเป็นสีดำ
3. Leaf ทั้งหมดต้องเป็นสีดำ
4. โหนดสีแดงมีโหนดลูกเป็นสีดำ ทั้ง 2 โหนด
5. จากโหนดใดๆ ไปหา Leaf ที่เป็นลูกหลานของตัวเอง จะต้องมีจำนวนโหนดสีดำเท่ากันหมด

ความสูงของ Red-Black Tree เป็น O(log n)

วิธีแก้ปัญหา เมื่อเพิ่ม Leaf Node เข้าไปใหม่ที่จุดใดจุดหนึ่ง ใน Leaf Node ที่เพิ่มเข้าไปใหม่ เราต้องทำการปรับสมดุลใหม่ โดยการตรวจสอบแล้วเปลี่ยนสีในบางจุดที่ต้องเปลี่ยนให้ตรงกับคุณสมบัติของ Red-Black Tree ทั้ง 5 ข้อไปเรื่อยๆ ไล่ตั้งแต่ Leaf Node ที่ได้ทำการเพิ่มเข้ามาขึ้นไปจนถึง Root

Divide and Conqure

เป็นยุทธศาสตร์ในการแก้ปัญหาด้วยอัลกอริทึมแบบหนึ่ง เช่น ถ้าต้องการหาข้อมูลอันหนึ่ง ให้จิ้มไปที่จุดกึ่งกลาง ถ้าเจอคำตอบก็จบ แต่ถ้าไม่เจอ เราก็เลือกว่าควรจะไปทางมากกว่าหรือน้อยกว่า (เนื่องจาก Binary Search นั้น ข้อมูลได้มีการเรียงกันก่อนอยู่แล้ว)

Concept – ตีเมืองใหญ่ให้เป็นเมืองเล็กก่อน

Review Merge Sort

1. จิ้มไปที่กิ่งกลางจะได้ array 2 ส่วน คือ Array Aขนาด n และ Array B ขนาด m
2. ซึ่ง array แต่ละส่วนจะทำการ Sort ใน Array ของตัวเอง เรียกว่า Merge Sort
3. หลังจากนั้นทำการ เปรียบค่าแต่ละค่า ในแต่ละ Index ระหว่าง array ได้ค่าไหนที่น้อยกว่าก็ทำการ Add เข้าไปใน array ใหม่ ชื่อว่า C และทำไปเรื่อยๆ จนครบ เรียกว่า การ Merge

Algorithm

  เราจะได้อัลกอริทึมในการ Merge โดยให้ k=0, i=1, j=1

  1. While k < n+m 
  2.	 k $\Leftarrow$ k+1
  3.	if A[i] < B[j]
  4.		C[k] $\Leftarrow$ A[i]
  5.		i $\Leftarrow$i+1
  6.	else
  7.		C[k] $\Leftarrow$ B[j]
  8.		j $\Leftarrow$ j+1

Proof

 เราจะพิสูจน์ว่าอัลกอริทึมข้างบนถูกต้อง โดย
  *ถ้า array A เรียงจากน้อยไปหามาก และ
  *ถ้า array B เรียงจากน้อยไปหามาก แล้ว
  *Array C จะเป็น array ที่มาจาก array A และ array B ที่เรียงจากน้อยไปหามาก

Loop Invariants

จาก C[1…k] มีข้อมูลของ A[1…i+1] และ B[1…j-1] และเรียงลำดับ

จะพิสูจน์ว่า array ชุดใหม่ มาจาก

จะได้ว่า Z เป็นค่าใหญ่ที่สุดใน array Aที่ตำแหน่ง i แต่ปัญหาอยู่ที่จะทำอย่างไรให้เห็นว่า Z มีค่ามากที่สุดใน array B ในตำแหน่ง j

จากรูปข้างบนแสดงให้เห็นว่า เงื่อนไขใน Loop Invariants ยังไม่แข็งแกร่งพอ โดยจะเพิ่มเงื่อนไขใหม่ได้เป็น จาก C[1…k] มีข้อมูลของ A[1…i+1] และ B[1…j-1] และเรียงลำดับ (เพิ่ม และข้อมูลทุกตัวใน C[1…k] น้อยกว่าหรือเท่ากับ A[i] และ B[j]

Trick หากเงื่อนไขของ Loop Invariants แรกยังไม่แข็งแกร่งพอ ก็ให้หาเงื่อนไขเพิ่มเติมที่รัดกุมกว่าเดิมใส่เข้าไปจนกว่าจะพิสูจน์ได้ ทำให้ได้ว่าอัลกอริทึมนี้ จะได้ Big O = O(m+n) ซึ่งวนลูปทั้งหมด m+n รอบ ซึ่งหลักๆแล้วเราจะดูที่เวลาการทำงานมากกว่า

Merge Sort Algorithm

  Merge Sort(A) ให้  n = ขนาดของ A                      $\Rightarrow$ ใช้เวลา T(n)
  A(left) $\Leftarrow$ A[1…(n/2)]          	                         $\Rightarrow$ ใช้เวลา O(n)
  A(right) $\Leftarrow$ A[(n+1)/2 …n] 			         $\Rightarrow$ ใช้เวลา O(n)
  
  Assume ว่า n เป็นกำลังของ 2
  
  S(left) $\Leftarrow$ Merge Sort(A(left))	                	 $\Rightarrow$ ใช้เวลา T(n/2)
  S(right) $\Leftarrow$ Merge Sort(A(right))		         $\Rightarrow$ ใช้เวลา T(n/2)
  S $\Leftarrow$ Merge Sort(S(left), S(right))		         $\Rightarrow$ ใช้เวลา O(n)
  Return S

   ให้ T(n) เป็นเวลาการทำงานที่แย่ที่สุด เมื่อ input ขนาด n โดยที่ O(n)+O(n) = O(n) ดังนั้น จะได้ T(n) = 2T(n/2) + O(n)

ปัญหาอยู่ที่อัลกอริทึมนี้ยังผิดอยู่ เพราะเนื่องจากยังไม่มี Base Case จึงไม่รู้ว่าจะต้องเริ่มทำ Loop เมื่อไร โดยในที่นี้ จะให้ Base Case เป็น T(1) = O(1) และให้ T(n) เป็น recurrence แต่เนื่องจาก O(n)+O(n)=O(n) นั้น ค่าคงที่บางส่วนจะหายไป ดังนั้นจึงเปลี่ยน T(n) ใหม่เป็น T(n) <= 2T(n/2) +Cn

Review Quick Sort

เมื่อแยกตัว pivotแล้ว จะได้

เมื่อทำการ Quick Sort แล้ว จะได้

ต่างจาก Merge Sort ตรงที่ Merge Sort จะเริ่มจากจุดกึ่งกลาง แต่ Quick Sort จะต้องเริ่มหาตัว pivot ก่อน

 จะใช้เวลา T(n) = O(n) + T(k) + T(n-k-1) โดยที่ในกรณีที่แย่ที่สุดนั้น จะได้ T(n) = O(n) + T(n-1)

การหาค่า pivot จะง่าย ก็ต่อเมื่อตัว pivot อยู่ตรงกลาง ซึ่งเราจะใช้วิธี Selection หาค่า Median