อธิบายต้นไม้ไบนารี 5 ประเภท [พร้อมภาพประกอบ]

ในวิทยาการคอมพิวเตอร์ โครงสร้างข้อมูลต่างๆ ช่วยในการจัดเรียงข้อมูลในรูปแบบต่างๆ ในหมู่พวกเขา ต้นไม้มีการใช้กันอย่างแพร่หลายโครงสร้างข้อมูลนามธรรมที่จำลองโครงสร้างต้นไม้แบบลำดับชั้น ต้นไม้มักจะมีค่ารูทและทรีย่อยที่เกิดขึ้นจากโหนดย่อยจากโหนดหลัก ต้นไม้เป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น

โครงสร้างข้อมูลต้นไม้ทั่วไปไม่มีการจำกัดจำนวนโหนดย่อยที่สามารถเก็บได้ อย่างไรก็ตาม นี่ไม่ใช่กรณีของไบนารีทรี บทความนี้จะเรียนรู้เกี่ยวกับโครงสร้างข้อมูลต้นไม้เฉพาะ – ต้นไม้ไบนารีและ ประเภทของต้นไม้ ไบนารี

โครงสร้างข้อมูลต้นไม้ไบนารีคืออะไร?

ต้นไม้ ไบนารี เป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้นแบบต้นไม้ที่มีลูกสูงสุดสองคนสำหรับผู้ปกครองแต่ละคน ทุกโหนดใน ไบนารีทรี มีการอ้างอิงด้านซ้ายและขวาพร้อมกับองค์ประกอบข้อมูล โหนดที่ด้านบนของลำดับชั้นของต้นไม้เรียกว่าโหนดรูท โหนดที่มีโหนดย่อยอื่นคือโหนดหลัก

โหนดหลักมีโหนดย่อยสองโหนด: ลูกด้านซ้ายและโหนดลูกด้านขวา การแฮช ข้อมูลการกำหนดเส้นทางสำหรับการรับส่งข้อมูลเครือข่าย การบีบอัดข้อมูล การเตรียมไบนารีฮีป และทรีการค้นหาแบบไบนารีเป็นแอปพลิเคชันบางตัวที่ใช้ไบนารีทรี

คำศัพท์ที่เกี่ยวข้องกับต้นไม้ไบนารีและประเภทของต้นไม้ไบนารี

• โหนด: มันแสดงถึงจุดสิ้นสุดในต้นไม้
• ราก: โหนดบนสุดของต้นไม้
• พาเรนต์: แต่ละโหนด (นอกเหนือจากรูท) ในทรีที่มีโหนดย่อยอย่างน้อยหนึ่งโหนดเรียกว่าโหนดพาเรนต์
• ลูก: โหนดที่ตรงมาจากโหนดหลักเมื่อย้ายออกจากรูทคือโหนดย่อย
• Leaf Node: นี่คือโหนดภายนอก พวกเขาเป็นโหนดที่ไม่มีลูก
• โหนดภายใน: ตามชื่อที่แนะนำ โหนดภายในเหล่านี้มีโหนดย่อยอย่างน้อยหนึ่งรายการ
• ความลึกของต้นไม้: จำนวนขอบจากโหนดของต้นไม้ถึงรากคือ
• ความสูงของต้นไม้: คือจำนวนขอบจากโหนดถึงใบที่ลึกที่สุด ความสูงของต้นไม้ก็ถือเป็นความสูงของรากด้วย

เนื่องจากคุณคุ้นเคยกับคำศัพท์เฉพาะที่เกี่ยวข้องกับไบนารีทรีและประเภทของไบนารีทรีแล้ว ถึงเวลาทำความเข้าใจ คอมโพเนนต์ทรีไบนารี แล้ว ดูหลักสูตรวิทยาศาสตร์ข้อมูลของเราเพื่อเรียนรู้เชิงลึกเกี่ยวกับโครงสร้างไบนารีและส่วนประกอบ

ส่วนประกอบต้นไม้ไบนารี

มีสาม องค์ประกอบ ท รีไบนารี โหนด ไบนารีทรี ทุก โหนดมีสามองค์ประกอบที่เกี่ยวข้องกัน กลายเป็นแนวคิดที่จำเป็นสำหรับโปรแกรมเมอร์ที่จะเข้าใจ องค์ประกอบไบนารีทรีทั้งสามเหล่านี้:

1. องค์ประกอบข้อมูล
2. ตัวชี้ไปที่ทรีย่อยด้านซ้าย
3. ตัวชี้ไปที่ทรีย่อยด้านขวา

แหล่งที่มา

ส่วนประกอบทรีไบนารี ทั้งสามนี้ เป็นตัวแทนของโหนด ข้อมูลอยู่ตรงกลาง ตัวชี้ด้านซ้ายชี้ไปที่โหนดย่อย สร้างแผนผังย่อยด้านซ้าย ตัวชี้ด้านขวาจะชี้ไปที่โหนดย่อยที่ด้านขวา เพื่อสร้างแผนผังย่อยที่ถูกต้อง

อ่าน: คำถามคาดเดายอดนิยมและวิธีการให้ข้อมูลสำหรับวิทยาศาสตร์ข้อมูล

ประเภทของต้นไม้ไบนารี

ต้นไม้ไบนารี มีหลาย ประเภท และต้นไม้ไบนารีแต่ละ ประเภท มีลักษณะเฉพาะ ต่อไปนี้คือรายละเอียดเกี่ยวกับ ต้นไม้ไบนารีแต่ละประเภท :

1. ต้นไม้ไบนารีเต็ม

