ในวิทยาการคอมพิวเตอร์ต้นไม้คาร์ทีเซียนเป็นต้นไม้ไบนารีที่สร้างขึ้นจากลำดับของตัวเลขที่แตกต่างกัน ในการสร้างต้นไม้คาร์ทีเซียน ให้กำหนดให้ตัวเลขที่น้อยที่สุดในลำดับเป็นราก และสร้างต้นไม้ย่อยซ้ายและขวาแบบเรียกซ้ำจากลำดับย่อยก่อนและหลังตัวเลขนี้ ต้นไม้คาร์ทีเซียนมีนิยามเฉพาะตัวว่าเป็น ฮีปแบบมินิม ( min-heap ) ซึ่งการท่องไปในฮีปแบบสมมาตร (ตามลำดับ)จะคืนค่าลำดับเดิมกลับมา

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

ต้นไม้คาร์ทีเซียนถูกกำหนดโดยใช้ต้นไม้ไบนารีซึ่งเป็นรูปแบบหนึ่งของต้นไม้ที่มีรากในการสร้างต้นไม้คาร์ทีเซียนสำหรับลำดับตัวเลขที่แตกต่างกันที่กำหนด ให้ตั้งรากเป็นตัวเลขต่ำสุดในลำดับ^{[ 1 ]}และ สร้างต้นไม้ย่อยซ้ายและขวา แบบเรียกซ้ำจากลำดับย่อยก่อนและหลังตัวเลขนี้ตามลำดับ ในกรณีพื้นฐาน เมื่อลำดับย่อยใดลำดับหนึ่งว่างเปล่า จะไม่มีต้นไม้ย่อยซ้ายหรือขวา^{[ 2 ]}

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

1. ต้นไม้คาร์ทีเซียนสำหรับลำดับคือต้นไม้ไบนารีที่มีโหนดหนึ่งโหนดสำหรับแต่ละตัวเลขในลำดับนั้น
2. การ ท่อง ต้นไม้แบบสมมาตร (ตามลำดับ) จะได้ลำดับเดิม หรือกล่าวอีกนัยหนึ่ง สำหรับแต่ละโหนด ตัวเลขในซับทรีด้านซ้ายจะอยู่ก่อนโหนดนั้นในลำดับ และตัวเลขในซับทรีด้านขวาจะอยู่ทีหลัง
3. ต้นไม้มีคุณสมบัติ min-heap กล่าวคือ ผู้ปกครองของโหนดที่ไม่ใช่โหนดรากจะมีค่าน้อยกว่าตัวโหนดเอง^{[ 1 ]}

คำจำกัดความทั้งสองนี้เทียบเท่ากัน: ต้นไม้ที่กำหนดแบบเรียกซ้ำตามที่อธิบายไว้ข้างต้นคือต้นไม้ที่ไม่ซ้ำกันที่มีคุณสมบัติที่ระบุไว้ข้างต้น หากลำดับของตัวเลขมีการซ้ำกัน สามารถกำหนดต้นไม้คาร์ทีเซียนได้โดยปฏิบัติตามกฎการตัดสินความเสมอที่สอดคล้องกันก่อนที่จะใช้การสร้างข้างต้น ตัวอย่างเช่น องค์ประกอบแรกจากสององค์ประกอบที่เท่ากันสามารถถือได้ว่าเป็นองค์ประกอบที่เล็กกว่า^{[ 2 ]}

