Árvore binária de busca do tipo splay
Publicado por Perfil removido (última atualização em 12/03/2010)
[ Hits: 8.956 ]
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)
Just Do It - XML Generic Editor
Nenhum comentário foi encontrado.
Atenção a quem posta conteúdo de dicas, scripts e tal (6)
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
O mínimo que você precisa saber sobre o terminal (parte 2)
O mínimo que você precisa saber sobre o terminal (parte 1)
Como iniciar uma máquina virtual do VirtualBox automaticamente no boot do LUbuntu 18 LTS
Mudar o gerenciador de login (GDM para SDDM e vice-versa) - parte 2
Como deixar as abas do Firefox mais fininhas
Mudar o gerenciador de login (GDM para SDDM)
"Tentando" fazer com que programas rodem no Wayland e no X11
Acesso a Pasta compartilhada do samba (6)
samba4 GPO politicas paou de funcionar e regras (7)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta