คำถามและคำตอบในการสัมภาษณ์แบบไบนารีทรีที่พบบ่อยที่สุด [สำหรับมือใหม่และผู้มีประสบการณ์]

บทนำ

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

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

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

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

คำถามและคำตอบสัมภาษณ์ต้นไม้ไบนารียอดนิยม

ส่วนต่อไปนี้ประกอบด้วยแคตตาล็อกของคำถามและคำตอบที่คาดหวังตามแนวคิดต้นไม้ไบนารี

1) ใบไม้โหนดคืออะไร?

โหนดใดๆ ในไบนารีทรีหรือทรีที่ไม่มีลูก เรียกว่าโหนดลีฟ

2) โหนดรูทคืออะไร?

โหนดแรกหรือโหนดบนสุดในทรีเรียกว่าโหนดรูท

3) คุณจะหาบรรพบุรุษร่วมที่ต่ำที่สุด (LCA) ของต้นไม้ไบนารีใน Java ได้อย่างไร

ให้เราพิจารณาสองโหนด n1 และ n2 ที่เป็นส่วนหนึ่งของไบนารีทรี

บรรพบุรุษร่วมต่ำสุด (LCA) ของ n1 และ n2 คือบรรพบุรุษร่วมของ n1 และ n2 ซึ่งอยู่ห่างจากรากมากที่สุด

คุณสามารถทำตามวิธีการต่อไปนี้เพื่อค้นหา LCA

1. ก) ค้นหาเส้นทางจากโหนดรูทไปยัง n1 และเก็บไว้ในอาร์เรย์
2. b) ค้นหาเส้นทางจากโหนดรูทไปยัง n2 และเก็บไว้ในอาร์เรย์
3. c) สำรวจทั้งสองเส้นทางจนกว่าค่าจะเท่ากันในอาร์เรย์ทั้งสอง

4) คุณจะตรวจสอบได้อย่างไรว่าไบนารีทรีที่กำหนดเป็นทรีย่อยของไบนารีทรีอื่นหรือไม่

พิจารณาว่าเรามีไบนารีทรี T ตอนนี้เราต้องการตรวจสอบว่าไบนารีทรี S เป็นทรีย่อยของ T หรือไม่

ในการทำเช่นนี้ ก่อนอื่น ให้ลองตรวจสอบว่าคุณพบโหนดใน T ที่อยู่ใน S ด้วยหรือไม่

เมื่อคุณพบโหนดทั่วไปนี้แล้ว ให้ตรวจสอบว่าโหนดต่อไปนี้เป็นส่วนหนึ่งของ S ด้วยหรือไม่

ถ้าใช่ เราสามารถพูดได้อย่างปลอดภัยว่า S เป็นแผนผังย่อยของ T

ต้องอ่าน: แนวคิดและหัวข้อโครงการโครงสร้างข้อมูล

5) คุณหาระยะห่างระหว่างสองโหนดในไบนารีทรีได้อย่างไร?

พิจารณาสองโหนด n1 และ n2 ที่เป็นส่วนหนึ่งของไบนารีทรี

ระยะห่างระหว่าง n1 และ n2 เท่ากับจำนวนขอบขั้นต่ำที่ต้องข้ามผ่านเพื่อไปให้ถึงจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง

สิ่งสำคัญคือต้องสังเกตว่า คุณสำรวจระยะทางที่สั้นที่สุดระหว่างโหนด

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

ต้นไม้การค้นหาแบบไบนารี (BST) เป็นต้นไม้ไบนารีชนิดพิเศษซึ่งแต่ละโหนดภายในมีคีย์ สำหรับแผนผังการค้นหาแบบไบนารี กฎคือ:

1. ก) โหนดสามารถมีคีย์ที่มากกว่าคีย์ทั้งหมดในทรีย่อยด้านซ้ายของโหนด
2. b) โหนดสามารถมีคีย์ที่เล็กกว่าคีย์ทั้งหมดในทรีย่อยด้านขวาของโหนด

ดังนั้น หาก n1 เป็นโหนดที่มีคีย์ 8 ดังนั้นทุกโหนดในทรีย่อยด้านซ้ายของ n1 จะมีคีย์ที่น้อยกว่า 8 และทุกๆ โหนดในทรีย่อยด้านขวาของ n1 จะมีคีย์ที่มากกว่า 8

7) ต้นไม้ที่สมดุลในตัวเองคืออะไร?

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

เพื่อให้ BST มีความสมดุลในตัวเอง เป็นสิ่งสำคัญที่จะต้องปฏิบัติตามกฎของ BST อย่างสม่ำเสมอเพื่อให้ทรีย่อยด้านซ้ายมีคีย์ที่มีมูลค่าต่ำกว่าในขณะที่ทรีย่อยด้านขวามีคีย์ที่มีมูลค่าสูง

ทำได้โดยใช้สองการดำเนินการ:

– หมุนซ้าย

– หมุนขวา

8) ต้นไม้ AVL คืออะไร?

ต้นไม้ AVL ได้รับการตั้งชื่อตามผู้ประดิษฐ์: Adelson, Velski และ Landis ต้นไม้ AVL เป็นต้นไม้ไบนารีที่สร้างสมดุลในตัวเอง ซึ่งจะตรวจสอบความสูงของต้นไม้ย่อยด้านซ้ายและต้นไม้ย่อยด้านขวา และรับรองว่าความแตกต่างไม่เกิน 1 ความแตกต่างนี้เรียกว่าปัจจัยความสมดุล

ดังนั้น BalanceFactor = ความสูง (ทรีย่อยด้านซ้าย) – ความสูง (ทรีย่อยด้านขวา)

หากปัจจัยความสมดุลมากกว่า 1 ต้นไม้จะสมดุลโดยใช้เทคนิคบางอย่างต่อไปนี้:

– หมุนซ้าย

– หมุนขวา

– หมุนซ้าย-ขวา

– หมุนขวา-ขวา

อ่านเพิ่มเติม: การเรียงลำดับในโครงสร้างข้อมูล

9) คุณจะแปลงไบนารีทรีเป็นทรีการค้นหาไบนารีใน Java ได้อย่างไร

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

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

10) คุณจะลบโหนดออกจากแผนผังการค้นหาแบบไบนารีใน Java ได้อย่างไร

การลบสำหรับ BST อาจทำได้ยาก เนื่องจากต้องรักษาคุณสมบัติของมันไว้หลังการดำเนินการ ต่อไปนี้คือกรณีที่เป็นไปได้ทั้งสามกรณี:

1. โหนดที่จะลบคือโหนดปลายสุด
   เพียงแค่ลบโหนด
2. โหนดที่จะลบมีลูกหนึ่งคน

ในกรณีนี้ ให้คัดลอกชายน์ไปที่โหนดและลบเด็กออก

1. โหนดที่จะลบมีลูกสองคน

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

11) โครงสร้างข้อมูลต้นไม้สีแดง-ดำ คืออะไร?

ต้นไม้แดง-ดำ เป็นต้นไม้ที่ปรับสมดุลตนเองชนิดพิเศษที่มีคุณสมบัติดังต่อไปนี้:

1. แต่ละโหนดมีสีแดงหรือสีดำ
2. รากเป็นสีดำเสมอ
3. โหนดสีแดงไม่สามารถมีแม่สีแดงหรือลูกสีแดง
4. ทุกเส้นทางจากโหนดรูทไปยังโหนด NULL มีจำนวนโหนดสีดำเท่ากัน

ต้องอ่าน: แนวคิดและหัวข้อโครงการโครงสร้างข้อมูล

12) คุณจะรู้ได้อย่างไรว่าต้นไม้สองต้นเหมือนกัน?

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

นี่คืออัลกอริทึมที่ช่วยให้เราทำสิ่งนี้ได้:

1. ตรวจสอบข้อมูลของโหนดรูท ( ข้อมูล tree1 == ข้อมูล tree2)
2. ตรวจสอบทรีย่อยด้านซ้ายซ้ำๆ เรียก sameTree ( tree1-> left subtree, tree2-> left subtree)
3. ในทำนองเดียวกันตรวจสอบทรีย่อยด้านขวา
4. ถ้า a,b,c เป็นจริง, return1

ชำระเงิน: ประเภทของไบนารีทรี

ความคิดสุดท้าย

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

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