Vermelho Preto Árvore de Rotações e a Cor Vira

Thamindu Dilshan Jayawickrama
Thamindu Dilshan Jayawickrama

Siga

Jul 11, 2020 · 6 min de leitura

Uma busca típica árvore, como Árvore de Busca Binária (BST) poderia executar uma altura de O(n), o que poderia resultar no pior caso de tempo de complexidade O(n) para operações básicas de busca, inserção, exclusão, etc. Isso depende inteiramente da ordem dos itens que estão sendo inseridos no BST. Mas, há certas situações em que não temos todo o item definido Ao começar a construir a árvore. É aí que as árvores de busca equilibradas entram em jogo. Em uma árvore de busca balanceada, uma altura de o(log n) é garantida ao implementar um conjunto dinâmico de itens n. Árvores vermelhas-pretas, árvores AVL, 2-3 árvores, e árvores B são alguns dos exemplos para implementações de árvores de busca balanceadas. Este artigo é sobre as operações de modificação de árvores envolvidas com árvores vermelhas-pretas.

Uma Árvore Vermelha-Preta (RB-Tree) é uma árvore de busca binária de auto-equilíbrio onde cada nó segue um conjunto de regras. Cada nó em uma árvore RB tem um atributo extra; a cor, que pode ser vermelha ou preta. Em uma implementação típica RB-Tree, haverá um conjunto de nós sentinelas para sinalizar que um nó folha é alcançado. Esses nós são referidos como NULLs (ou NILs) e considerados como nós folha neste artigo. Abaixo estão o conjunto de regras ou as propriedades que cada nó deve seguir.

  1. cada nó é vermelho ou preto.2. A raiz e as folhas são pretas.3. Se um nó é vermelho, então seu pai é preto.4. Todos os caminhos simples de qualquer nó para uma folha descendente têm o mesmo número de nós Negros (altura Negra).

    A altura de um RB-Árvore permanece em O(n log n) depois de cada árvore modificação da operação, que resultou em um garantida limite superior de S(n log n) para essas operações. As operações inserir e excluir causam modificações na árvore RB. Após cada operação de modificação de árvore, a árvore será auto-balanceada através de mudanças de cor e rotações. Antes de entrar nessas operações, devemos estar familiarizados com a seguinte notação.

    Uma rotação é uma operação especial concebidos para auto balanceamento de Árvores de Busca Binária que pode ser realizada em O(1) hora. Uma propriedade interessante sobre rotações é que preserva a ordem que atravessa as chaves (ordenando as chaves).

    A decisão de executar uma rotação ou uma mudança de cor é baseado na tia do considerado nó (o nó atual). Se o nódulo tem uma tia Negra, fazemos uma rotação. Se o nódulo tiver uma tia vermelha, fazemos uma inversão de cores. Depois de fazer uma rotação, devemos colorir a árvore. Depois de realizar essas operações, a árvore deve ser terminada como abaixo.

    Se o nó atual é filho à esquerda de seu avô esquerda criança, podemos rodar o avô de todo o pais. Se o nó atual é o filho direito do Filho direito de seu avô, nós deixamos girar o avô em torno do Pai. Se o nó atual é o filho direito do filho esquerdo de seu avô, fazemos uma rotação esquerda-direita onde rodamos o avô e a criança em torno do Pai. Se o nó atual é o filho esquerdo do Filho direito de seu avô, fazemos uma rotação direita-esquerda onde rodamos o avô e a criança em torno do Pai. Todas as rotações podem ser resumidas como para o diagrama abaixo.

    Um fato importante a lembrar é que, após a realização de qualquer árvore operação de modificação, você deve validar a árvore contra o conjunto de regras para saber se a quaisquer violações estão lá. Se existe uma violação (ex: raiz é vermelha) você deve corrigi-la. Agora vamos construir uma simples RB-Tree inserindo abaixo do conjunto de teclas. Note que por simplicidade, nós de folhas (nulos) são ignorados em diagramas abaixo.

    5, 8, 1, 10, 9, 15, 20

    devemos inserir cada tecla como um nó vermelho. Portanto, inserimos 5 como um nó vermelho e imediatamente colori-lo de volta para preto como é o nó raiz. Então inserimos 8 Como filho direito do nó 5. seguimos a propriedade BST básica quando inserimos as chaves. Inserir 1 é o mesmo que inserir 8.

    em seguida, devemos inserir 10 8 direito da criança. Inserimo-lo como um nó vermelho e verificamos se há violações. Tanto o 8 como o 10 são nódulos vermelhos e está a violar a 3ª propriedade. Devíamos ver se a tia está vermelha. Então fazemos um flip colorido. Após a mudança de cor, podemos ver que o nó raiz é vermelho e está violando a segunda propriedade. Então corrigimo-lo mudando a cor do nó raiz.

    em seguida, devemos inserir a chave 9. Após a inserção, podemos ver que ambos 9 e 10 nós são vermelhos e está violando a segunda propriedade. Nós verificamos para a tia e como é preto (NULL são pretos), nós realizamos uma rotação direita-esquerda (a violação está na sub-árvore esquerda da criança direita). Depois da rotação, devíamos fazer uma correcção de cores.

    Agora vamos inserir a chave 15. Após a inserção, podemos ver que dois nós vermelhos consecutivos estão lá e a tia dos 15 é um nó vermelho. Então, devíamos fazer uma inversão de cores. Depois disso, verificamos se há violações e podemos descobrir que não há violações.

    Agora vamos inserir a chave de 20 a árvore. Após a inserção, podemos ver que a tia é negra e, portanto, devemos realizar uma rotação à esquerda (violação está na sub-árvore direita da criança). Depois da rotação, devíamos fazer uma correcção de cores.

    neste artigo, nós olhamos para uma determinada auto-balanceamento de árvore de busca binária; Red-Black Tree. É garantido que eles têm uma altura de O (log n), Portanto, tendo uma complexidade de tempo no pior caso de o(log n) para Operações básicas de árvore. Árvores vermelhas-pretas são particularmente úteis em muitas aplicações de ciência da computação. C++ Standard Template Library (STL) has set, multiset, map, and multimap based on RB-Trees. Além disso, o TreeMap em Java language é uma implementação de navegador baseada em RB-Tree.

Deixe uma resposta

O seu endereço de email não será publicado.