ต้นไม้คาร์ทีเซียน
ประวัติ

ต้นไม้คาร์ทีเซียน ถูกนำมาใช้และตั้งชื่อโดย Vuillemin (1980) ชื่อมาจากระบบพิกัดคาร์ทีเซียนสำหรับเครื่องบิน: ในรุ่นของ Vuillemin ของโครงสร้างนี้เช่นเดียวกับในช่วงสองมิติการประยุกต์ใช้การค้นหาที่กล่าวข้างต้นต้นไม้คาร์ทีเซียน สำหรับชุดจุดมีลำดับการเรียงลำดับของจุดโดย x- พิกัดเป็นลำดับ traversal สมมาตรของมันและมีคุณสมบัติ heap ตาม y พิกัดของจุด Gabow, เบนท์ลีย์ & Tarjan (1984) และผู้เขียนตามมาตามคำจำกัดความที่นี่ซึ่งเป็นต้นไม้คาร์ทีเซียนถูกกำหนดจากลำดับ การเปลี่ยนแปลงนี้ generalizes การตั้งค่าทางเรขาคณิตของ Vuillemin เพื่อให้ลำดับนอกเหนือจากลำดับที่เรียงจากพิกัด x และช่วยให้ต้นไม้คาร์ทีเซียนจะใช้กับปัญหาที่ไม่ใช่ทางเรขาคณิตเช่นกัน
ต้นไม้คาร์ทีเซียนอาจถูกนำมาใช้เป็นส่วนหนึ่งของโครงสร้างข้อมูลที่มีประสิทธิภาพสำหรับการสืบค้นขั้นต่ำสุดช่วงค้นหาปัญหาเกี่ยวกับการสอบถามที่ต้องการค่าต่ำสุดในลำดับต่อเนื่องของลำดับ ในต้นไม้คาร์ทีเซียนค่าต่ำสุดนี้อาจพบได้ที่บรรพบุรุษที่ต่ำที่สุดในด้านซ้ายสุดและขวาสุดในลำดับชั้น ตัวอย่างเช่นในลำดับ (12,10,20,15) ของลำดับที่แสดงในภาพประกอบแรกค่าต่ำสุดของลำดับชั้น (10) เป็นบรรพบุรุษร่วมสุดที่ต่ำที่สุดของค่าด้านซ้ายและด้านขวาที่สุด (12 และ 15) เนื่องจากบรรพบุรุษที่ต่ำสุดอาจพบได้ในแบบคงที่ต่อการค้นหาโดยใช้โครงสร้างข้อมูลที่ใช้พื้นที่เชิงเส้นเพื่อจัดเก็บและอาจสร้างขึ้นในเชิงเส้นเวลา ขอบเขตเดียวกันสำหรับปัญหาการย่อเล็กลงในช่วง
Bender & Farach-Colton (2000) ได้ทำให้ความสัมพันธ์ระหว่างโครงสร้างข้อมูลสองข้อนี้แย่ลงโดยแสดงให้เห็นว่าบรรพบุรุษที่ต่ำสุดในต้นอินพุทสามารถแก้ไขได้อย่างมีประสิทธิภาพโดยใช้เทคนิคที่ไม่ใช่ต้นไม้เพื่อลดช่วง โครงสร้างข้อมูลของพวกเขาใช้เทคนิคการทัวร์ของออยเลอร์เพื่อแปลงโหนดต้นทางให้เป็นลำดับและหาช่วง minima ในลำดับผลลัพธ์ ลำดับที่เกิดจากการเปลี่ยนแปลงนี้มีรูปแบบพิเศษ (ตัวเลขที่อยู่ติดกันแสดงความสูงของโหนดที่อยู่ติดกันในต้นไม้แตกต่างกัน± 1) ซึ่งใช้ประโยชน์จากโครงสร้างข้อมูลของตน เพื่อแก้ปัญหาการลดช่วงสำหรับลำดับที่ไม่ได้มีรูปแบบพิเศษนี้พวกเขาใช้ต้นไม้คาร์ทีเซียน เพื่อแปลงปัญหาการลดลงในช่วงเป็นปัญหาบรรพบุรุษที่ต่ำที่สุดร่วมกันแล้วใช้เทคนิคทัวร์ออยเลอร์เพื่อเปลี่ยนปัญหาอีกครั้งในช่วงหนึ่งของการย่อเล็กสุด สำหรับลำดับด้วยรูปแบบพิเศษนี้
ปัญหาการลดช่วงเวลาเดียวกันอาจได้รับการตีความทางเลือกในแง่ของการค้นหาช่วงสองมิติ การสะสมของหลายจุด finitely ในคาร์ทีเซียน เครื่องบินอาจถูกใช้เพื่อสร้างต้นไม้คาร์ทีเซียนโดยการเรียงลำดับจุดโดย x พิกัดของพวกเขาและใช้พิกัด y ในลำดับนี้เป็นลำดับค่าที่ต้นไม้นี้จะเกิดขึ้น ถ้า S คือเซตย่อยของจุดอินพุทภายในแผ่นแนวตั้งที่กำหนดโดยความไม่เท่าเทียม L ≤ x ≤ R, p คือจุดสุดทายที่สุดใน S (หนึ่งที่มีพิกัด x ต่ำสุด) และ q คือจุดสุดทายที่สุดใน S หนึ่งที่มีพิกัดสูงสุด x) แล้วบรรพบุรุษที่ต่ำสุดของ p และ q ในต้นไม้คาร์ทีเซียนเป็นจุดต่ำสุดในแผ่น แบบสอบถามสามด้านซึ่งในงานคือการแสดงรายการทุกจุดภายในขอบเขตที่ล้อมรอบด้วยความไม่เสมอภาคสามอัน L ≤ x ≤ R และ y ≤ T อาจได้รับคำตอบโดยหาจุดต่ำสุด b นี้เปรียบเทียบค่า y กับพิกัด T และ (ถ้าจุดอยู่ในพื้นที่สามด้าน) ดำเนินการอย่างต่อเนื่องในแผ่นสองแผ่นที่ล้อมรอบระหว่าง p และ b และระหว่าง b และ q ด้วยวิธีนี้หลังจากจุดซ้ายสุดและขวาสุดในแผ่นระบุจุดทุกจุดในพื้นที่สามด้านอาจแสดงเป็นค่าคงที่ต่อจุด
การก่อสร้างเดียวกันของบรรพบุรุษที่ต่ำที่สุดในต้นไม้คาร์ทีเซียน ทำให้สามารถสร้างโครงสร้างข้อมูลที่มีพื้นที่เชิงเส้นที่ช่วยให้ระยะทางระหว่างจุดคู่ในพื้นที่ ultrametric ใด ๆ ที่จะสอบถามในเวลาคงที่ต่อแบบสอบถาม ระยะทางภายใน ultrametric เป็นเช่นเดียวกับเส้นทาง minimax น้ำหนักในขั้นต่ำ spanning tree ของเมตริก จากต้นไม้ทอดต่ำสุดเราสามารถสร้างต้นไม้คาร์ทีเซียนซึ่งโหนดรากหมายถึงขอบที่หนักที่สุดของต้นไม้ทอดต่ำสุด การถอดขอบนี้แบ่งพาร์ติชันต่ำสุดออกเป็นสองทรีย่อยและต้นไม้คาร์ทีเซียนที่สร้างขึ้นใหม่สำหรับทรีย่อยทั้งสองนี้สร้างเด็ก ๆ ของโหนดรากของต้นไม้คาร์ทีเซียน ใบของต้นคาร์ทีเซียนแสดงถึงจุดของพื้นที่เมตริกและบรรพบุรุษที่ต่ำสุดของสองใบในต้นไม้คาร์ทีเซียนเป็นเส้นที่หนักที่สุดระหว่างจุดสองจุดในโครงสร้างสแปนนิ่งซึ่งมีน้ำหนักเท่ากับระยะห่างระหว่างจุดสองจุด . เมื่อพิจารณาขั้นต่ำสุดของต้นไม้และน้ำหนักของขอบเรียงต้นไม้คาร์ทีเซียนอาจถูกสร้างขึ้นในเชิงเส้นเวลา