ต้นไม้คาร์ทีเซียนได้รับการแนะนำและตั้งชื่อโดยVuillemin (1980)ซึ่งใช้เป็นตัวอย่างของการปฏิสัมพันธ์ระหว่างเรขาคณิตเชิงการจัดเรียงและการออกแบบและการวิเคราะห์โครงสร้างข้อมูลโดยเฉพาะอย่างยิ่ง Vuillemin ใช้โครงสร้างเหล่านี้เพื่อวิเคราะห์ความซับซ้อนของกรณีเฉลี่ยของการดำเนินการเชื่อมต่อและการแยกบนต้นไม้ค้นหาแบบ ไบนารี ชื่อนี้ได้มาจาก ระบบ พิกัดคาร์ทีเซียนสำหรับระนาบ: ในโครงสร้างเวอร์ชันหนึ่งนี้ เช่นเดียวกับในแอปพลิเคชันการค้นหาช่วงสองมิติที่กล่าวถึงด้านล่าง ต้นไม้คาร์ทีเซียนสำหรับชุดจุดจะมีลำดับที่เรียงตามพิกัด x ของจุดเป็นลำดับการท่องแบบสมมาตร และมีคุณสมบัติฮีปตามพิกัด x ของจุด Vuillemin อธิบายทั้งโครงสร้างเวอร์ชันเรขาคณิตนี้และคำจำกัดความที่นี่ซึ่งต้นไม้คาร์ทีเซียนถูกกำหนดจากลำดับ การใช้ลำดับแทนพิกัดจุดทำให้มีการตั้งค่าทั่วไปมากขึ้นซึ่งช่วยให้ต้นไม้คาร์ทีเซียนสามารถนำไปใช้กับปัญหาที่ไม่ใช่เรขาคณิตได้เช่นกัน^{[ 2 ]}${\displaystyle x}$${\displaystyle y}$

ต้นไม้คาร์ทีเซียนสามารถสร้างได้ในเวลาเชิงเส้นจากลำดับอินพุต วิธีหนึ่งคือการประมวลผลค่าลำดับจากซ้ายไปขวา โดยรักษาต้นไม้คาร์ทีเซียนของโหนดที่ประมวลผลไปแล้วไว้ในโครงสร้างที่อนุญาตให้เดินทางขึ้นและลงของต้นไม้ได้ ในการประมวลผลค่าใหม่แต่ละค่าให้เริ่มต้นที่โหนดที่แสดงค่าก่อนหน้าในลำดับและติดตามเส้นทางจากโหนดนี้ไปยังรากของต้นไม้จนกว่าจะพบค่าที่เล็กกว่าโหนดนั้นจะกลายเป็นลูกทางขวาของและลูกทางขวาก่อนหน้าของจะกลายเป็นลูกทางซ้ายใหม่ของเวลาทั้งหมดสำหรับกระบวนการนี้เป็นเชิงเส้น เนื่องจากเวลาที่ใช้ในการค้นหาผู้ปกครองของแต่ละโหนดใหม่สามารถคิดค่าใช้จ่ายกับจำนวนโหนดที่ถูกลบออกจากเส้นทางขวาสุดในต้นไม้ได้^{[ 3 ]}${\displaystyle a}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$

