point quadtree คือการปรับตัวของไบนารีทรีที่นำมาใช้เพื่อแสดงข้อมูลจุดแบบ 2 มิติ คุณสมบัติของควอดทรีทั้งหมดใช้ร่วมกันโดยพอยต์ควอดทรี
มักจะมีประสิทธิภาพมากในการเปรียบเทียบจุดข้อมูลที่มีลำดับ 2 มิติ ซึ่งมักจะดำเนินการในเวลา O(log n) Point quadtrees เป็นคำกล่าวที่มีค่าสำหรับความสมบูรณ์ แต่ k-d tree นั้นเหนือกว่าพวกมันในฐานะเครื่องมือสำหรับการค้นหาไบนารีทั่วไป
จุดควอดทรีถูกสร้างขึ้นดังนี้
จากจุดถัดไปที่จะแทรก เราจะคำนวณเซลล์ที่เซลล์นั้นอยู่และเพิ่มลงในต้นไม้
มีการเพิ่มจุดใหม่เพื่อให้เซลล์ที่ประกอบด้วยจุดนั้นแบ่งออกเป็นจตุภาคด้วยเส้นแนวตั้งและแนวนอนที่ลากผ่านจุด ดังนั้น เซลล์เป็นรูปสี่เหลี่ยมผืนผ้าแต่ไม่จำเป็นต้องเป็นสี่เหลี่ยมจัตุรัส
ในแผนผังเหล่านี้ แต่ละโหนดจะประกอบด้วยจุดอินพุตหนึ่งจุด
เนื่องจากการแบ่งระนาบถูกกำหนดโดยลำดับของการแทรกจุด ความสูงของต้นไม้จึงอ่อนไหวและขึ้นอยู่กับลำดับการสอด การแทรกในลำดับที่ไม่ถูกต้องอาจทำให้ต้นไม้ที่มีความสูงเป็นเส้นตรงในจำนวนจุดอินพุต (ซึ่งจุดนั้นจะกลายเป็นรายการที่เชื่อมโยง)
หากชุดจุดคงที่ สามารถทำการประมวลผลล่วงหน้าเพื่อสร้างต้นไม้ที่มีความสูงสมดุล
โครงสร้างโหนดสำหรับจุดควอดทรี
โหนดของ point quadtree จะเหมือนกับโหนดของ binary tree โดยมีความแตกต่างที่สำคัญคือมันเกี่ยวข้องกับตัวชี้สี่ตัว (แต่ละ pointer ใช้สำหรับแต่ละ quadrant) แทนที่จะเป็นสองตัว ("left" และ "right") เป็น ในต้นไม้ไบนารีธรรมดา โดยปกติแล้ว กุญแจจะถูกแบ่งออกเป็นสองส่วน ซึ่งหมายถึงพิกัด x และ y
ดังนั้นโหนดจึงประกอบด้วยข้อมูลต่อไปนี้
- ตัวชี้สี่ตัว:เหล่านี้คือ quad[‘NW’], quad[‘NE’], quad[‘SW’] และ quad[‘SE’]
- NW-ตะวันตกเฉียงเหนือ, NE-ตะวันออกเฉียงเหนือ, SW-ตะวันตกเฉียงใต้, SE-ตะวันออกเฉียงใต้
- จุด; ซึ่งจะประกอบไปด้วย
- คีย์; มักจะแสดงเป็นพิกัด x, y
- ค่า; เช่นชื่อ
