訪問節點數（visits）：0
線＝交替維度分割線（垂直＝x 切、水平＝y 切）；虛線矩形（黃）＝查詢範圍；橘色（current）＝當前檢查的節點/剛畫的分割線。
剪枝＝整個右子樹（3 個真實點）被跳過，不是巧合的空子樹。
前面的樹都在處理「一串數字」，但真實世界常要問空間問題：地圖上離我最近的餐廳是哪家？哪些會議時段 互相衝突？這頁兩種結構就是為此而生。KD 樹把平面像切蛋糕一樣，橫一刀、直一刀輪流分，找最近的點時能 整塊整塊跳過「不可能更近」的區域，不必逐一比對；區間樹專門處理「一段一段的範圍」（時間、線段），每個 節點記住底下所有範圍伸得最遠到哪，查詢時一看就知道某整支能不能直接略過。共同的訣竅都是：先把空間分好， 查詢時大膽剪掉不可能的部分。
兩者都是「先切分再剪枝」的空間索引，但切分的對象不同：KD 樹把 2D 平面依座標軸交替切分， 每個節點是一條垂直或水平的分割線，範圍查詢時靠查詢矩形與分割線的位置關係跳過整塊不可能有結果的區域； 區間樹則是把一維區間集合用 AVL 樹組織，每個節點額外擴增 maxEnd（子樹內所有區間右端點的最大值）， 重疊查詢時只要某子樹的 maxEnd 小於查詢左端點，就代表該子樹內所有區間都不可能與查詢重疊，可整支剪掉。
buildBalanced 依當前深度 depth%2 交替選 x/y 維度，將點集依該維度排序後取中位數（floor(n/2)）為節點， 遞迴建左右子樹（決定性、無隨機）；每個節點同時代表平面上一條分割線，把父節點傳下來的矩形區域切成左右兩半。 rangeSearch 檢查目前節點是否落在查詢矩形內即收進結果，再依節點的分割維度與矩形 lower/upper 邊界判斷： lower[dim] <= 節點座標[dim] 才需要搜尋左子樹、upper[dim] >= 節點座標[dim] 才需要搜尋右子樹， 否則整支子樹跳過（真剪枝，不只是「子樹恰好是空的」這種巧合）。
insert(low, high) 是標準 BST 插入（依 low 比較），但每次插入回溯時額外更新兩個欄位： height（AVL 平衡用）與 max（自身 high、左子樹 max、右子樹 max 三者取最大，即該子樹涵蓋的最遠右端點）； |balance| > 1 時依失衡型態旋轉（LL/RR/LR/RL），旋轉不影響 max 的正確性，只是換了子樹形狀。 findAllOverlaps 檢查目前節點是否與查詢區間重疊即加入結果，再判斷左右子樹是否值得下探： 某子樹的 max < 查詢左端點，代表該子樹內所有區間的右端點都比查詢左端點還小，不可能重疊，整支剪掉。