二叉搜索樹通常用來保存一維的數據，而有時可能需要在這些一維的數據中搜索出所有在一個範圍內的元素。比如：一顆樹有元素 { 1, 3, 5, 9, 11, 12 }，給定一個閉區間 [4, 11]，最後的搜索結果應該是 { 5, 9, 11 }。
對於範圍搜索，一個 naive 的實現可以遍歷樹的所有節點，然後輸出所有在區間範圍內的元素。這種實現的復雜度是 Ɵ(n)，n = 樹節點數量，相當於最差的線性搜索。實踐時，在二插搜索樹上的範圍搜索可以利用搜索樹有序的特性進行優化，避免一些不必要的節點訪問。範圍搜索迭代的每一步大致可以分為三個場合，我們可以通過給節點著色來區分這三個場合，即分別定義黑色節點、灰色節點以及白色節點。
搜索樹中每一個節點都隱式地與一個值域相關聯，這個值域表示了當前節點及所有其子節點的值域，也就是當前（子）樹的值域。二叉搜索樹根部節點的值域是 (-∞,∞)，而每深入一層節點，這個值域就可以被當前節點的值一分為二，分別用來與兩個子樹相關聯。比如：一顆二叉搜索樹的根部節點的值是 2，而兩個子節點的值分別是 1 和 3，那麽根部節點的值域是 (-∞,∞)，左子節點的值域是 (-∞,2]，右子節點的值域是 [2,∞)，因為左子樹的所有節點的值都必然小於等於 2，而右子樹的所有節點的值都必然大於等於 2。知曉了這個隱式的值域，就可以用來和我們範圍搜索給定的範圍進行比較，從而避免不必要的搜索。
黑色節點是所有值域是範圍搜索區間的子集的節點；白色節點是所有值域和範圍搜索區沒有交集的節點；灰色節點是非白非黑的所有節點（即節點值域和範圍搜索區間的交集並非兩個集合中任何一個的子集）。如果當前節點是黑色節點，其子節點也都將是黑色，所以可以按順序將子樹的元素輸出；如果當前節點是灰色節點，那就不能確定它的子節點是什麽顏色，於是需要在子樹上遞歸應用範圍搜索，並檢查灰色節點的值是否在區間範圍內，如果是則輸出；如果當前節點是白色節點，其子節點也都將是白色，自然什麽都不用做。所以，優化後的範圍搜索實際上就是避免了冗余地遍歷白色節點。
下面是這個算法的一個 C 接口。為了節約代碼，這個實現是直接建立在這個 AVL 樹實現之上的。
/* * Searches for elements within [lo, hi] in an AVL tree. * * @param tree the tree to search on * @param lo the lower bound of the range * @param hi the upper bound of the range */ void avl_search_range(avltree_t* /*tree*/, int /*lo*/, int /*hi*/);
為了簡化實現，avl_search_range 直接把元素輸出到了標準輸出設備。實踐時可能會需要輸出到一容器中並返回給調用者。
#include <limits.h>
void
print_inorder(node_t* node)
{
if (node == 0)
return;
print_inorder(node->lchild);
printf("%d ", node->elem);
print_inorder(node->rchild);
}
void
search_range(node_t* node, int lo, int hi, int left, int right)
{
if (node == 0)
return;
/* Black node. */
else if (lo <= left && right <= hi)
print_inorder(node);
/* Gray node. */
else if (left <= hi && lo <= right) {
int elem = node->elem;
search_range(node->lchild, lo, hi, left, elem);
if (lo <= elem && elem <= hi)
printf("%d ", elem);
search_range(node->rchild, lo, hi, elem, right);
}
}
void
avl_search_range(avltree_t* tree, int lo, int hi)
{
search_range(tree->root, lo, hi, INT_MIN, INT_MAX);
printf("\n");
}
遞歸調用時，為了讓輸出的元素按順序排列需要先進行左子樹的遞歸，然後檢查並輸出當前節點元素，最後進行右子樹的遞歸。avl_search_range∈Ɵ(k+log(n))，k = 範圍搜索區間大小，n = 節點數量。
第七水螰 