ต้นไม้รูปสี่เหลี่ยมคืออะไร?

ต้นไม้รูปสี่เหลี่ยมบางครั้ง quadtree, q-tree หรือ qt เป็นศัพท์วิทยาศาสตร์คอมพิวเตอร์ที่หมายถึงวิธีการจัดระเบียบข้อมูลในสี่ Quadrantsบางครั้งฐานข้อมูลใช้ต้นไม้รูปสี่เหลี่ยมเพื่อจัดเก็บและค้นหาบันทึกของพวกเขาโครงสร้างองค์กรประเภทนี้ทำงานได้ดีโดยเฉพาะอย่างยิ่งในการค้นหาบิตหรือพิกเซลโดยเฉพาะในภาพสองมิติ

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

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

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

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

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

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