ทรีไบนารีในโครงสร้างข้อมูล: คุณสมบัติ ประเภท การเป็นตัวแทน & ประโยชน์

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

ต้นไม้ไบนารีคืออะไร?

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

โหนดทั้งหมดในไบนารีทรีมีสามองค์ประกอบหลัก –

• องค์ประกอบข้อมูล
• การอ้างอิงที่ถูกต้อง
• อ้างอิงซ้าย

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

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

เช็คเอาท์: แนวคิดโครงงานวิทยาศาสตร์ข้อมูลสำหรับผู้เริ่มต้น

คุณสมบัติที่สำคัญของโหนดในไบนารีทรี

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

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

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

เรียนรู้เพิ่มเติม: โครงสร้างข้อมูล & อัลกอริธึมใน Python

ต้นไม้การค้นหาแบบไบนารีคืออะไร

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

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

การเป็นตัวแทนของต้นไม้ไบนารี

1. การเป็นตัวแทนที่เชื่อมโยง

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

ในการเป็นตัวแทนนี้ แต่ละโหนดมีสามส่วนที่แตกต่างกัน –

• ตัวชี้ที่ชี้ไปทางโหนดด้านขวา
• ตัวชี้ที่ชี้ไปทางโหนดด้านซ้าย
• องค์ประกอบข้อมูล

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

2. การแสดงตามลำดับ

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

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

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

1. ต้นไม้ไบนารีแบบเต็ม : ต้นไม้ ไบนารีแบบเต็มคือต้นไม้ไบนารีที่มีโหนดมีลูกสองคนหรือไม่มีเลย กล่าวอีกนัยหนึ่ง ต้นไม้ไบนารีจะกลายเป็นต้นไม้ไบนารีแบบเต็มเมื่อแยกจากใบไม้ โหนดอื่นๆ ทั้งหมดมีลูกสองคน
2. ต้นไม้ไบนารีที่สมบูรณ์ : ต้นไม้ ไบนารีที่สมบูรณ์คือต้นไม้ที่มีระดับที่แตกต่างกันทั้งหมด ข้อยกเว้นเพียงอย่างเดียวคือระดับสุดท้ายซึ่งมีคีย์อยู่ทางด้านซ้าย ไบนารี่ฮีปมักถูกใช้เป็นตัวอย่างของไบนารีทรีที่สมบูรณ์
3. ต้นไม้ไบนารีที่สมบูรณ์แบบ: ต้นไม้ ไบนารีที่สมบูรณ์แบบคือต้นไม้ไบนารีที่มีใบอยู่ในระดับเดียวกันและมีโหนดภายในมีลูกสองคน ตัวอย่างทั่วไปของต้นไม้ไบนารีที่สมบูรณ์แบบคือแผนภูมิต้นไม้ตระกูลบรรพบุรุษ
4. ต้นไม้ไบนารีที่เสื่อมโทรมทางพยาธิวิทยา: ต้นไม้ที่เสื่อมโทรมคือต้นไม้ไบนารีที่มีโหนดภายในมีลูกหนึ่งคน ระดับประสิทธิภาพจะคล้ายกับรายการที่เชื่อมโยง เรียนรู้เพิ่มเติมเกี่ยวกับประเภทของไบนารีทรี

อ่าน: โครงสร้างข้อมูล 6 แบบที่ใช้บ่อยที่สุดใน R

ประโยชน์ของไบนารีทรี

1. วิธีที่เหมาะสมที่สุดในการจัดเก็บข้อมูลตามลำดับชั้น
2. สะท้อนความสัมพันธ์เชิงโครงสร้างที่มีอยู่ในชุดข้อมูลที่กำหนด
3. ทำการแทรกและลบได้เร็วกว่ารายการและอาร์เรย์ที่เชื่อมโยง
4. วิธีที่ยืดหยุ่นในการถือและย้ายข้อมูล
5. ใช้สำหรับเก็บโหนดให้ได้มากที่สุด
6. เร็วกว่ารายการที่เชื่อมโยงและช้ากว่าอาร์เรย์เมื่อเข้าถึงองค์ประกอบ

บทสรุป

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

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