ผลต่างระหว่างรุ่นของ "204512-53/lecture2"
(→Proof) |
|||
| แถว 14: | แถว 14: | ||
==Proof== | ==Proof== | ||
นิยาม ที่ Node u ใดๆ bh(u) (black height ของ u) จะเท่ากับจำนวน Black Node จาก u ไป Node Leaf ใดๆ(ไม่นับ u)) | นิยาม ที่ 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 | + | ===Claim=== |
| + | สำหรับ internal node u ใดๆจำนวน internal node ใน sub-tree ใดๆที่ u เป็น rootจะมีค่าไม่น้อยกว่า 2^bh(u) -1 | ||
| − | Proof (By induction) | + | ===Proof (By induction)=== |
ให้ w = u.left และ h = u.right | ให้ w = u.left และ h = u.right | ||
bh(w) ≥ bh(u) – 1 | bh(w) ≥ bh(u) – 1 | ||
bh(x) ≥ bh(u) – 1 | bh(x) ≥ bh(u) – 1 | ||
โดย Induction | โดย 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 | ดังนั้น internal node ของ u = 1 + 2^(bh(u)-1) -1 + 2^(bh(u)-1) -1 = 2^bh(u) -1 | ||
พิจารณา Red-Black Tree ใดๆสูง h | พิจารณา 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) | |
รุ่นแก้ไขเมื่อ 10:56, 6 กรกฎาคม 2553
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)
