我在 AVL 树搜索问题上遇到错误

Question

我正在尝试为 AVL 树执行搜索功能，当我尝试搜索树中的数字时，代码工作正常，但出现错误

AttributeError: 'NoneType' object has no attribute 'search'

当尝试搜索不在树中的号码时

这是搜索功能

    def search(self, data):
   
      if self is None:
        return "the key doesn't exist"  
      elif data < self.data:
        return self.left.busca(data)
      elif data > self.data:
        return self.right.busca(data)
      else:
        return "the key exist"

和整个代码（变量名在pt-br中）

class No:
def __init__(self, data):
    self.data = data
    self.setaFilhos(None, None)

def setaFilhos(self, esquerda, direita):
    self.esquerda = esquerda
    self.direita = direita

def balanco(self):
    prof_esq = 0
    if self.esquerda:
        prof_esq = self.esquerda.profundidade()
    prof_dir = 0
    if self.direita:
        prof_dir = self.direita.profundidade()
    return prof_esq - prof_dir

def profundidade(self):
    prof_esq = 0
    if self.esquerda:
        prof_esq = self.esquerda.profundidade()
    prof_dir = 0
    if self.direita:
        prof_dir = self.direita.profundidade()
    return 1 + max(prof_esq, prof_dir)

def rotacaoEsquerda(self):
    self.data, self.direita.data = self.direita.data, self.data
    old_esquerda = self.esquerda
    self.setaFilhos(self.direita, self.direita.direita)
    self.esquerda.setaFilhos(old_esquerda, self.esquerda.esquerda)

def rotacaoDireita(self):
    self.data, self.esquerda.data = self.esquerda.data, self.data
    old_direita = self.direita
    self.setaFilhos(self.esquerda.esquerda, self.esquerda)
    self.direita.setaFilhos(self.direita.direita, old_direita)

def rotacaoEsquerdaDireita(self):
    self.esquerda.rotacaoEsquerda()
    self.rotacaoDireita()

def rotacaoDireitaEsquerda(self):
    self.direita.rotacaoDireita()
    self.rotacaoEsquerda()

def executaBalanco(self):
    bal = self.balanco()
    if bal > 1:
        if self.esquerda.balanco() > 0:
            self.rotacaoDireita()
        else:
            self.rotacaoEsquerdaDireita()
    elif bal < -1:
        if self.direita.balanco() < 0:
            self.rotacaoEsquerda()
        else:
            self.rotacaoDireitaEsquerda()

def insere(self, data):
    if data <= self.data:
        if not self.esquerda:
            self.esquerda = No(data)
        else:
            self.esquerda.insere(data)
    else:
        if not self.direita:
            self.direita = No(data)
        else:
            self.direita.insere(data)
    self.executaBalanco()

def remove(self, data):
    if self.direita is None and self.esquerda is None:
        return None
    if data < self.data:
        self.esquerda = self.esquerda.remove(data)
    elif data > self.data:
        self.direita = self.direita.remove(data)
    else:
        if self.direita is None:
            return self.esquerda
        if self.esquerda is None:
            return self.direita
        tmp = self.direita._min()
        self.data = tmp.data 
        self.direita = self.direita.remove(tmp.data)
    self.executaBalanco()
    return self
  
def busca(self, data):
  if self is None:
        return "A chave não existe"  
  elif data < self.data:
    return self.esquerda.busca(data)
  elif data > self.data:
    return self.direita.busca(data)
  else:
    return "A chave existe"
     
def _min(self):
    if self.esquerda is None:
        return self
    else:
        return self.esquerda._min()

def imprimeArvore(self, indent = 0):
    print ( "-" * indent + "|" + str(self.data))
    if self.esquerda:
        self.esquerda.imprimeArvore(indent + 2)
    if self.direita:
        self.direita.imprimeArvore(indent + 2)
arvore = None
for data in [15, 27, 49, 10, 8, 67, 59, 9, 13, 20, 14]:
if arvore:
   arvore.insere(data)
else:
  arvore = No(data)
arvore.imprimeArvore()
arvore.busca(1)

我认为问题是找不到密钥时返回，但我不确定，none 我试图阅读的类似问题帮助了我，我试图查看其他人的代码至少对我来说，我的代码应该可以工作。我做错了什么？还有另一种方法吗？

Answer 1

    def search(self, data):
   
      if self is None:
        return "the key doesn't exist"  
      elif data < self.data:
        return self.left.busca(data)
      elif data > self.data:
        return self.right.busca(data)
      else:
        return "the key exist"

如果搜索方法调用成功，self不是None。在对 search.

进行递归调用之前，您应该检查 self.left 是 None 还是 self.right 是 None

    def search(self, data):
   
      if data == self.data:
        return "the key exists"
       
      if data < self.data and self.left is not None:
        return self.left.busca(data)
      elif data > self.data and self.right is not None:
        return self.right.busca(data)
      else:
        return "the key exist"

我在 AVL 树搜索问题上遇到错误

I'm getting a error on an AVL tree search problem

python

search

avl-tree