ต้นไม้คาร์ทีเซียน

ในวิทยาการคอมพิวเตอร์ต้นไม้คาร์ทีเซียน (อังกฤษ : Cartesian tree) เป็นต้นไม้ไบนารีที่ได้จากลำดับของตัวเลข มันสามารถกำหนดได้ไม่ซ้ำกันจากคุณสมบัติที่เป็น heap-ordered และการ traversal แบบสมมาตร (ตามลำดับ) ของต้นไม้จะส่งกลับลำดับเริ่มต้น แนะนำโดย Vuillemin (1980) ในบริบทของโครงสร้างข้อมูลการค้นหาช่วงทางเรขาคณิต ต้นไม้คาร์ทีเซียนยังถูกนำมาใช้ในการนิยามโครงสร้างข้อมูล Tree Treap และ Randomized Binary Search Tree สำหรับปัญหาการค้นหาแบบไบนารี ต้นไม้คาร์ทีเซียน สำหรับลำดับอาจจะสร้างในเชิงเส้นเวลาโดยใช้ขั้นตอนวิธี stack - based สำหรับการค้นหาค่าที่เล็กที่สุดใกล้ที่สุดในลำดับ

คำนิยาม

ต้นไม้คาร์ทีเซียน สำหรับลำดับของตัวเลขที่แตกต่างกันสามารถกำหนดได้โดยไม่ซ้ำกันโดยคุณสมบัติต่อไปนี้:

1. ต้นไม้คาร์ทีเซียน สำหรับลำดับมีหนึ่งโหนดสำหรับแต่ละหมายเลขในลำดับ โหนดแต่ละโหนดมีค่าลำดับเดียว

2. ทรานแซทชันที่สมมาตร (ตามลำดับ) ของต้นไม้จะส่งผลให้เกิดลำดับเดิม นั่นคือทรีย่อยที่ยังเหลือประกอบด้วยค่าก่อนหน้ารากในลำดับลำดับในขณะที่ทรีย่อยที่ถูกต้องประกอบด้วยค่าต่ำกว่ารากและข้อ จำกัด ของคำสั่งที่เหมือนกันจะอยู่ที่โหนดล่างของต้นไม้

3.ต้นไม้มีคุณสมบัติ heap: parent ของโหนดที่ไม่ใช่โหนดใดมีค่าน้อยกว่าโหนดนั้นเอง

รากฐานของต้นไม้ต้องเป็นจำนวนน้อยที่สุดในลำดับ รากนี้เป็นค่าต่ำสุดของลำดับและ subtrees ซ้ายและขวาเป็นต้นไม้คาร์ทีเซียน สำหรับบันเซทด้านซ้ายและขวาของค่าราก ดังนั้นสามคุณสมบัติข้างต้นไม่ซ้ำกันกำหนดต้นไม้คาร์ทีเซียน

ถ้าลำดับของตัวเลขมี repetitions ต้นไม้คาร์ทีเซียนอาจถูกกำหนดโดยการกำหนดกฎการผูกเสมอกัน (ตัวอย่างเช่นการกำหนดว่าสององค์ประกอบแรกเท่ากันถือว่าเป็นขนาดเล็กของทั้งสอง) ก่อนที่จะใช้กฎข้างต้น

ประวัติ

ต้นไม้คาร์ทีเซียน ถูกนำมาใช้และตั้งชื่อโดย 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 ของเมตริก จากต้นไม้ทอดต่ำสุดเราสามารถสร้างต้นไม้คาร์ทีเซียนซึ่งโหนดรากหมายถึงขอบที่หนักที่สุดของต้นไม้ทอดต่ำสุด การถอดขอบนี้แบ่งพาร์ติชันต่ำสุดออกเป็นสองทรีย่อยและต้นไม้คาร์ทีเซียนที่สร้างขึ้นใหม่สำหรับทรีย่อยทั้งสองนี้สร้างเด็ก ๆ ของโหนดรากของต้นไม้คาร์ทีเซียน ใบของต้นคาร์ทีเซียนแสดงถึงจุดของพื้นที่เมตริกและบรรพบุรุษที่ต่ำสุดของสองใบในต้นไม้คาร์ทีเซียนเป็นเส้นที่หนักที่สุดระหว่างจุดสองจุดในโครงสร้างสแปนนิ่งซึ่งมีน้ำหนักเท่ากับระยะห่างระหว่างจุดสองจุด . เมื่อพิจารณาขั้นต่ำสุดของต้นไม้และน้ำหนักของขอบเรียงต้นไม้คาร์ทีเซียนอาจถูกสร้างขึ้นในเชิงเส้นเวลา

ทรีพ

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

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

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

การก่อสร้างที่มีประสิทธิภาพ

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

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

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

การประยุกต์ใช้ในการเรียงลำดับ

Levcopoulos & Petersson (1989) อธิบายขั้นตอนการเรียงลำดับตามต้นไม้คาร์ทีเซียน พวกเขาอธิบายอัลกอริทึมตามต้นไม้ที่มีจำนวนสูงสุดที่ราก แต่อาจแก้ไขได้อย่างตรงไปตรงมาเพื่อสนับสนุนต้นไม้คาร์ทีเซียนด้วยการประชุมว่าค่าต่ำสุดอยู่ที่ราก สำหรับความสอดคล้องกันนี่คืออัลกอริทึมที่ได้รับการแก้ไขแล้วซึ่งอธิบายไว้ด้านล่างนี้

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

1.สร้างต้นไม้คาร์ทีเซียน สำหรับลำดับการป้อนข้อมูล

2.เริ่มต้นคิวลำดับความสำคัญตอนแรกมีเฉพาะรากของต้นไม้เท่านั้น

3.ขณะคิวลำดับความสำคัญไม่ว่างเปล่า:

• ค้นหาและลบค่าต่ำสุด x ในลำดับความสำคัญ
• เพิ่ม x ไปยังลำดับเอาต์พุต
• เพิ่มเด็กต้นไม้ Cartesian ของ x ไปที่ลำดับความสำคัญ

เช่นเดียวกับการแสดง Levcopoulos และ Petersson สำหรับลำดับการป้อนข้อมูลที่เรียงลำดับเกือบแล้วขนาดของคิวลำดับความสำคัญจะยังเล็กอยู่ซึ่งทำให้สามารถใช้ประโยชน์จากอินพุตที่เรียงลำดับเกือบและทำงานได้รวดเร็วยิ่งขึ้น โดยเฉพาะเวลาทำงานที่เลวร้ายที่สุดของอัลกอริทึมนี้คือ O (n log k) โดยที่ k คือค่าเฉลี่ยมากกว่าค่าทั้งหมด x ในลำดับของจำนวนคู่ต่อเนื่องของค่าลำดับที่วงเล็บ x นอกจากนี้ยังพิสูจน์ว่าขอบเขตล่างระบุว่าสำหรับ n และ k = ω (1) อัลกอริทึมการเรียงลำดับที่ใช้การเปรียบเทียบจะต้องใช้การเปรียบเทียบΩ (n log k) สำหรับอินพุตบางตัว