while (root !== null) {
const result1 = start.compareTo(root.key)
const result2 = end.compareTo(root.key)
// 当前节点比 start 小,不再搜索左子树
if (result1 > 0) {
root = root.right
continue
}
// 当前节点大于 end,不再搜索右子树
if (result2 < 0) {
root = root.left
continue
}
break
}
if (!root) return results
const stack = [] let current: AvlNode<K> | null = root
while (stack.length || current) {
while (current) {
stack.push(current)
// 当前节点比 start 小,不再搜索 current 的左子树
if (start.compareTo(current.key) > 0) break
current = current.left
}
if (stack.length) {
// 指向栈顶
current = stack[stack.length - 1] const gteStart = start.compareTo(current.key) <= 0
const lteEnd = end.compareTo(current.key) >= 0
if (gteStart && lteEnd) {
results.push(current.key)
}
stack.pop()
// 只有 current 比 end 小,才继续搜索 current 的右子树
if (lteEnd) {
current = current.right
}
else {
current = null
}
}
}
return results
}
// 增加结点数量
_increaseSize() {
this._size += 1
}
// 减少结点数量
_decreaseSize() {
this._size -= 1
}
// 设置左子结点,同时维护 parent 关系
_setLeft(node: AvlNode<K>, child: AvlNode<K> | null) {
// 断开旧 left 结点
if (node.left !== null) {
node.left.parent = null
}
// 连接新结点
if (child !== null) {
// 从旧 parent 中断开
if (child.parent !== null) {
child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
}
child.parent = node
}
node.left = child
}
// 设置右子结点,同时维护 parent 关系
_setRight(node: AvlNode<K>, child: AvlNode<K> | null) {
// 断开旧 right 结点
if (node.right !== null) {
node.right.parent = null
}
// 连接新结点
if (child !== null) {
// 从旧 parent 中断开
if (child.parent !== null) {
child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
}
child.parent = node
}