用python• 一组生物学家将有关DNA结构的信息保存在平衡的二叉搜索树 (即AVL)中，使用DNA结构的比重(整数)作为键。生物学家经 常问这样的问题:“树中是否有比重在a和b(含)之间的DNA结 构?”他们希望尽快得到答案。 • 设计一个有效的算法，给定整数 a 和 b，如果树中存在键 x，则返 回 true，使得 a<=x<=b，如果树中不存在这样的键，则返回 false。 a和b可能不在AVL树中。 • 用代码或伪代码描述您的算法。您的算法的时间复杂度是多少?

算法思路如下：

1. 找到最小的比b大的节点，记为p；

2. 找到最大的比a小的节点，记为q；

3. 如果p和q存在且p和q之间有节点，则存在比重在a和b之间的DNA结构，返回true；否则返回false。

时间复杂度为O(logn)，因为在AVL树中查找最小比b大的节点和最大比a小的节点的时间复杂度为O(logn)。

伪代码如下：

function isExistInRange(root, a, b):
    if root is None:
        return false
    if root.key >= a and root.key <= b:
        return true
    if root.key < a:
        return isExistInRange(root.right, a, b)
    if root.key > b:
        return isExistInRange(root.left, a, b)

function findMaxLessThan(root, x):
    if root is None:
        return None
    if root.key < x:
        node = findMaxLessThan(root.right, x)
        if node is None:
            return root
        else:
            return node
    else:
        return findMaxLessThan(root.left, x)

function findMinGreaterThan(root, x):
    if root is None:
        return None
    if root.key > x:
        node = findMinGreaterThan(root.left, x)
        if node is None:
            return root
        else:
            return node
    else:
        return findMinGreaterThan(root.right, x)

function isExistInRange(root, a, b):
    p = findMinGreaterThan(root, b)
    q = findMaxLessThan(root, a)
    if p is None or q is None or p == q:
        return false
    else:
        return true