在 AVL 树中查找下一个更大的元素

Question

假设我有以下 AVL 树，我的任务是找到给定元素的下一个更大的元素（即 7 为 6）。我可以使用什么算法？

Answer 1

你递归地遍历节点，如果你找到节点 6，那么你 return 最左边 children..

伪代码：

 function find_bigger_key(key, node):
    if node = null then
      return null
    else if node.key = key then
       return min_node(node)
    else if key < node.key then
       return find_bigger_key(key, node.left)
    else
       return find_bigger_key(key, node.right)

 function min_node(node):
    if node.ltree = null then
      return node
    else
       return min_node(node.ltree)

这只是一个示例，但这取决于您的 AVLTree object 模型的外观。

python中的示例实现：

class AVLTree(object):
   def __init__(self, key, ltree=None, rtree=None):
      self.key = key ; self.ltree = ltree ; self.rtree = rtree ;
      # perhaps some other attributes here....

   # some other methods here ...

   def find_bigger_key(self, key):
    if not self: return None
    elif self.key == key:
        if self.rtree:
          return self.rtree.min_node()
        else:
          return None
    elif self.key > key:
        return self.left.find_bigger_key(key)
    else:
        return self.right.find_bigger_key(key)

python 的示例输出：

>>> # aTree is a avltree object that represents your example
>>> key = 6
>>> found_node = aTree.find_bigger_key(key)
>>> print(found_node)
7
>>> key = 7
>>> found_node = aTree.find_bigger_key(key)
>>> print(found_node)
None

在 AVL 树中查找下一个更大的元素

Find next greater element in AVL tree

avl-tree