เป็นต้นไม้ไบนารีชนิดพิเศษที่มีลูกเป็นศูนย์หรือลูกสองคน หมายความว่าโหนดทั้งหมดในไบนารีทรีนั้นควรมีโหนดย่อยสองโหนดของโหนดหลักหรือโหนดหลักคือโหนดปลายสุดหรือโหนดภายนอก

กล่าวอีกนัยหนึ่ง ต้นไม้ไบนารีแบบเต็มคือไบนารีทรีที่ไม่ซ้ำกัน ซึ่งทุกโหนดยกเว้นโหนดภายนอกมีลูกสองคน เมื่อมันมีลูกคนเดียว ต้นไม้ไบนารีดังกล่าวจะไม่เป็นต้นไม้ไบนารีแบบเต็ม ในที่นี้ปริมาณของโหนดปลายสุดเท่ากับจำนวนโหนดภายในบวกหนึ่งโหนด สมการจะเหมือนกับ L=I+1 โดยที่ L คือจำนวนโหนดปลายสุด และ I คือจำนวนโหนดภายใน

นี่คือโครงสร้างของต้นไม้ไบนารีแบบเต็ม:

2. สมบูรณ์ไบนารีทรี

ต้นไม้ไบนารีที่สมบูรณ์เป็นต้นไม้ไบนารีอีกประเภทหนึ่งที่ระดับทรีทั้งหมดเต็มไปด้วยโหนดทั้งหมด ยกเว้นระดับต่ำสุดของทรี นอกจากนี้ ในระดับสุดท้ายหรือต่ำสุดของไบนารีทรีนี้ ทุกโหนดควรอยู่ทางด้านซ้าย นี่คือโครงสร้างของต้นไม้ไบนารีที่สมบูรณ์:

3. ต้นไม้ไบนารีที่สมบูรณ์แบบ

ต้นไม้ไบนารีได้รับการกล่าวขานว่า 'สมบูรณ์แบบ' หากโหนดภายในทั้งหมดมีลูกสองคนอย่างเคร่งครัด และโหนดภายนอกหรือโหนดปลายสุดทั้งหมดอยู่ที่ระดับเดียวกันหรือความลึกเท่ากันภายในต้นไม้ ต้นไม้ไบนารีที่สมบูรณ์แบบที่มีความสูง 'h' มี 2 ชั่วโมง – 1 โหนด นี่คือโครงสร้างของต้นไม้ไบนารีที่สมบูรณ์แบบ:

4. ต้นไม้ไบนารีที่สมดุล

ต้นไม้ไบนารีจะเรียกว่า 'สมดุล' หากความสูงของต้นไม้เป็น O (logN) โดยที่ 'N' คือจำนวนโหนด ในไบนารีทรีที่สมดุล ความสูงของทรีย่อยด้านซ้ายและด้านขวาของแต่ละโหนดควรแตกต่างกันอย่างน้อยหนึ่งรายการ AVL Tree และ Red-Black Tree เป็นตัวอย่างทั่วไปของโครงสร้างข้อมูลที่สามารถสร้างแผนผังการค้นหาไบนารีที่สมดุล นี่คือตัวอย่างของต้นไม้ไบนารีที่สมดุล:

5. เสื่อมโทรมไบนารีทรี

ต้นไม้ไบนารีกล่าวกันว่าเป็นต้นไม้ไบนารีที่เสื่อมโทรมหรือต้นไม้ไบนารีทางพยาธิวิทยาหากทุกโหนดภายในมีลูกเพียงคนเดียว แผนผังดังกล่าวคล้ายกับรายการเชื่อมโยงที่ชาญฉลาด นี่คือตัวอย่างของไบนารีทรีที่เสื่อมโทรม:

ประโยชน์ของต้นไม้ไบนารี

• การดำเนินการค้นหาในไบนารีทรีนั้นเร็วกว่าเมื่อเทียบกับต้นไม้อื่น
• เพียงสองทางก็เพียงพอที่จะจัดเตรียมองค์ประกอบตามลำดับการเรียงลำดับ
• ง่ายต่อการรับองค์ประกอบสูงสุดและต่ำสุด
• การข้ามผ่านกราฟยังใช้ต้นไม้ไบนารีด้วย
• การแปลงคำต่อท้ายและนิพจน์คำนำหน้าที่แตกต่างกันเป็นไปได้โดยใช้ต้นไม้ไบนารี

อ่านเพิ่มเติม: โครงสร้างการตัดสินใจในการเรียนรู้ของเครื่อง: ฟังก์ชัน การจำแนก ข้อดีและข้อเสีย

บทสรุป

ต้นไม้ไบนารีเป็นหนึ่งในต้นไม้ที่ใช้กันอย่างแพร่หลายมากที่สุดในโครงสร้างข้อมูล ต้นไม้ไบนารี แต่ละ ประเภท มีคุณสมบัติที่เป็นเอกลักษณ์ โครงสร้างข้อมูลเหล่านี้มีข้อกำหนดเฉพาะในวิทยาการคอมพิวเตอร์ประยุกต์ เราหวังว่าบทความนี้เกี่ยวกับประเภทของต้นไม้ไบนารีจะเป็นประโยชน์ upGrad เปิดสอนหลักสูตรต่างๆ ในด้านวิทยาศาสตร์ข้อมูล แมชชีนเลิร์นนิง บิ๊กดาต้า และอื่นๆ

หากคุณอยากเรียนรู้เกี่ยวกับวิทยาศาสตร์ข้อมูล ลองดูโปรแกรม Executive PG ของ IIIT-B & upGrad ใน Data Science ซึ่งสร้างขึ้นสำหรับมืออาชีพที่ทำงานและมีกรณีศึกษาและโครงการมากกว่า 10 รายการ เวิร์กช็อปภาคปฏิบัติจริง การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม 1 -on-1 พร้อมที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