Найти следующий больший элемент в дереве AVL

Question

Предположим, что у меня есть дерево AVL, и моя задача - найти следующий больший элемент данного элемента (т. Е. Его 7 для 6). Какой алгоритм я могу использовать?

Answer 1

Идет recursivly через узлы, и если вы обнаружили, то узел 6, то вы возвращаете глубочайшие левые ребенок ..

псевдокод:

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.

Пример из реализации в 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) 

Пример из выходного питона:

>>> # 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