Árvore binária de busca do tipo splay

Publicado por Ewerton Daniel de Lima (última atualização em 12/03/2010)

[ Hits: 8.846 ]

Download splay_tree.zip




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.

  



Esconder código-fonte

# -*- 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)

Scripts recomendados

Exercício com números randômicos - randint

Visualizar a data e hora de um servidor SNTP e atualizar na BIOS do sistema

Gerador de números para Mega-Sena

Probabilidade de Vencer - Poker Texas Hold

Intefacil QEmu em pygtk


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts