Binomial Tree (ต้นไม้ไบโนเมียล) คืออะไร?
Binomial Tree เป็นโครงสร้างข้อมูลแบบต้นไม้ที่มีลำดับ (ordered tree) โดย B₀ ประกอบด้วยโหนดเดียว ส่วน Bₖ ประกอบด้วยสอง Binomial Tree คือ Bₖ₋₁ ที่เชื่อมต่อกัน รากของต้นหนึ่งจะเป็นลูกซ้ายสุดของรากอีกต้นหนึ่ง ใช้ในการวิเคราะห์ทุนหรือหุ้น
โหนดของ Binomial Tree แทนค่าภายใน (intrinsic value) ของสินทรัพย์ ช่วยให้นักลงทุนวิเคราะห์เวลาและค่าที่เหมาะสมสำหรับการลงทุน
Binomial Heap (ฮีปไบโนเมียล) คืออะไร?
Binomial Heap เป็นโครงสร้างข้อมูลที่ประกอบจากการรวมหลาย Binomial Tree เข้าด้วยกัน
คุณสมบัติของ Binomial Heap H:
- Binomial Tree ทุกต้นใน H เป็น heap-ordered (คีย์ของโหนดมากกว่าหรือเท่ากับคีย์ของพาเรนต์)
- มี Binomial Tree ใน H สูงสุด 1 ต้น ที่รากมี degree (องศา) ใดๆ ก็ตาม
ตัวอย่าง Binomial Heap
การแสดงผลในหน่วยความจำของโหนด Binomial Heap
โหนดแต่ละตัวใน Binomial Heap แสดงในหน่วยความจำด้วย 5 ฟิลด์:
- Parent Pointer - เก็บที่อยู่ของโหนดพาเรนต์ เพื่อเชื่อมโยงกับโหนดอื่นในโครงสร้าง
- Key - เก็บข้อมูลหรือคีย์ที่โหนดครอบครอง
- Degree - ระบุองศาหรือระดับของโหนด
- Left Child Pointer - เก็บที่อยู่ของลูกซ้ายสุด
- Sibling Pointer - เก็บที่อยู่ของพี่น้อง (sibling) ต่อไป
ตัวอย่างการแสดงผล
1. โหนดเดี่ยว (Single node)
2. โหนดพาเรนต์และลูก (Parent and child)
3. โหนดพี่น้อง (Sibling nodes)
