Árvore binária de busca do tipo splay
Publicado por Ewerton Daniel de Lima (última atualização em 12/03/2010)
[ Hits: 8.848 ]
Olá pessoal, postei há pouco tem um gerador de referência cruzada que usa essa estrutura de árvores ( http://www.vivaolinux.com.br/script/Gerador-de-referencia-cruzada-de-texto ).
Resolvi postar aqui separadamente a estrutura da SplayTree em Python caso alguém necessite para outra aplicação.
Obs.: Desenvolvido em Python 3.1.
# -*- coding: utf-8 -*- """ Authors: Ewerton Lima, Fernando Rocha Date: 07/12/2009 Version: 1.0 """ from splay_tree_node import Node class SplayTree(object): """Implementa uma árvore binária de busca do tipo SplayTree.""" slots = ("__raiz", "__qtde") def __init__(self): self.__raiz = None self.__qtde = 0 def __len__(self): return self.__qtde @property def raiz(self): ''' Retorna valor do nó que está na raiz da árvore. ''' return self.__raiz.dado @property def altura(self, pont=None): ''' Retorna a altura da árvore. ''' if not pont: pont = self.__raiz def altura_aux(pont): ''' Método auxiliar do 'altura'. ''' if not pont: return 0 else: altura_dir = altura_aux(pont.dir) + 1 altura_esq = altura_aux(pont.esq) + 1 return altura_dir if altura_dir > altura_esq else altura_esq return altura_aux(pont) def remover_tudo(self): ''' Apaga a árvore inteira, setando o ponteiro da raíz para valor nulo. ''' self._raiz = None def esta_vazia(self): ''' Verifica se a árvore está vazia ou se contém elementos. Retorna True quando vazia e False para qualquer outro caso. ''' return self.__raiz == None def rotacionar_esquerda(self, pont=None, pont_ante=None): ''' Rotaciona para a esquerda um nó representado por ponteiro com o parâmetro 'pont' e o seu nó pai representado por ponteiro usando o parâmetro 'pont_ante'. ''' if pont_ante == self.__raiz: pont_temp = pont.esq pont.esq = pont_ante pont.pai = pont_ante.pai pont_ante.pai = pont pont_ante.dir = pont_temp if pont_temp: pont_temp.pai = pont_ante self.__raiz = pont else: pont_temp = pont.esq pont.esq = pont_ante pont.pai = pont_ante.pai pont_ante.pai = pont pont_ante.dir = pont_temp if pont_temp: pont_temp.pai = pont_ante if pont.pai.dado > pont.dado: pont.pai.esq = pont self.rotacionar_direita(pont, pont.pai) else: pont.pai.dir = pont self.rotacionar_esquerda(pont, pont.pai) def rotacionar_direita(self, pont=None, pont_ante=None): ''' Rotaciona para a direita um nó representado por ponteiro com o parâmetro 'pont' e o seu nó pai representado por ponteiro usando o parâmetro 'pont_ante'. ''' if pont_ante == self.__raiz: pont_temp = pont.dir pont.dir = pont_ante pont.pai = pont_ante.pai pont_ante.pai = pont pont_ante.esq = pont_temp if pont_temp: pont_temp.pai = pont_ante self.__raiz = pont else: pont_temp = pont.dir pont.dir = pont_ante pont.pai = pont_ante.pai pont_ante.pai = pont pont_ante.esq = pont_temp if pont_temp: pont_temp.pai = pont_ante if pont.pai.dado > pont.dado: pont.pai.esq = pont self.rotacionar_direita(pont, pont.pai) else: pont.pai.dir = pont self.rotacionar_esquerda(pont, pont.pai) def splay(self, pont): ''' Faz o procedimento de Splay, baseando-se no ponteiro do elemento sobre o qual objetiva-se fazer o splay. Verifica qual é a necessidade de rotação do nó (para esquerda ou para direita) e faz a rotação. ''' pont_ante = pont.pai if not (pont and pont_ante): return if pont == pont_ante.dir: self.rotacionar_esquerda(pont, pont_ante) else: self.rotacionar_direita(pont, pont_ante) def inserir(self, dado): ''' Insere o elemento na árvore obedecendo às propriedades de uma árvore binária de busca, fazendo ainda o splay no final. Mantém assim as propriedades de uma SplayTree. ''' nodo = Node(dado) if not self.__raiz: self.__raiz = nodo else: pont = self.__raiz pont_ante = self.__raiz while pont: pont_ante = pont if pont.dado > dado: pont = pont.esq else: pont = pont.dir if pont_ante.dado > dado: pont_ante.esq = nodo else: pont_ante.dir = nodo nodo.pai = pont_ante self.__qtde += 1 self.splay(nodo) def antecessor(self, pont): '''Baseando-se no ponteiro representado pelo parâmetro 'pont', retorna o ponteiro para maior elemento da subárvore da esquerda, caso exista e também o ponteiro de seu nó pai. ''' antecessor = pont.esq pont_ante = pont while antecessor.dir: pont_ante = antecessor antecessor = antecessor.dir return antecessor, pont_ante def remover(self, objetivo, pont=None, pont_ante=None): ''' Utiliza os ponteiros 'pont' e 'pont_ante' para efetuar a remoção de determinado elemento. Caso não tenha os ponteiros, pode ser passado o valor do elemento no parâmetro 'objetivo'. Neste caso, será feita a busca pelos ponteiros na árvore, obedecendo às propriedades de uma árvore binária de busca, fazendo ainda o splay no final. Mantém assim as propriedades de uma SplayTree. ''' if not pont: pont = self.buscar_sem_splay(objetivo) pont_ante = pont.pai if pont: #Caso em que é folha if not (pont.esq or pont.dir): if pont_ante.dir == pont: pont_ante.dir = None else: pont_ante.esq = None self.splay(pont) #Caso em que não existe o filho da direita elif not pont.dir: pont.dado = pont.esq.dado self.remover(objetivo, pont.esq, pont) #Caso em que não existe o filho da esquerda elif not pont.esq: pont.dado = pont.dir.dado self.remover(objetivo, pont.dir, pont) #Caso em que existem ambos os filhos else: antecessor, pont_ante = self.antecessor(pont) pont.dado = antecessor.dado self.remover(objetivo, antecessor, pont_ante) self.__qtde -= 1 def buscar(self, objetivo): ''' Faz a busca do valor representado pelo parâmetro 'objetivo', baseando-se nas propriedades de uma árvore binária de busca, fazendo ainda o splay do nó no final, se este for encontrado. Mantém assim as propriedades de uma SplayTree. Retorna o ponteiro do nó (que será a raiz após o splay). Se não for encontrado o elemento retornará None. ''' pont = self.__raiz if pont: while pont and pont.dado != objetivo: if pont.dado > objetivo: pont = pont.esq else: pont = pont.dir if pont: self.splay(pont) return pont else: return None def buscar_sem_splay(self, objetivo): ''' Faz a busca do valor representado pelo parâmetro 'objetivo', baseando-se nas propriedades de uma árvore binária de busca, NÃO faz o splay do nó no final. Mais utilizado dentro da classe. Retorna o ponteiro do nó buscado ou None se não for encontrado. ''' pont = self.__raiz if pont: while pont and pont.dado != objetivo: if pont.dado > objetivo: pont = pont.esq else: pont = pont.dir if pont: return pont else: return None def caminhar(self, tipo=1, funcao=None): ''' Faz o caminhamento em todos os itens da árvore e executa a função especificada no parâmetro funcao. Para o parâmetro "tipo" são válidas três opções: 1. Em ordem 2. Pré-ordem 3. Pós-ordem ''' if not funcao: funcao = self.print_dado def caminhar_aux(pont, tipo, func): ''' Método auxiliar do 'caminhar'. ''' if pont: if tipo == 2: func(pont) caminhar_aux(pont.esq, 1, func) if tipo == 1: func(pont) caminhar_aux(pont.dir, 1, func) if tipo == 3: func(pont) caminhar_aux(self.__raiz, tipo, funcao) def print_dado(self, pont): ''' Imprime o dado do ponteiro representado pelo parâmetro 'pont'. ''' print(pont.dado)
Veja a versão das principais distrubuições.
Nenhum comentário foi encontrado.
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
E a guerra contra bots continua
Tradução do artigo do filósofo Gottfried Wilhelm Leibniz sobre o sistema binário
Conheça o firewall OpenGFW, uma implementação do (Great Firewall of China).
Instalando o FreeOffice no LMDE 6
Anki: Remover Tags de Estilo HTML de Todas as Cartas
Colocando uma opção de redimensionamento de imagem no menu de contexto do KDE
Criar um script para testar pen drive (5)
Não consigo acessar os modos de desempenho (0)
Problema com alias usando locate (4)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba