แผนผังการค้นหาคืออะไร?

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

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

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

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

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

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

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