ความแตกต่างที่สำคัญ – Binary Tree vs Binary Search Tree
โครงสร้างข้อมูลเป็นวิธีที่เป็นระบบในการจัดระเบียบข้อมูลเพื่อใช้อย่างมีประสิทธิภาพ การจัดเรียงข้อมูลโดยใช้โครงสร้างข้อมูลควรลดเวลาทำงานหรือเวลาดำเนินการ นอกจากนี้ โครงสร้างข้อมูลควรต้องมีหน่วยความจำขั้นต่ำ บางครั้งสามารถจัดเรียงข้อมูลในโครงสร้างแบบต้นไม้ได้ ต้นไม้แสดงถึงโหนดที่เชื่อมต่อกันด้วยขอบ โหนดบนสุดคือรูท แต่ละโหนดสามารถมีได้สูงสุดสองโหนด เรียกว่าโหนดย่อย โหนดทางด้านซ้ายของโหนดหลักคือโหนดย่อยด้านซ้ายในขณะที่โหนดทางด้านขวาของโหนดหลักคือโหนดที่ถูกต้องBinary Tree และ Binary Search Tree เป็นโครงสร้างข้อมูลสองโครงสร้าง ต้นไม้ไบนารีเป็นโครงสร้างข้อมูลประเภทหนึ่งที่โหนดหลักแต่ละโหนดสามารถมีโหนดย่อยได้ไม่เกินสองโหนด แผนผังการค้นหาแบบไบนารีเป็นแผนผังไบนารีที่โหนดย่อยด้านซ้ายมีเฉพาะโหนดที่มีค่าน้อยกว่าหรือเท่ากับโหนดหลัก และโดยที่โหนดย่อยที่ถูกต้องจะมีเฉพาะโหนดที่มีค่ามากกว่าโหนดหลักเท่านั้น นั่นคือความแตกต่างที่สำคัญ โครงสร้างข้อมูลแบบไบนารีและโครงสร้างการค้นหาแบบไบนารีต่างจากโครงสร้างข้อมูล เช่น อาร์เรย์ ไม่มีขีดจำกัดบนในการจัดเก็บข้อมูล
ไบนารีทรีคืออะไร
เมื่อจัดเรียงข้อมูลในโครงสร้างแบบทรี โหนดที่ด้านบนสุดของทรีจะเรียกว่าโหนดรูท ต้นไม้ทั้งต้นสามารถมีได้เพียงรากเดียว โหนดใดๆ ยกเว้นโหนดรูทจะมีขอบขึ้นไปถึงโหนดหนึ่ง เรียกว่าโหนดหลัก โหนดด้านล่างรหัสหลักเรียกว่าโหนดย่อย โหนดหลักแต่ละโหนดสามารถมีโหนดย่อยได้สูงสุดสองโหนด พวกเขาจะเรียกว่าโหนดลูกด้านซ้ายและโหนดลูกด้านขวาโหนดที่ไม่มีโหนดย่อยเรียกว่าโหนดปลายสุด ไม่มีวิธีเฉพาะในการจัดเรียงข้อมูลในไบนารีทรี มีเส้นทางจากโหนดรูทไปยังแต่ละโหนด
รูปที่ 01: ตัวอย่างไบนารีทรี
ด้านบนเป็นตัวอย่างของไบนารีทรี องค์ประกอบที่ 2 ที่ด้านบนของต้นไม้คือราก แต่ละโหนดมีโหนดสูงสุดสองโหนด หากทรีมีลูปหรือโหนดหนึ่งโหนดมีโหนดมากกว่า 2 โหนด จะไม่สามารถจัดประเภทเป็นไบนารีทรีได้ ในการไปจากโหนดหนึ่งไปอีกโหนดหนึ่ง จะมีเส้นทางเดียวเสมอ โหนดย่อยของโหนดรูท 2 คือ 7 และ 5นอกจากนี้ยังเป็นไปได้ที่โหนดจะไม่มีโหนด แต่โหนดใด ๆ ไม่สามารถมีได้มากกว่าสองโหนด องค์ประกอบที่ถูกต้องของรูทคือ 5 องค์ประกอบที่ 5 คือโหนดหลักสำหรับโหนดย่อย 9 โหนด 4 และ 11 ไม่มีองค์ประกอบย่อย ดังนั้นจึงเป็นโหนดลีฟ
ไบนารีทรีใช้สำหรับจัดเก็บข้อมูลตามลำดับชั้น คล้ายกับโครงสร้างไฟล์ของคอมพิวเตอร์ โครงสร้างข้อมูลเช่นอาร์เรย์สามารถจัดเก็บข้อมูลจำนวนหนึ่งได้ แต่ในไบนารีทรี ไม่มีการจำกัดจำนวนของโหนด
Binary Search Tree คืออะไร
แผนผังการค้นหาแบบไบนารีคือโครงสร้างข้อมูลแบบไบนารีทรี คล้ายกับไบนารีทรี ต้นไม้การค้นหาแบบไบนารียังสามารถมีได้สองโหนด โหนดใดๆ ยกเว้นโหนดรูทจะมีขอบขึ้นไปถึงโหนดหนึ่ง เรียกว่าโหนดหลัก โหนดด้านล่างที่เชื่อมต่อโดยขอบด้านล่างเรียกว่าโหนดย่อย โหนดที่ไม่มีโหนดย่อยเรียกว่าโหนดปลายสุด โหนดหลักแต่ละโหนดสามารถมีได้ไม่เกินสองโหนดมีโหนดย่อยที่อ้างถึงโหนดย่อยด้านซ้ายและโหนดย่อยด้านขวา องค์ประกอบบนสุดเรียกว่าโหนดรูท ลูกด้านซ้ายมีเพียงโหนดที่มีค่าน้อยกว่าหรือเท่ากับโหนดหลัก ลูกที่ถูกต้องมีเพียงโหนดที่มีค่ามากกว่าหรือเท่ากับโหนดหลัก
รูปที่ 02: ตัวอย่าง Binary Search Tree
ธาตุที่ 8 คือธาตุบนสุด ดังนั้นจึงเป็นโหนดรูท ถ้า 3 เป็นโหนดหลัก ดังนั้น 1 และ 6 จะเป็นโหนดย่อย 1 เป็นโหนดชายน์ด้านซ้ายในขณะที่ 6 เป็นโหนดชายน์ด้านขวาลูกด้านซ้ายมีค่าน้อยกว่าหรือเท่ากับโหนดหลัก เมื่อ 3 เป็นโหนดหลัก ด้านซ้ายควรมีองค์ประกอบที่น้อยกว่าหรือเท่ากับ 3 ในตัวอย่างนี้ คือ 1 ลูกที่ถูกต้องมีเพียงโหนดที่มีค่ามากกว่าโหนดหลักเท่านั้น เมื่อ 3 เป็นโหนดหลัก โหนดย่อยที่ถูกต้องควรมีค่ามากกว่า 3 ในตัวอย่างนี้ คือ 6 ในทำนองเดียวกัน มีลำดับที่แน่นอนในการจัดเรียงองค์ประกอบข้อมูลแต่ละองค์ประกอบเป็นแผนผังการค้นหาแบบไบนารี โครงสร้างข้อมูลเป็นวิธีที่มีประสิทธิภาพในการจัดเรียง ดึงข้อมูล และค้นหาข้อมูล
ความคล้ายคลึงกันระหว่างต้นไม้ไบนารีและโครงสร้างการค้นหาไบนารีคืออะไร
- ทั้ง Binary Tree และ Binary Search Tree เป็นโครงสร้างข้อมูลแบบลำดับชั้น
- ทั้ง Binary Tree และ Binary Search Tree มีรูทแล้ว
- ทั้ง Binary Tree และ Binary Search Tree สามารถมีโหนดย่อยได้สูงสุดสองโหนด
ต้นไม้ไบนารีและโครงสร้างการค้นหาไบนารีต่างกันอย่างไร
ต้นไม้ไบนารีเทียบกับต้นไม้ค้นหาไบนารี |
|
| ต้นไม้ไบนารีเป็นโครงสร้างข้อมูลประเภทหนึ่งที่โหนดหลักแต่ละโหนดสามารถมีโหนดย่อยได้สูงสุดสองโหนด | แผนผังการค้นหาแบบไบนารีเป็นทรีไบนารีที่โหนดย่อยด้านซ้ายมีเฉพาะโหนดที่มีค่าน้อยกว่าหรือเท่ากับโหนดหลัก และโดยที่โหนดย่อยที่ถูกต้องจะมีเฉพาะโหนดที่มีค่ามากกว่าโหนดหลัก |
| การจัดเรียงข้อมูล | |
| ไบนารีทรีไม่มีลำดับเฉพาะในการจัดเรียงองค์ประกอบข้อมูล | โครงสร้างการค้นหาแบบไบนารีมีลำดับเฉพาะในการจัดเรียงองค์ประกอบข้อมูล |
| การใช้งาน | |
| ไบนารีทรีถูกใช้เพื่อค้นหาข้อมูลและสารสนเทศอย่างมีประสิทธิภาพในโครงสร้างทรี | ต้นไม้ค้นหาแบบไบนารีใช้สำหรับแทรก ลบ และค้นหาข้อมูล |
สรุป – Binary Tree vs Binary Search Tree
โครงสร้างข้อมูลเป็นวิธีการจัดระเบียบข้อมูล บางครั้งสามารถจัดเรียงข้อมูลในโครงสร้างแบบต้นไม้ได้ สองรายการคือไบนารีทรีและทรีการค้นหาไบนารี บทความนี้กล่าวถึงความแตกต่างระหว่างไบนารีทรีและทรีการค้นหาไบนารี ต้นไม้ไบนารีเป็นโครงสร้างข้อมูลประเภทหนึ่งที่โหนดหลักแต่ละโหนดสามารถมีโหนดย่อยได้ไม่เกินสองโหนด แผนผังการค้นหาแบบไบนารีเป็นแผนผังไบนารีที่โหนดย่อยด้านซ้ายมีเฉพาะโหนดที่มีค่าน้อยกว่าหรือเท่ากับโหนดหลัก และโดยที่โหนดย่อยที่ถูกต้องจะมีเฉพาะโหนดที่มีค่ามากกว่าโหนดหลักเท่านั้น
ดาวน์โหลดไฟล์ PDF ของ Binary Tree กับ Binary Search Tree
คุณสามารถดาวน์โหลดไฟล์ PDF ของบทความนี้และใช้เพื่อวัตถุประสงค์ออฟไลน์ตามหมายเหตุอ้างอิง โปรดดาวน์โหลดไฟล์ PDF ที่นี่: ความแตกต่างระหว่างต้นไม้ไบนารีและต้นไม้การค้นหาไบนารี