อัลกอริทึมการสร้างแบบเชิงเส้นทางเลือกอีกวิธีหนึ่งนั้นอิงตาม ปัญหา ค่าที่เล็กกว่าที่อยู่ใกล้ที่สุดทั้งหมดในลำดับอินพุต ให้กำหนดเพื่อนบ้านด้านซ้ายของค่าหนึ่งเป็นค่าที่ปรากฏก่อนหน้าซึ่งเล็กกว่าและอยู่ใกล้กว่าค่าที่เล็กกว่าอื่นๆ ในตำแหน่ง เพื่อนบ้านด้านขวาถูกกำหนดในลักษณะสมมาตร ลำดับของเพื่อนบ้านด้านซ้ายสามารถหาได้โดยอัลกอริทึมที่รักษาสแต็ ก ที่มีลำดับย่อยของอินพุต สำหรับแต่ละค่าลำดับใหม่สแต็กจะถูกดึงออกจนกว่าจะว่างเปล่าหรือองค์ประกอบบนสุดมีค่าน้อยกว่าแล้วจึงใส่ ลงในสแต็ก เพื่อนบ้านด้านซ้ายของคือองค์ประกอบบนสุดในขณะที่ถูกใส่ลงไป เพื่อนบ้านด้านขวาสามารถหาได้โดยการใช้อัลกอริทึมสแต็กเดียวกันกับลำดับย้อนกลับ ผู้ปกครองของในต้นไม้คาร์ทีเซียนคือเพื่อนบ้านด้านซ้ายของหรือเพื่อนบ้านด้านขวาของแล้วแต่ว่ามีอยู่และมีค่ามากกว่า เพื่อนบ้านด้านซ้ายและด้านขวาสามารถสร้างได้อย่างมีประสิทธิภาพโดยอัลกอริทึมแบบขนานทำให้สูตรนี้มีประโยชน์ในอัลกอริทึมแบบขนานที่มีประสิทธิภาพสำหรับการสร้างต้นไม้คาร์ทีเซียน^{[ 4 ]}${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$

อีกหนึ่งอัลกอริธึมแบบใช้เวลาเชิงเส้นสำหรับการสร้างต้นไม้คาร์ทีเซียนนั้นใช้หลักการแบ่งและพิชิต (divide-and-conquer ) อัลกอริธึมนี้จะสร้างต้นไม้แบบเรียกซ้ำบนแต่ละครึ่งของข้อมูลอินพุต จากนั้นจึงรวมต้นไม้ทั้งสองเข้าด้วยกัน กระบวนการรวมจะเกี่ยวข้องเฉพาะโหนดบนแกน ซ้ายและขวา ของต้นไม้เหล่านี้เท่านั้น โดยแกนซ้ายคือเส้นทางที่ได้จากการติดตามขอบลูกซ้ายจากรากจนถึงโหนดที่ไม่มีลูกซ้าย และแกนขวาจะถูกกำหนดแบบสมมาตร เช่นเดียวกับเส้นทางใดๆ ใน min-heap ค่าของแกนทั้งสองจะเรียงลำดับจากค่าที่น้อยที่สุดที่รากไปจนถึงค่าที่ใหญ่ที่สุดที่ปลายเส้นทาง ในการรวมต้นไม้ทั้งสอง ให้ใช้อัลกอริธึมการรวมกับแกนขวาของต้นไม้ด้านซ้ายและแกนซ้ายของต้นไม้ด้านขวา โดยแทนที่เส้นทางทั้งสองในต้นไม้ทั้งสองด้วยเส้นทางเดียวที่มีโหนดเดียวกัน ในเส้นทางที่รวมกัน ผู้สืบทอดในลำดับที่เรียงแล้วของแต่ละโหนดจากต้นไม้ด้านซ้ายจะถูกวางไว้ในลูกด้านขวา และผู้สืบทอดของแต่ละโหนดจากต้นไม้ด้านขวาจะถูกวางไว้ในลูกด้านซ้าย ซึ่งเป็นตำแหน่งเดียวกับที่เคยใช้สำหรับผู้สืบทอดในแกนหลัก ลูกด้านซ้ายของโหนดจากต้นไม้ด้านซ้ายและลูกด้านขวาของโหนดจากต้นไม้ด้านขวายังคงไม่เปลี่ยนแปลง อัลกอริทึมนี้สามารถประมวลผลแบบขนานได้ เนื่องจากในแต่ละระดับของการเรียกซ้ำ ปัญหาย่อยทั้งสองสามารถคำนวณแบบขนานได้ และการดำเนินการรวมก็สามารถประมวลผลแบบขนานได้อย่างมีประสิทธิภาพเช่นกัน^{[ 5 ]}

อัลกอริทึมแบบเชิงเส้นอีกตัวหนึ่งที่ใช้การแสดงลำดับอินพุตแบบรายการเชื่อมโยงนั้น อิงตามการเชื่อมโยงค่าสูงสุดเฉพาะที่ : อัลกอริทึมจะระบุ องค์ประกอบ ค่าสูงสุดเฉพาะ ที่ซ้ำๆ กล่าว คือ องค์ประกอบที่ใหญ่กว่าเพื่อนบ้านทั้งสอง (หรือใหญ่กว่าเพื่อนบ้านเพียงตัวเดียว ในกรณีที่เป็นองค์ประกอบแรกหรือองค์ประกอบสุดท้ายในรายการ) จากนั้นองค์ประกอบนี้จะถูกลบออกจากรายการ และแนบเป็นลูกทางขวาของเพื่อนบ้านทางซ้าย หรือลูกทางซ้ายของเพื่อนบ้านทางขวา ขึ้นอยู่กับว่าเพื่อนบ้านตัวใดมีค่ามากกว่า โดยจะตัดสินใจในกรณีที่มีค่าเท่ากันโดยพลการ กระบวนการนี้สามารถนำไปใช้ได้ในรอบการประมวลผลอินพุตจากซ้ายไปขวาเพียงครั้งเดียว และเห็นได้ง่ายว่าแต่ละองค์ประกอบสามารถมีลูกทางซ้ายได้มากที่สุดหนึ่งตัว และลูกทางขวาได้มากที่สุดหนึ่งตัว และต้นไม้ไบนารีที่ได้จะเป็นต้นไม้คาร์ทีเซียนของลำดับอินพุต^{[ 6 ] [ 7 ]}

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

ต้นไม้คาร์ทีเซียนเป็นส่วนหนึ่งของโครงสร้างข้อมูลที่มีประสิทธิภาพสำหรับการค้นหาค่าต่ำสุดในช่วงอินพุตของการค้นหาประเภทนี้ระบุลำดับย่อยที่ต่อเนื่องกันของลำดับดั้งเดิม เอาต์พุตของการค้นหาควรเป็นค่าต่ำสุดในลำดับย่อยนี้^{[ 9 ]}ในต้นไม้คาร์ทีเซียน ค่าต่ำสุดนี้สามารถพบได้ที่บรรพบุรุษร่วมที่ต่ำที่สุดของค่าซ้ายสุดและขวาสุดในลำดับย่อย ตัวอย่างเช่น ในลำดับย่อย (12,10,20,15,18) ของลำดับตัวอย่าง ค่าต่ำสุดของลำดับย่อย (10) ก่อให้เกิดบรรพบุรุษร่วมที่ต่ำที่สุดของค่าซ้ายสุดและขวาสุด (12 และ 18) เนื่องจากสามารถค้นหาบรรพบุรุษร่วมที่ต่ำที่สุดได้ในเวลาคงที่ต่อการค้นหา โดยใช้โครงสร้างข้อมูลที่ใช้พื้นที่เชิงเส้นในการจัดเก็บและสามารถสร้างได้ในเวลาเชิงเส้น ขอบเขตเดียวกันนี้จึงใช้ได้กับปัญหาการลดค่าในช่วง^{[ 10 ]}

Bender & Farach-Colton (2000)ได้พลิกกลับความสัมพันธ์ระหว่างปัญหาโครงสร้างข้อมูลทั้งสองนี้ โดยแสดงให้เห็นว่าโครงสร้างข้อมูลสำหรับการลดช่วง (range minimization) สามารถนำมาใช้ในการหาบรรพบุรุษร่วมที่ต่ำที่สุด (lowest common ancestors) ได้เช่นกัน โครงสร้างข้อมูลของพวกเขากำหนดระยะห่างจากรากของแต่ละโหนดในต้นไม้ และสร้างลำดับของระยะห่างเหล่านี้ตามลำดับของเส้นทางออยเลอร์ (Euler tour ) ของต้นไม้ (ที่เพิ่มขอบเป็นสองเท่า) จากนั้นจึงสร้างโครงสร้างข้อมูลการลดช่วงสำหรับลำดับที่ได้ บรรพบุรุษร่วมที่ต่ำที่สุดของจุดยอดสองจุดใดๆ ในต้นไม้ที่กำหนดสามารถพบได้จากระยะห่างน้อยที่สุดที่ปรากฏในช่วงระหว่างตำแหน่งเริ่มต้นของจุดยอดสองจุดนั้นในลำดับ Bender และ Farach-Colton ยังได้เสนอวิธีการลดช่วงที่สามารถใช้กับลำดับที่ได้จากการแปลงนี้ ซึ่งมีคุณสมบัติพิเศษคือค่าลำดับที่อยู่ติดกันจะแตกต่างกันหนึ่งค่า ตามที่พวกเขาอธิบาย สำหรับการลดช่วงในลำดับที่ไม่มีรูปแบบนี้ เป็นไปได้ที่จะใช้ต้นไม้คาร์ทีเซียนเพื่อลดปัญหาการลดช่วงให้เหลือบรรพบุรุษร่วมที่ต่ำที่สุด จากนั้นใช้เส้นทางออยเลอร์เพื่อลดบรรพบุรุษร่วมที่ต่ำที่สุดให้เหลือปัญหาการลดช่วงที่มีรูปแบบพิเศษนี้^{[ 11 ]}

ปัญหาการลดช่วงเดียวกันนี้อาจตีความได้อีกแบบหนึ่งในแง่ของการค้นหาช่วงสองมิติ เราสามารถใช้ จุดจำนวนจำกัดใน ระนาบพิกัดคาร์ทีเซียน เพื่อสร้างต้นไม้คาร์ทีเซียนได้ โดยการเรียงลำดับจุดตาม พิกัด x และใช้พิกัด x ตามลำดับนี้เป็นลำดับของค่าที่ใช้สร้างต้นไม้ ถ้าเป็นเซตย่อยของจุดอินพุตภายในระนาบแนวตั้งที่กำหนดโดยอสมการคือจุดซ้ายสุดใน(จุดที่มีพิกัด x ต่ำสุด) และคือจุดขวาสุดใน(จุดที่มีพิกัด x สูงสุด) แล้วบรรพบุรุษร่วมที่ต่ำที่สุดของและในต้นไม้คาร์ทีเซียนคือจุดล่างสุดในระนาบนั้น การค้นหาช่วงสามด้าน ซึ่งงานคือการแสดงรายการจุดทั้งหมดภายในภูมิภาคที่ล้อมรอบด้วยอสมการสามข้อและสามารถตอบได้โดยการค้นหาจุดล่างสุดนี้เปรียบเทียบพิกัด - ของจุดนั้นกับและ (ถ้าจุดนั้นอยู่ภายในภูมิภาคสามด้าน) ดำเนินการเรียกซ้ำต่อไปในแผ่นสองแผ่นที่ล้อมรอบระหว่างและและระหว่างและด้วยวิธีนี้ หลังจากระบุจุดซ้ายสุดและขวาสุดในแผ่นแล้ว จุดทั้งหมดภายในภูมิภาคสามด้านสามารถแสดงรายการได้ในเวลาคงที่ต่อจุด^{[ 3 ]}${\displaystyle x}$${\displaystyle y}$${\displaystyle S}$${\displaystyle L\leq x\leq R}$${\displaystyle p}$${\displaystyle S}$${\displaystyle x}$${\displaystyle q}$${\displaystyle S}$${\displaystyle x}$${\displaystyle p}$${\displaystyle q}$${\displaystyle L\leq x\leq R}$${\displaystyle y\leq T}$${\displaystyle b}$${\displaystyle y}$${\displaystyle T}$${\displaystyle p}$${\displaystyle b}$${\displaystyle b}$${\displaystyle q}$

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

ต้นไม้คาร์ทีเซียนของลำดับที่เรียงลำดับแล้วเป็นเพียงกราฟเส้นทางที่มีรากอยู่ที่จุดปลายซ้ายสุด การค้นหาแบบไบนารีในต้นไม้นี้จะลดรูปเป็นการค้นหาตามลำดับในเส้นทาง อย่างไรก็ตาม การสร้างที่แตกต่างกันจะใช้ต้นไม้คาร์ทีเซียนเพื่อสร้างต้นไม้ค้นหาแบบไบนารีที่มีความลึกแบบลอการิทึมจากลำดับค่าที่เรียงลำดับแล้ว ซึ่งสามารถทำได้โดยการสร้าง หมายเลขลำดับ ความสำคัญสำหรับแต่ละค่า และใช้ลำดับของลำดับความสำคัญเพื่อสร้างต้นไม้คาร์ทีเซียน การสร้างนี้อาจมองได้ในกรอบเรขาคณิตที่อธิบายไว้ข้างต้น ซึ่งพิกัด x ของชุดจุดคือค่าในลำดับที่เรียงลำดับแล้ว และพิกัด y คือลำดับความสำคัญของค่าเหล่านั้น^{[ 14 ]}${\displaystyle x}$${\displaystyle y}$

แนวคิดนี้ถูกนำไปใช้โดยSeidel & Aragon (1996)ซึ่งเสนอให้ใช้ตัวเลขสุ่มเป็นลำดับความสำคัญต้นไม้ค้นหาแบบไบนารีที่ปรับสมดุลตัวเองได้ซึ่งเป็นผลมาจากการเลือกแบบสุ่มนี้เรียกว่าtreapเนื่องจากเป็นการผสมผสานคุณสมบัติของต้นไม้ค้นหาแบบไบนารีและ min-heap การแทรกข้อมูลลงใน treap สามารถทำได้โดยการแทรกคีย์ใหม่เป็นใบของต้นไม้ที่มีอยู่ เลือกค่าลำดับความสำคัญให้กับคีย์นั้น แล้วทำการหมุนต้นไม้ตามเส้นทางจากโหนดไปยังรากของต้นไม้เพื่อแก้ไขการละเมิดคุณสมบัติของ heap ที่เกิดจากการแทรกนี้ การลบข้อมูลก็สามารถทำได้ในทำนองเดียวกันโดยการเปลี่ยนแปลงค่าคงที่ให้กับต้นไม้ ตามด้วยลำดับการหมุนตามเส้นทางเดียวในต้นไม้^{[ 14 ]}รูปแบบหนึ่งของโครงสร้างข้อมูลนี้เรียกว่า zip tree ซึ่งใช้แนวคิดเดียวกันของลำดับความสำคัญแบบสุ่ม แต่ทำให้การสร้างลำดับความสำคัญแบบสุ่มง่ายขึ้น และดำเนินการแทรกและลบด้วยวิธีที่แตกต่างกัน โดยการแบ่งลำดับและต้นไม้คาร์ทีเซียนที่เกี่ยวข้องออกเป็นสองลำดับย่อยและสองต้นไม้ แล้วจึงรวมเข้าด้วยกันอีกครั้ง^{[ 15 ]}

หากเลือกค่าลำดับความสำคัญของแต่ละคีย์แบบสุ่มและเป็นอิสระต่อกันในแต่ละครั้งที่มีการแทรกคีย์เข้าไปในต้นไม้ ต้นไม้คาร์ทีเซียนที่ได้จะมีคุณสมบัติเช่นเดียวกับต้นไม้ค้นหาแบบไบนารีแบบสุ่มซึ่งเป็นต้นไม้ที่คำนวณโดยการแทรกคีย์ในลำดับการเรียงสับเปลี่ยน ที่เลือกแบบสุ่ม โดยเริ่มต้นจากต้นไม้ว่างเปล่า โดยแต่ละครั้งที่แทรกจะไม่เปลี่ยนแปลงโครงสร้างของต้นไม้ก่อนหน้า และแทรกโหนดใหม่เป็นใบของต้นไม้ ต้นไม้ค้นหาแบบไบนารีแบบสุ่มได้รับการศึกษามานานกว่า treaps และเป็นที่ทราบกันดีว่ามีพฤติกรรมที่ดีในฐานะต้นไม้ค้นหา ความ ยาว ที่คาดหวังของเส้นทางการค้นหาไปยังค่าใด ๆ ที่กำหนดจะมีค่าสูงสุดไม่เกินและต้นไม้ทั้งหมดมี ระดับความลึก แบบลอการิทึม (ระยะทางสูงสุดจากรากถึงใบ) ด้วยความน่าจะเป็นสูง กล่าวอย่างเป็นทางการมากขึ้น มีค่าคงที่อยู่ค่าหนึ่งที่ทำให้ระดับความลึกเป็นด้วยความน่าจะเป็นที่เข้าใกล้หนึ่งเมื่อจำนวนโหนดเข้าใกล้ค่าอนันต์ พฤติกรรมที่ดีเช่นเดียวกันนี้ยังคงมีอยู่ใน treaps ด้วย นอกจากนี้ ยังเป็นไปได้เช่นกัน ตามที่ Aragon และ Seidel แนะนำ ที่จะจัดลำดับความสำคัญของโหนดที่เข้าถึงบ่อยใหม่ ทำให้โหนดเหล่านั้นเคลื่อนไปทางรากของ treap และเร่งความเร็วในการเข้าถึงคีย์เดียวกันในอนาคต^{[ 14 ]}${\displaystyle 2\ln n}$${\displaystyle C}$${\displaystyle \leq C\ln n}$

Levcopoulos & Petersson (1989)อธิบายอัลกอริทึมการเรียงลำดับโดยใช้ต้นไม้คาร์ทีเซียน พวกเขาอธิบายอัลกอริทึมโดยใช้ต้นไม้ที่มีค่าสูงสุดอยู่ที่ราก^{[ 16 ]}แต่สามารถปรับเปลี่ยนได้อย่างง่ายดายเพื่อรองรับต้นไม้คาร์ทีเซียนโดยมีข้อตกลงว่าค่าต่ำสุดอยู่ที่ราก เพื่อความสอดคล้อง จึงเป็นเวอร์ชันที่ปรับเปลี่ยนของอัลกอริทึมนี้ที่อธิบายไว้ด้านล่าง

อัลกอริทึม Levcopoulos–Petersson สามารถมองได้ว่าเป็นเวอร์ชันของการเรียงลำดับแบบเลือกหรือการเรียงลำดับแบบฮีปที่รักษาคิวลำดับความสำคัญของค่าต่ำสุดที่เป็นไปได้ และในแต่ละขั้นตอนจะค้นหาและลบค่าต่ำสุดในคิวนี้ โดยย้ายค่านี้ไปยังส่วนท้ายของลำดับเอาต์พุต ในอัลกอริทึมของพวกเขา คิวลำดับความสำคัญประกอบด้วยเฉพาะองค์ประกอบที่มีผู้ปกครองในต้นไม้คาร์ทีเซียนที่ถูกค้นพบและลบออกไปแล้วเท่านั้น ดังนั้น อัลกอริทึมจึงประกอบด้วยขั้นตอนต่อไปนี้: ^{[ 16 ]}

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

ดังที่ Levcopoulos และ Petersson แสดงให้เห็น สำหรับลำดับอินพุตที่เกือบจะเรียงลำดับแล้ว ขนาดของคิวลำดับความสำคัญจะยังคงเล็ก ทำให้วิธีนี้สามารถใช้ประโยชน์จากอินพุตที่เกือบจะเรียงลำดับและทำงานได้เร็วขึ้น โดยเฉพาะอย่างยิ่ง เวลาการทำงานในกรณีที่เลวร้ายที่สุดของอัลกอริทึมนี้คือโดยที่คือความยาวของลำดับ และคือค่าเฉลี่ยของจำนวนคู่ค่าลำดับที่ต่อเนื่องกันซึ่งครอบคลุมค่าที่กำหนด (หมายความว่าค่าที่กำหนดอยู่ระหว่างค่าลำดับทั้งสอง) พวกเขายังพิสูจน์ขอบเขตล่างที่ระบุว่า สำหรับและ ใดๆ (ไม่คงที่) อัลกอริทึมการเรียงลำดับตามการเปรียบเทียบใดๆ จะต้องใช้การเปรียบเทียบสำหรับอินพุตบางส่วน^{[ 16 ]}${\displaystyle O(n\log k)}$${\displaystyle n}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k}$${\displaystyle \Omega (n\log k)}$

ปัญหาการจับคู่ต้นไม้คาร์ทีเซียนได้รับการกำหนดให้เป็นรูปแบบทั่วไปของการจับคู่สตริงซึ่งค้นหาสตริงย่อย (หรือในบางกรณีลำดับย่อย ) ของสตริงที่กำหนดซึ่งมีต้นไม้คาร์ทีเซียนในรูปแบบเดียวกันกับรูปแบบที่กำหนด ได้มีการพัฒนาอัลกอริธึมที่รวดเร็วสำหรับรูปแบบต่างๆ ของปัญหาที่มีรูปแบบเดียวหรือหลายรูปแบบ รวมถึงโครงสร้างข้อมูลที่คล้ายคลึงกับต้นไม้ต่อท้ายและโครงสร้างการจัดทำดัชนีข้อความอื่นๆ^{[ 17 ]}