ต้นไม้K -d แบบผ่อนคลายหรือต้นไม้K มิติแบบ ผ่อนคลายเป็นโครงสร้างข้อมูลที่เป็นรูปแบบหนึ่งของต้นไม้ Kdเช่นเดียวกับต้นไม้ K มิติ ต้นไม้ K มิติแบบผ่อนคลายจะจัดเก็บชุดของระเบียนหลายมิติ n รายการ โดยแต่ละรายการจะมีคีย์ K มิติที่ไม่ซ้ำกันx=(x ,... ,x )แตกต่างจากต้นไม้ Kd ตรงที่ในต้นไม้ Kd แบบผ่อนคลาย ตัวแยกแยะในแต่ละโหนดจะเป็นค่าใดก็ได้ ต้นไม้ Kd แบบผ่อนคลายได้รับการแนะนำในปี 1998 ^{[ 1 ]}

ต้นไม้ Kd แบบผ่อนคลายสำหรับชุดคีย์ K มิติ คือต้นไม้ไบนารีที่มีลักษณะดังนี้:

1. แต่ละโหนดประกอบด้วยเรคอร์ด K มิติ และมีค่าดิสครีมิแนนต์j ∈ {0,1,...,K − 1}ที่ เกี่ยวข้อง
2. สำหรับทุกโหนดที่มีคีย์xและดิสคริมิแนนท์jเงื่อนไขคงที่ต่อไปนี้เป็นจริง: บันทึกใดๆ ในซับทรีด้านซ้ายที่มีคีย์ y จะสอดคล้องกับy < x และบันทึกใดๆ ในซับทรีด้านขวาที่มีคีย์ y จะสอดคล้องกับy j x ^{[ 2 ]}

ถ้าK = 1ต้นไม้ Kd แบบผ่อนคลายจะเป็นต้นไม้ค้นหาแบบไบนารี

เช่นเดียวกับในต้นไม้ Kd ต้นไม้ Kd แบบผ่อนคลายที่มีขนาดnจะเหนี่ยวนำให้เกิดการแบ่งโดเมน D ออกเป็นn+1บริเวณ โดยแต่ละบริเวณจะสอดคล้องกับใบในต้นไม้ Kd กรอบล้อมรอบ (หรืออาร์เรย์ขอบเขต) ของโหนด {x,j} คือบริเวณของพื้นที่ที่ถูกกำหนดโดยใบซึ่ง x ตกอยู่เมื่อถูกแทรกเข้าไปในต้นไม้ ดังนั้น กรอบล้อมรอบของราก {y,i} คือ [0,1] ^Kกรอบล้อมรอบของรากของต้นไม้ย่อยด้านซ้ายคือ [0,1] × ... × [0,y ] × ... × [0,1] และอื่นๆ

ความซับซ้อนของเวลาโดยเฉลี่ยในโครงสร้างต้นไม้ Kd แบบผ่อนคลายที่มี ระเบียน nรายการ มีดังนี้:

• การค้นหาแบบตรงกันทุกประการ: O(log n)
• การค้นหาแบบจับคู่บางส่วน: O(n ^1−f(s/K) ) โดยที่:
  • มีการระบุคุณลักษณะ s จากทั้งหมด K รายการ
  • โดยที่ 0 < f(s/K) < 1 ซึ่งเป็นฟังก์ชันค่าจริงของ s/K
• การค้นหาเพื่อนบ้านที่ใกล้ที่สุด: O(log n) ^{[ 3 ]}

• ต้นไม้k -d
• ต้นไม้k -d โดยปริยาย คือต้นไม้k -d ที่กำหนดโดยฟังก์ชันการแบ่งโดยปริยาย แทนที่จะเป็นชุดการแบ่งที่จัดเก็บไว้อย่างชัดเจน
• ต้นไม้k -d แบบ min/maxคือ ต้นไม้ k -d ที่กำหนดค่าต่ำสุดและค่าสูงสุดให้กับแต่ละโหนด