Mudar o método de inserção para ao invés de inserir e então procurar pelo nó desbalanceado (self.insert(data) + self.searchUnbalancedNode()) fazer com que a função de inserir retorne o nó avô do nó que foi inserido.
Dessa forma, será possível checar o caso mais simples de desbalanceamento que é com uma sub-árvore de profundidade 2. Caso haja desbalanceamento basta tratá-lo como feito anteriormente.
Implementação
Criar uma variável grandpa que aponta para self além do current, que será usado para percorrer a árvore em busca do lugar a inserir o nó, e usar um contador count que vai fazer grandpa começar a descer a árvore quando count > 2 . Esse contador garante que nos casos de borda, quando a profundidade for menor que 3, o nó raiz seja retornado.
Criar uma função auxiliar que vai dizer para qual dos dois filhos grandpa deverá descer.
Essa função deverá checar se current é um filho do filho esquerdo ou do filho direito de grandpa.
ENTRADA: nó de uma árvore, valor
PROCESSAMENTO: checagem
SAÌDA: true ou false
Resultado
Isso irá diminuir o tempo de complexidade gasto para inserir na árvore e fazer com que apenas uma simples substituição no método insertAVL aconteça, que é a remoção da chamada do método searchUnbalancedNode
Cinnamoon-dev
commented
10 months ago
Objetivo
Mudar o método de inserção para ao invés de inserir e então procurar pelo nó desbalanceado (
self.insert(data) + self.searchUnbalancedNode()) fazer com que a função de inserir retorne o nó avô do nó que foi inserido.Dessa forma, será possível checar o caso mais simples de desbalanceamento que é com uma sub-árvore de profundidade 2. Caso haja desbalanceamento basta tratá-lo como feito anteriormente.
Implementação
Criar uma variável
grandpaque aponta para self além docurrent, que será usado para percorrer a árvore em busca do lugar a inserir o nó, e usar um contadorcountque vai fazergrandpacomeçar a descer a árvore quandocount > 2. Esse contador garante que nos casos de borda, quando a profundidade for menor que 3, o nó raiz seja retornado.Criar uma função auxiliar que vai dizer para qual dos dois filhos
grandpadeverá descer. Essa função deverá checar securrenté um filho do filho esquerdo ou do filho direito degrandpa.ENTRADA: nó de uma árvore, valor PROCESSAMENTO: checagem SAÌDA: true ou false
Resultado
Isso irá diminuir o tempo de complexidade gasto para inserir na árvore e fazer com que apenas uma simples substituição no método
insertAVLaconteça, que é a remoção da chamada do métodosearchUnbalancedNode