Блог

Я решаю алгоритм BST с заданным числом n, мне нужно вернуть наибольшее значение, которое меньше n. К сожалению, как только я нахожу ответ. Мой код не возвращает его, но продолжает цикл. Чего я не понимаю? Спасибо.

 class Node:

# Constructor to create a new node
  def __init__(self, key):
      self.key = key
      self.left = None
      self.right = None
      self.parent = None

# A binary search tree 
class BinarySearchTree:

  # Constructor to create a new BST
  def __init__(self):
      self.root = None

  def find_largest_smaller_key(self, num):
      largest = 0

      while self.root:

        if self.root.key < num and self.root.key > largest:
            largest = self.root.key

        if self.root.right:
          if self.root.right.key < num and self.root.right.key > largest:
            self.root = self.root.right

        if self.root.left:
            if self.root.left.key < num and self.root.left.key > largest:
              largest = self.root.left.key
              self.root = self.root.left
      return largest
  

Классный алгоритм.

Подумайте о том, что произойдет, когда больше не будет ни левого, ни правого:

Это может произойти один раз, но больше не вызывать then largest == self.root .поэтому ключа здесь нет

  if self.root.key < num and self.root.key > largest:
            largest = self.root.key
  

Этого не произойдет

 if self.root.right:
  

Это также не приведет

 if self.root.left:
  

но

self.root по-прежнему имеет значение true, поэтому

   while self.root:
  

Будет продолжать работать g вечно