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

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

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

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

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

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

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

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