อธิบาย 5 ประเภทของไบนารีทรีในโครงสร้างข้อมูล

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

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

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

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

ก่อนจะพูดถึงไบนารีทรีประเภท ต่างๆ เรามาทำความรู้จักกับคำศัพท์ที่ใช้ใน ไบนารีทรีกัน ก่อน

โหนด: มันเก็บค่าข้อมูลในต้นไม้ไบนารี

รูท: โหนดบนสุดในไบนารีทรีเรียกว่ารูทของทรี

ขนาด: หมายถึงจำนวนโหนดในไบนารีทรี

โหนดหลัก: โหนดในไบนารีทรีที่มีลูก

โหนดลูก: เป็นโหนดที่เกิดจากโหนดแม่ที่ย้ายออกจากรูทของไบนารีทรี

โหนดภายใน: เป็นโหนดที่มีลูกอย่างน้อยหนึ่งตัวในไบนารีทรี

Leaf node: เป็นโหนดที่ไม่มีลูกเป็นอีกทางเลือกหนึ่งสำหรับโหนดภายนอก

ความลึกของแผนผังโหนด: คำนวณในบริบทของโหนดหนึ่งๆมันถูกอ้างถึงเป็นจำนวนขอบจากโหนดเฉพาะไปยังรูท

ความยาวพาธภายในของทรี: หมายถึงผลรวมของระดับของโหนดภายในทุกโหนดในไบนารีทรี

ความยาวพาธภายนอกของทรี: ถูกกำหนดเป็นผลรวมของระดับของโหนดภายนอกทุกโหนดในไบนารีทรี

ความสูงของโหนดในต้นไม้: คือจำนวนของขอบจากโหนดเฉพาะไปยังโหนดลีฟที่ลึกที่สุดของไบนารีทรีความสูงของรูตจะมากกว่าโหนดอื่นๆ ในไบนารีทรีเสมอ

ทีนี้เรามาดูรายละเอียดของไบนารีทรี 5 ประเภทกัน

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

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

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

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

คุณต้องเดินทางโหนดทั้งหมดเพื่อตรวจสอบว่าต้นไม้เป็นต้นไม้ไบนารีหรือไม่ รหัสจะส่งกลับเป็น "เท็จ" หากโหนดใดมีลูกหนึ่งคน มันจะส่งคืนค่า "True" หากโหนดทั้งหมดมีลูก 0 หรือ 2 ลูก

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

• จำนวนโหนดปลายสุดเท่ากับจำนวนโหนดภายใน + 1 ตัวอย่างเช่น หากจำนวนโหนดภายในคือ 4 จำนวนโหนดปลายสุดจะเท่ากับ 5
• จำนวนโหนดสูงสุดและจำนวนโหนดในไบนารีทรีเท่ากัน จะแสดงเป็น 2h+1 -1
• จำนวนโหนดขั้นต่ำในไบนารีทรีแบบเต็มคือ 2h-1
• ความสูงต่ำสุดของไบนารีทรีแบบเต็มคือ log 2 (n+1) – 1
• ความสูงสูงสุดของไบนารีทรีแบบเต็มคือ h = (n+1)/2

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

ต้นไม้ไบนารีที่สมบูรณ์แบบเป็นหนึ่งในประเภทของต้นไม้ไบนารี ที่ทุกโหนดต้องมีลูก 0 หรือ 2 และระดับของโหนดแต่ละใบต้องเหมือนกันกล่าวอีกนัยหนึ่งต้นไม้ไบนารีที่สมบูรณ์แบบในโครงสร้างข้อมูล ถูกกำหนดให้เป็นต้นไม้ที่โหนดภายในทั้งหมดมีสองสาขาและโหนดที่ไม่มีสาขา (leaf nodes) อยู่ในระดับเดียวกัน

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

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

3. กรอกไบนารีทรี

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

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

นี่คือคุณสมบัติหลักของไบนารีทรีที่สมบูรณ์:

• จำนวนโหนดสูงสุดคือ 2 ชั่วโมง+1 – 1
• จำนวนโหนดขั้นต่ำคือ 2 ชั่วโมง
• ความสูงต่ำสุดคือ log 2 (n+1) – 1

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

ในต้นไม้ไบนารีที่สมดุล ความสูงของต้นไม้คือ log 2 ของจำนวนโหนดทั้งหมด สมมติว่าความสูงของต้นไม้คือ h และจำนวนโหนดทั้งหมดของต้นไม้คือ n สมการคำนวณความสูงคือ h = log(n) ความสูงที่แตกต่างกันสูงสุดระหว่างแผนผังย่อยด้านขวาและแผนผังย่อยด้านซ้ายต้องเป็น "1"

ความแตกต่างอาจมีค่าอื่นๆ เช่น 0 และ -1 ต้นไม้ไบนารีประเภท นี้ เรียกอีกอย่างว่าต้นไม้ AVLหนึ่งในตัวอย่างที่รู้จักกันดีของต้นไม้ไบนารีที่สมดุลคือต้นไม้สีแดง-ดำ

คุณสามารถใช้รหัสต่อไปนี้เพื่อเรียกใช้ต้นไม้ไบนารีที่สมดุล

โหนดคลาสส่วนตัว {

ค่า int ส่วนตัว;

โหนดส่วนตัวเหลือ;

สิทธิ์โหนดส่วนตัว

}

บูลีนสาธารณะ isBalanced (Node n) {

ถ้า (balancedtreeHeight(n) > -1)

กลับจริง;

กลับเป็นเท็จ;

}

สาธารณะ int สมดุลต้นไม้ความสูง (โหนด n) {

ถ้า (n == null)

กลับ 0;

int h1 = balancetreeHeight(n.right);

int h2 = balancetreeHeight(n.left);

ถ้า (h1 == -1 || h2 == -1)

กลับ -1;

ถ้า (Math.abs(h1 – h2) > 1)

กลับ -1;

ถ้า (h1 > h2)

กลับ h1 + 1;

กลับ h2 + 1;

}

ตรวจสอบโปรแกรม US - Data Science ของเรา

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

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

อ่านบทความยอดนิยมในสหรัฐอเมริกา - วิทยาศาสตร์ข้อมูล

บทสรุป

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

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

เริ่มต้นด้วยการเดินทางการเรียนรู้ด้วยเครื่องของคุณใน upGrad

หากคุณต้องการเรียนรู้ Data Science คุณสามารถติดตาม หลักสูตร Master of Science in Data Science ของ upGrad ได้ หลักสูตร 24 เดือนนี้ให้ความรู้ทักษะต่างๆ เช่น Python, Deploy ML Models, BD processing using Spark, Predictive Analytics & Statistics และ Supervised and Unsupervised ML Models หลักสูตรนี้เหมาะสำหรับผู้บริหารที่มีความทะเยอทะยาน ผู้สำเร็จการศึกษา MBA วิศวกร และผู้เชี่ยวชาญในสาขาต่างๆ

การสำเร็จหลักสูตรนี้จะช่วยให้คุณทำงานเป็น Data Engineer, Big Data Analyst, Machine Learning Engineer และ Data Scientist