Arvores.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Árvores\n",
    "\n",
    "### *Conceito*\n",
    "\n",
    "Árvore, é uma das mais importantes estruturas de dados não lineares. Conceitualmente diferente das listas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica, seus elementos se encontram \"acima\" ou \"abaixo\" de outros elementos da árvore. Uma terminologia muito utilizada nas estruturas de árvores tem origem das árvores genealógicas. O relacionamento entre nós é descrito com os termos \"pai\" (ou \"mãe\") para os antecessores diretos de um nó, \"filhos\" (ou \"filhas\") para os descendentes diretos e \"irmãos\" (ou \"irmãs\") para toi.e., dos os nós com mesmo pai.\n",
    "\n",
    "São estruturas eficientes e simples em relação ao tratamento computacional, diferentemente dos grafos. Há inúmeros problemas no mundo real que podem ser modelados e resolvidos através das árvores. Estruturas de pastas de um sistema operacional, interfaces gráficas, bancos de dados e sites da internet são exemplos de aplicações de árvores.\n",
    "\n",
    "Uma árvore é formada por um conjunto de elementos que armazenam informações chamados nós. Toda árvore possui o elemento chamado raiz, que possui ligações para outros elementos denominados ramos ou filhos. Estes filhos podem estar ligados a outros elementos que também podem possuir outros filhos. O elemento que não possui filhos é conhecido como nó folha.\n",
    "\n",
    "### *Definição*\n",
    "\n",
    "Formalmente, definimos uma árvore **T** como um conjunto finito de zero ou mais nós tal que:\n",
    "\n",
    " * Se o número de nós = 0, temos uma árvore vazia, ou\n",
    " * Se o número de nós > 0\n",
    "     * existe um nó especialmente denominado raiz de T\n",
    "     * os nós restantes formam **_m ≥ 0_** conjuntos disjuntos **_P1, P2, P3,...,Pm_**, cada um desses conjuntos é uma árvore em si, chamada subárvore da raiz de **T**, ou simplesmente subárvore.\n",
    "\n",
    "O número máximo de filhos em um nó é chamado ordem da árvore. Uma árvore binária é aquela de ordem 2, portanto uma árvore em que cada elemento possui no máximo 2 filhos.\n",
    "\n",
    "### *Travessia*\n",
    "\n",
    "Uma das operações importantes consiste em percorrer cada elemento da árvore uma única vez. Esse percurso, também chamado de travessia da árvore, pode ser feito em pré-ordem (os filhos de um nó são processados após o nó) ou em pós-ordem (os filhos são processados antes do nó). Em árvores binárias é possível ainda fazer uma travessia em-ordem, em que se processa o filho à esquerda, o nó, e finalmente o filho à direita.\n",
    "\n",
    "![](./assets/tree12.gif)\n",
    "\n",
    "* Pré-ordem:\n",
    "    1. Vistar a raiz.\n",
    "    2. Percorrer a sua subárvore esquerda em pré-ordem.\n",
    "    3. Percorrer a sua subárvore direita em pré-ordem.\n",
    "    \n",
    " A travessiva em pré-ordem é: 1, 2, 4, 5, 3\n",
    " \n",
    "\n",
    "* Em ordem:\n",
    "    1. Visitar nó mais a esquerda possível.\n",
    "    2. Visitar raiz do nó do passa anterior.\n",
    "    3. Visitar o nó a direita da raiz do passo anterior.\n",
    "    \n",
    " A travessiva em ordem é: 4, 2, 5, 1, 3\n",
    " \n",
    "    \n",
    "* Pós-ordem:\n",
    "    1. Visitar nó mais a esquerda possível.\n",
    "    2. Visitar nó a direita.\n",
    "    3. Visitar a raiz dos nós dos passos anteriores.\n",
    "    \n",
    " A travessia em pós-ordem é: 4, 5, 2, 3, 1\n",
    "\n",
    "\n",
    "## Árvore binária\n",
    "\n",
    "### *Conceito*\n",
    "\n",
    "Uma árvore binária é uma árvore a qual atende a propriedade de ter ordem 2 portanto uma árvore em que cada elemento possui no máximo 2 filhos. Uma árvore \"estritamente binária\" é uma árvore na qual todo nó tem zero ou duas folhas. Existem autores, porém, que adotam essa definição para o termo completa, e utilizam o termo quase completa para árvores em que os níveis podem possuir ou não dois elementos.\n",
    "\n",
    "Os nós de uma árvore binária possuem graus zero, um ou dois. Um nó de grau zero é denominado folha.\n",
    "\n",
    "Em uma árvore binária, por definição, cada nó poderá ter até duas folhas, sendo que ela se compara com a ABB (árvore binária de busca), apesar de não ter a propriedade da mesma (\"na abb, existe uma regra na inserção\").\n",
    "\n",
    "A profundidade de um nó é a distância deste nó até a raiz. Um conjunto de nós com a mesma profundidade é denominado nível da árvore. A maior profundidade de um nó, é a altura da árvore.\n",
    "\n",
    "\n",
    "### *Definição*\n",
    "\n",
    "Uma árvore binária é uma estrutura de dados caracterizada por:\n",
    "\n",
    " * Ou não tem elemento algum (árvore vazia).\n",
    " * Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.\n",
    "\n",
    "Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores binárias de busca\n",
    "\n",
    "### *Inserção*\n",
    "\n",
    "A idéia é fazer a tarvessia da árvore em ordem  usando fila. Se encontrarmos um nó cujo filho esquerdo está vazio, criamos uma nova chave como filho da esquerda do nó. Senão, se encontrarmos um nó cujo filho a direita está vazio, fazemos nova chave como filho a direita. Continuamos a percorrer a árvore até encontrarmos um nó cuja esquerda ou direita está vazia."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Novo nó"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class newNode():  \n",
    "  \n",
    "    def __init__(self, data):  \n",
    "        self.key = data \n",
    "        self.left = None\n",
    "        self.right = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Travessia em Ordem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inorder(temp): \n",
    "  \n",
    "    if (not temp): \n",
    "        return\n",
    "  \n",
    "    inorder(temp.left)  \n",
    "    print(temp.key,end = \" \") \n",
    "    inorder(temp.right)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inserção"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_bin(temp,key): \n",
    "  \n",
    "    q = []  \n",
    "    q.append(temp)  \n",
    "    \n",
    "    # Faça a travessia em ordem de nível até \n",
    "    # encontrarmos um lugar vazio.  \n",
    "    while (len(q)):  \n",
    "        temp = q[0]  \n",
    "        q.pop(0)  \n",
    "  \n",
    "        if (not temp.left): \n",
    "            temp.left = newNode(key)  \n",
    "            break\n",
    "        else: \n",
    "            q.append(temp.left)  \n",
    "  \n",
    "        if (not temp.right): \n",
    "            temp.right = newNode(key)  \n",
    "            break\n",
    "        else: \n",
    "            q.append(temp.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exemplo de árvore binária\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Travessia em ordem antes da inserção: 7 11 10 15 9 8 \n",
      "Travessia em ordem após a inserção: 7 11 12 10 15 9 8 "
     ]
    }
   ],
   "source": [
    "root = newNode(10)  \n",
    "root.left = newNode(11)  \n",
    "root.left.left = newNode(7)  \n",
    "root.right = newNode(9)  \n",
    "root.right.left = newNode(15)  \n",
    "root.right.right = newNode(8)  \n",
    "  \n",
    "print(\"Travessia em ordem antes da inserção:\", end = \" \") \n",
    "inorder(root)  \n",
    "  \n",
    "key = 12\n",
    "insert_bin(root, key)  \n",
    "\n",
    "print()\n",
    "print(\"Travessia em ordem após a inserção:\", end = \" \") \n",
    "inorder(root) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### *Remoção*\n",
    "\n",
    "Dada uma árvore binária, remova um nó dela certificando-se de que a árvore encolhe a partir da parte inferior (isto é, o nó excluído é substituído pelo nó mais inferior e mais à direita)\n",
    "\n",
    "Ex:\n",
    "\n",
    "Remova o 10 na árvore 1. e remova o 20 na árvore 2.:\n",
    "       1.                                                                  2.\n",
    "       \n",
    "         10                                                                  10\n",
    "        /  \\                                                                /  \\\n",
    "      20    30                                                            20    30\n",
    "                                                                                  \\\n",
    "                                                                                   40\n",
    "                                                                                   \n",
    "Resultado:\n",
    "       1.                                                                   2.\n",
    "       \n",
    "         30                                                                   10\n",
    "        /                                                                    /  \\\n",
    "      20                                                                   40    30"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Código remoção\n",
    "\n",
    "#### Função a qual deleta o mais profundo a direita"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def deleteDeepest(root,d_node): \n",
    "    q = [] \n",
    "    q.append(root) \n",
    "    while(len(q)): \n",
    "        temp = q.pop(0) \n",
    "        if temp is d_node: \n",
    "            temp = None\n",
    "            return\n",
    "        if temp.right: \n",
    "            if temp.right is d_node: \n",
    "                temp.right = None\n",
    "                return\n",
    "            else: \n",
    "                q.append(temp.right) \n",
    "        if temp.left: \n",
    "            if temp.left is d_node: \n",
    "                temp.left = None\n",
    "                return\n",
    "            else: \n",
    "                q.append(temp.left)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Função que apaga o elemento e o subtitui pelo mais profundo a direita"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def deletion(root, data): \n",
    "    q = [] \n",
    "    q.append(root) \n",
    "    while(len(q)): \n",
    "        temp = q.pop(0) \n",
    "        if temp.key == data: \n",
    "            key_node = temp \n",
    "        if temp.left: \n",
    "            q.append(temp.left) \n",
    "        if temp.right: \n",
    "            q.append(temp.right) \n",
    "    x = temp.key\n",
    "    deleteDeepest(root,temp) \n",
    "    key_node.key = x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exemplo de Remoção"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A árvore antes da remoção:\n",
      "7 11 12 10 15 9 8 \n",
      "A árvore após a remoção;\n",
      "7 8 12 10 15 9 "
     ]
    }
   ],
   "source": [
    "root = newNode(10) \n",
    "root.left = newNode(11) \n",
    "root.left.left = newNode(7) \n",
    "root.left.right = newNode(12) \n",
    "root.right = newNode(9) \n",
    "root.right.left = newNode(15) \n",
    "root.right.right = newNode(8) \n",
    "print(\"A árvore antes da remoção:\") \n",
    "inorder(root) \n",
    "key = 11\n",
    "deletion(root, key) \n",
    "print() \n",
    "print(\"A árvore após a remoção;\") \n",
    "inorder(root) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AVL\n",
    "\n",
    "Para garantir essa propriedade, a cada inserção ou remoção o fator de balanço deve ser atualizado a partir do pai do nó inserido até a raiz da árvore. Na inserção basta encontrar o primeiro nó desregulado (fb= -2 ou fb= 2), aplicar o operação de rotação necessária, não havendo necessidade de verificar os demais nós. Na remoção a verificação deverá prosseguir até a raiz, podendo requerer mais de uma rotação.\n",
    "\n",
    "### *Conceito*\n",
    "\n",
    "Árvore AVL é uma árvore binária de busca balanceada, ou seja, uma árvore balanceada (árvore completa) é a árvore que minimiza o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrências idênticas. Contudo, para garantir essa propriedade em aplicações dinâmicas, é preciso reconstruir a árvore para seu estado ideal a cada operação sobre seus nós (inclusão ou exclusão), para ser alcançado um custo de algoritmo com o tempo de pesquisa tendendo a *O(log n)*.\n",
    "\n",
    "As operações de busca, inserção e remoção de elementos possuem complexidade *O(log n)* (no qual *n* é o número de elementos da árvore), que são aplicados a árvore de busca binária.\n",
    "\n",
    "O nome AVL vem de seus criadores soviéticos Adelson Velsky e Landis, e sua primeira referência encontra-se no documento \"Algoritmos para organização da informação\" de 1962.\n",
    "\n",
    "### *Definição*\n",
    "\n",
    "Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.\n",
    "\n",
    "Pela definição fica estabelecido que todos os nós de uma árvore AVL devem respeitar a seguinte propriedade:\n",
    "\n",
    "* |hd(u) - he(u)| ≤ 1, onde hd(u) é a altura da subárvore direita do nó u e he(u) é a altura da subárvore esquerda do nó u.\n",
    "\n",
    "O valor hd(u) - he(u) é denominado fator de balanço do nó. Quando um nó possui fator de balanço com valor -1, 0 ou 1 então o mesmo é um nó balanceado, caso seja -2 ou +2 então o nó esta desbalanceado. Todos os nós de uma árvore AVL são balanceados, caso contrário a árvore não é AVL. \n",
    "\n",
    "O sinal do fator de baleceamento de cada nó é interpretado como o peso a direita ou a esquerda daquele nó, caso o fator seja positivo ( + ) então o peso da subárvore a direita é maior, caso seja negativo ( - ) o peso da subárvore a esquerda é maior.\n",
    "\n",
    "### *Balanceamento*\n",
    "\n",
    "Por definição, todos os nós da AVL devem ter fb = -1, 0 ou 1.\n",
    "\n",
    "Para garantir essa propriedade, a cada inserção ou remoção o fator de balanço deve ser atualizado a partir do pai do nó inserido até a raiz da árvore. Na inserção basta encontrar o primeiro nó desregulado (fb= -2 ou fb= 2), aplicar o operação de rotação necessária, não havendo necessidade de verificar os demais nós. Na remoção a verificação deverá prosseguir até a raiz, podendo requerer mais de uma rotação.\n",
    "\n",
    "### *Rotações*\n",
    "\n",
    "Existem dois tipo de rotações, a direita e a esquerda, a diferença entre ela está em qual nó sera subtituido, a direita ou a esquerda. Qual das duas rotações usar está associado ao fator de balanceamento do nó desbalanceado e seu filho a esquerda, seguindo a seguinte tabela:\n",
    "\n",
    "|Fator de balanceamento|Filho|Rotação|\n",
    "|--|--|--|\n",
    "| +2 | +1 | Esquerda |\n",
    "| -2 | -1 | Direita |\n",
    "| +2 | -1 | Direita -> Esquerda |\n",
    "| -2 | +1 | Esquerda -> Direita |\n",
    "\n",
    "Para os casos onde os sinais de pai e filho são inversos é necessário aplicar a rotação duas vezes, quando o pai for positivo quer dizer que o peso da subarvore direita é maior, logo a primeira rotação é para direita e se o filho for negativo quer dizer que o peso da subárvore a esquerda do nó filho é maior, aplica-se a rotação a esquerda. O inverso é valido, para pai e filhos com sinais de balanceamento -, + respectivamente, portanto uma rotação a esquerda seguida por outra a direita.\n",
    "\n",
    "#### Rotação a direita\n",
    "\n",
    "A rotação a direita é feita da seguinte forma:\n",
    "\n",
    "1. O nó desbalanceado desloca-se para esquerda e depois a direita.\n",
    "2. O nó que estava a direita do nó desbalanceado desloca-se a esquerda e duas vezes a direita, se posicionando novamente a direita do nó que estava desbalanceado.\n",
    "3. Por fim o nó que estava a direita do filho do nó desbalanceado se posiciona a esquerda do que estava desbalanceado.\n",
    "    \n",
    "![](./assets/rot-dir1.png)\n",
    "![](./assets/rot-dir2.png)\n",
    "\n",
    "#### Rotação a Esquerda\n",
    "\n",
    "A rotação a esquerda é exatamente o contrário da direita, é feita da seguinte forma:\n",
    "\n",
    "1. O nó desbalanceado desloca-se para direita e depois a esquerda.\n",
    "2. O nó que estava a esquerda do nó desbalanceado desloca-se a direita e duas vezes a esquerda, se posicionando novamente a esquerda do nó que estava desbalanceado\n",
    "3. Por fim o nó que estava a esquerda do filho do nó desbalanceado se posiciona a direita do que estava desbalanceado.\n",
    "\n",
    "![](./assets/rot-esq1.png)\n",
    "![](./assets/rot-esq2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Classe Árvore AVL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class AVL_Tree(object): \n",
    "    \n",
    "    # Inserção\n",
    "    def insert(self, root, key): \n",
    "      \n",
    "    # Passo 1 - Inserção de árvore binária de busca \n",
    "        if not root: \n",
    "            return TreeNode(key) \n",
    "        elif key < root.val: \n",
    "            root.left = self.insert(root.left, key) \n",
    "        else: \n",
    "            root.right = self.insert(root.right, key) \n",
    "  \n",
    "        # Passo 2 - Atualizar a altura do no pai\n",
    "        root.height = 1 + max(self.getHeight(root.left), \n",
    "                            self.getHeight(root.right)) \n",
    "  \n",
    "        # Passo 3 - Achar fator de balanceamento\n",
    "        balance = self.getBalance(root) \n",
    "  \n",
    "        # Passo 4 - Se o nó é desbalanceado,  \n",
    "        # então tente um dos 4 casos \n",
    "        \n",
    "        # Caso 1 - Esquerda \n",
    "        if balance > 1 and key < root.left.val: \n",
    "            return self.rightRotate(root) \n",
    "  \n",
    "        # Caso 2 - Direita\n",
    "        if balance < -1 and key > root.right.val: \n",
    "            return self.leftRotate(root) \n",
    "  \n",
    "        # Caso 3 - Esquerda, Direita \n",
    "        if balance > 1 and key > root.left.val: \n",
    "            root.left = self.leftRotate(root.left) \n",
    "            return self.rightRotate(root) \n",
    "  \n",
    "        # Caso 4 - Direita, Esquerda \n",
    "        if balance < -1 and key < root.right.val: \n",
    "            root.right = self.rightRotate(root.right) \n",
    "            return self.leftRotate(root) \n",
    "        \n",
    "        return root\n",
    "    \n",
    "    # Achar fator de balanceamento\n",
    "    def getBalance(self, root): \n",
    "        if not root: \n",
    "            return 0\n",
    "  \n",
    "        return self.getHeight(root.left) - self.getHeight(root.right)\n",
    "\n",
    "    # Rotação a Direita\n",
    "    def rightRotate(self, z): \n",
    "  \n",
    "        y = z.left \n",
    "        T3 = y.right \n",
    "  \n",
    "        # Realiza a rotação \n",
    "        y.right = z \n",
    "        z.left = T3 \n",
    "  \n",
    "        # Atualiza os pesos \n",
    "        z.height = 1 + max(self.getHeight(z.left), \n",
    "                        self.getHeight(z.right)) \n",
    "        y.height = 1 + max(self.getHeight(y.left), \n",
    "                        self.getHeight(y.right))\n",
    "        \n",
    "        # Retorna a nova raiz\n",
    "        return y\n",
    "\n",
    "    # Achar Altura\n",
    "    def getHeight(self, root): \n",
    "        if not root: \n",
    "            return 0\n",
    "  \n",
    "        return root.height \n",
    "\n",
    "    # Travessia em Pré-ordem\n",
    "    def preOrder(self, root): \n",
    "  \n",
    "        if not root: \n",
    "            return\n",
    "  \n",
    "        print(\"{0} \".format(root.val), end=\"\") \n",
    "        self.preOrder(root.left) \n",
    "        self.preOrder(root.right) \n",
    "        \n",
    "    # Rotação a Esquerda\n",
    "    def leftRotate(self, z): \n",
    "  \n",
    "        y = z.right \n",
    "        T2 = y.left \n",
    "  \n",
    "        # Realiza a rotação \n",
    "        y.left = z \n",
    "        z.right = T2 \n",
    "  \n",
    "        # Atualiza os pesos \n",
    "        z.height = 1 + max(self.getHeight(z.left), \n",
    "                         self.getHeight(z.right)) \n",
    "        y.height = 1 + max(self.getHeight(y.left), \n",
    "                         self.getHeight(y.right)) \n",
    "  \n",
    "        # Retorna a nova raiz \n",
    "        return y\n",
    "    \n",
    "# Nó\n",
    "class TreeNode(object): \n",
    "    def __init__(self, val): \n",
    "        self.val = val \n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.height = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exemplo de AVL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A travessia em pré-ordem árvore AVL construida é:\n",
      "30 20 10 25 40 50 \n"
     ]
    }
   ],
   "source": [
    "myTree = AVL_Tree() \n",
    "root = None\n",
    "  \n",
    "root = myTree.insert(root, 10) \n",
    "root = myTree.insert(root, 20) \n",
    "root = myTree.insert(root, 30) \n",
    "root = myTree.insert(root, 40) \n",
    "root = myTree.insert(root, 50) \n",
    "root = myTree.insert(root, 25) \n",
    "  \n",
    "\"\"\"A árvore AVL deve ser:\n",
    "\n",
    "            30 \n",
    "           /  \\ \n",
    "         20   40 \n",
    "        /  \\     \\ \n",
    "       10  25    50\n",
    "\"\"\"\n",
    "  \n",
    "# Travessia em pré-ordem \n",
    "print(\"A travessia em pré-ordem árvore AVL construida é:\") \n",
    "myTree.preOrder(root) \n",
    "print() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Árvore rubro-negra\n",
    "\n",
    "### **_Conceito_**\n",
    "\n",
    "Uma árvore rubro-negra é um tipo de árvore binária de busca balanceada, uma estrutura de dados usada em ciência da computação, tipicamente para implementar vetores associativos. A estrutura original foi inventada em 1972, por Rudolf Bayer que a chamou de \"Árvores Binárias B Simétricas\", mas adquiriu este nome moderno em um artigo de 1978 escrito por Leonidas J. Guibas e Robert Sedgewick. Ela é complexa, mas tem um bom pior-caso de tempo de execução para suas operações e é eficiente na prática: pode-se buscar, inserir, e remover em tempo *O(log n)*. De maneira simplificada, uma árvore rubro-negra é uma árvore de busca binária que insere e remove de forma inteligente, para assegurar que a árvore permaneça aproximadamente balanceada.\n",
    "\n",
    "Árvores rubro-negras, como todas as árvores binárias de busca, permitem travessia em-ordem de elementos de maneira eficiente, pois é possível acessar o pai de qualquer nó. O tempo de busca resulta da travessia da raiz a folha, desta forma uma árvore balanceada, tendo a menor altura possível, resulta em tempo de busca *O(log n)*. Nas árvores rubro-negras, os nós folhas não são relevantes e não contém dados. Estas folhas não precisam ser mantidas em memória de computador - basta apenas um ponteiro para nulo para identificá-las — mas algumas operações em árvores rubro-negras são simplificadas se os nós folha forem explicitados. Para economizar memória, algumas vezes um nó sentinela interpreta o papel de todos os nós folha; todas as referências dos nós internos para os nós folha apontam para o nó sentinela.\n",
    "\n",
    "### **_Definição_**\n",
    "\n",
    "Uma árvore rubro-negra é uma árvore de busca binária onde cada nó tem um atributo de cor, vermelho ou preto. Além dos requisitos ordinários impostos pelas árvores de busca binárias, as árvores rubro-negras tem os seguintes requisitos adicionais:\n",
    "\n",
    "1. Um nó é vermelho ou preto.\n",
    "2. A raiz é preta. (Esta regra é usada em algumas definições. Como a raiz pode sempre ser alterada de vermelho para preto, mas não sendo válido o oposto, esta regra tem pouco efeito na análise.)\n",
    "3. Todas as folhas(nil) são pretas.\n",
    "4. Ambos os filhos de todos os nós vermelhos são pretos.\n",
    "5. Todo caminho de um dado nó para qualquer de seus nós folhas descendentes contem o mesmo número de nós pretos.\n",
    "\n",
    "Essas regras asseguram uma propriedade crítica das árvores rubro-negras: que o caminho mais longo da raiz a qualquer folha não seja mais do que duas vezes o caminho mais curto da raiz a qualquer outra folha naquela árvore. O resultado é que a árvore é aproximadamente balanceada. Como as operações de inserção, remoção, e busca de valores necessitam de tempo de pior caso proporcional à altura da árvore, este limite proporcional a altura permite que árvores rubro-negras sejam eficientes no pior caso, diferentemente de árvore de busca binária.\n",
    "\n",
    "Para perceber por que essas propriedades garantem isto, basta observar que nenhum caminho pode ter dois nós vermelhos sucessivos, devido à propriedade 4. O caminho mais curto possível tem todos os nós pretos, e o caminho mais longo possível alterna entre nós vermelhos e pretos. Desde que todos os caminhos máximos têm o mesmo número de nós pretos, pela propriedade 5, isto mostra que nenhum caminho é mais do que duas vezes mais longo que qualquer outro caminho.\n",
    "\n",
    "Em muitas das representações de estruturas de dados em árvore, é possível para um nó pai ter só um filho, e os nós folha contêm dados. É possível representar árvores rubro-negras neste paradigma, mas ele modifica várias propriedades e deixa os algoritmos mais complexos. Por essa razão, este artigo usa \"folhas nulas\", que não contêm nenhum dado e simplesmente servem para indicar onde a árvore termina, como mostrado acima. Esses nós muitas vezes são omitidos dos desenhos, resultando em uma árvore que parece contradizer os princípios acima mencionados, mas que de fato não faz. Uma conseqüência disto é que todo nó interno (não-folha) têm dois filhos, embora um ou ambos filhos possam ser folhas nulas.\n",
    "\n",
    "Alguns explicam uma árvore rubro-negra como uma árvore de busca binária cujas bordas, em vez de nós, são coloridas em vermelho ou preto, mas isto não faz nenhuma diferença. A cor de um nó na terminologia deste artigo corresponde à cor da borda que une o nó ao seu pai, exceto que o nó de raiz é sempre preto (propriedade 2) ao passo que a borda correspondente não existe.\n",
    "\n",
    "### **_Altura do nó_**\n",
    "\n",
    "A altura de um nó nas árvores rubro-negras é calculada através da quantidade de nós pretos que o caminho entre o nó e sua folha descendente possui, como por invariante os caminhos traçados a partir de um nó até suas folhas descendentes devem possuir a mesma quantidade de nós pretos, esses serão sua altura.\n",
    "\n",
    "Para calcular-se a altura de um nó, existem duas formas possíveis:\n",
    "\n",
    "* Calcular a quantidade de nós pretos a partir do nó escolhido até suas folhas descendentes, incluindo o nó escolhido (caso seja preto) e excluindo os nós NIL.\n",
    "* Calcular a quantidade de nós pretos a partir do nó escolhido até suas folhas descendentes, excluindo o nó escolhido, no entanto, contando o nó NIL\n",
    "\n",
    "\n",
    "### **_Inserção_**\n",
    "\n",
    "A cada vez que uma operação é realizada na árvore, testa-se este conjunto de propriedades e são efetuadas rotações e ajuste de cores até que a árvore satisfaça todas estas regras.\n",
    "\n",
    "Uma rotação é uma operação realizada na árvore para garantir seu balanceamento. A rotação na árvore rubro-negra pode ser feita à direita e à esquerda, onde são alterados os ponteiros dos nós rotacionados.\n",
    "\n",
    "Ao inserir-se um elemento em uma árvore rubro-negra, esta é comparada com os elementos e alocada em sua posição conforme a regra 2. Ao inserir-se um elemento ele é sempre da cor vermelha (exceto se for o nó raiz). A seguir a árvore analisa o antecessor da folha. Se este for vermelho será necessário alterar as cores para garantir a regra 4.\n",
    "\n",
    "Uma inserção começa pela adição de um nó de forma semelhante a uma inserção em árvore binária, pintando-se o nó em vermelho. Diferentemente de uma árvore binária onde sempre adicionamos uma folha, na árvore rubro-negra as folhas não contém informação, então inserimos um nó vermelho na parte interna da árvore, com dois nós filhos pretos, no lugar de uma folha preta.\n",
    "\n",
    "O que acontece a seguir depende da cor dos nós vizinhos. O termo nó tio será usado para referenciar o irmão de um nó pái, como em uma árvore genealógica. Note que a:\n",
    "\n",
    "Propriedade 3 (todos as folhas são pretas) sempre se mantém;\n",
    "Propriedade 4 (ambos os filhos de um nó vermelho são pretos) é tratada somente pela adição de um nó vermelho, repintura de um nó preto como vermelho ou uma rotação;\n",
    "Propriedade 5 (todos os caminhos de um dado nó até suas folhas contém o mesmo número de nós pretos) é tratada apenas pela adição de um nó preto, repintura de um nó vermelho em preto ou uma rotação.\n",
    "Nota: O rótulo N será usado para denotar no novo nó sendo inserido. P denotará o pai de N', enquanto que G será o avô (grandparent) de N', e U (uncle) será o tio do nó N'. Note-se que entre em alguns casos, os papéis e os rótulos dos nós são trocadas, mas em cada caso, cada etiqueta continua a representar o mesmo nó que representava no início do caso. Qualquer cor exibida no diagrama ou é assumida no seu caso ou implícita por essas hipóteses\n",
    "\n",
    "### **_Casos_**:\n",
    "\n",
    "#### *Caso 1*:\n",
    "\n",
    "O novo nó N está na raiz da árvore. Neste caso, este nó é repintado de preto para satisfazer a Propriedade 2. Como esta ação adiciona um nó preto em todos os caminhos da árvore de uma só vez, a Propriedade 5 não é violada.\n",
    "\n",
    "#### *Caso 2*:\n",
    "\n",
    "O pai do novo nó P é preto. Neste caso a Propriedade 4 claramente não é invalidada. A Propriedade 5 tampouco é ameaçada pois o novo nó N tem como filhos dois nós-folha pretos, e sendo N vermelho, os caminhos passando por cada um dos seus filhos têm o mesmo número de nós pretos - da mesma forma que os caminhos que passavam pelo nó-folha preto que foi substituído por N. Por fim, neste caso, a árvore continua válida após a inserção, não sendo necessária mais alterações.\n",
    "\n",
    "#### *Caso 3*:\n",
    "\n",
    "Quando ambos o pai P e o tio U são vermelhos, então ambos podem ser repintados de preto e o avô G torna-se vermelho para manter a Propriedade 5. Agora, o novo nó vermelho N tem um pai na cor preta. Dado que todos os caminhos que passam pelo pai ou tio de N devem passar pelo seu avô, o número de nós pretos nestes caminhos não foi alterado. Porém, o avô G pode estar violando agora a Propriedade 2 ou 4. Para consertar isso, uma \"chamada recursiva\" do procedimento de insercao_caso1 é iniciada passando G como parâmetro (chamada recursiva aqui está em destaque pois a invocação ao caso 1 apenas PODE levar ao caso 3).\n",
    "\n",
    "Nota: como a invocação da recursão é sempre no final do algoritmo (tail-recursive call) o mesmo pode ser reescrito facilmente como um loop; sendo este o único loop do algoritmo, e todas as rotações acontecendo após o loop, isso prova que um número constante de rotações é realizado.\n",
    "\n",
    "#### *Caso 4*:\n",
    "\n",
    "O pai P é vermelho mas o tio U é preto; além disso, o novo nó N é o filho a direita de P, e P o filho a esquerda do seu pai G. Neste caso, uma rotação a esquerda que troca os papéis do novo nó N e de seu pai P deve ser realizada. Quando isso acontecer o antigo nó-pai P precisa ser tratado usando o Caso 5 (renomeando N e P) isso porque a Propriedade 4 ainda está sendo violada. Além disso, a rotação faz com que alguns caminhos (aqueles na sub-árvore denominada \"1\" na figura abaixo) passem pelo novo nó de forma diferente ao que acontecia antes, mas como os dois nós desta sub-árvore são vermelhos a Propriedade 5 não é violada (pela rotação).\n",
    "\n",
    "#### *Caso 5*:\n",
    "\n",
    "O pai P é vermelho mas o tio U é preto, o novo nó N é o filho esquerdo de seu pai P, e P é o filho esquerdo de seu pai, G. Neste caso, umarotação a direita no pai de P é realizada. O resultado é uma árvore onde o antigo pai P é agora pai tanto do novo nó N quanto do avô de N, G. É sabido que G é preto, já que seu antigo filho P não poderia ser vermelho. Então as cores de P e G são trocadas, e a árvore resultante satisfaz a propriedade 4 (ambos os filhos de cada nó vermelho são pretos). A propriedade 5 (Todos os caminhos de um determinado nó até suas folhas contém o mesmo número de nós pretos) também se mantém satisfeita, já que todos os caminhos até as folhas passam pelo nó G antes, e agora todos passam pelo P. Em cada caso, este é o único nó preto da sub-árvore.\n",
    "\n",
    "### **_Remoção_**\n",
    "\n",
    "A remoção nas árvores rubro-negras se inicia com uma etapa de busca e remoção como nas árvores binárias de busca convencionais. Então se alguma propriedade vermelho-preta for violada, a árvore deve ser rebalanceada. \n",
    "\n",
    "Caso a remoção efetiva seja de um nó vermelho, esta é realizada sem problemas, pois todas as propriedades da árvore se manterão intactas. Se o nó a ser removido for preto, a quantidade de nós pretos em pelo menos um dos caminhos da árvore foi alterado, o que implica que algumas operações de rotação e/ou alteração de cor sejam feitas para manter o balanceamento da árvore. \n",
    "\n",
    "Para ocorrer a remoção de um nó em arvore preta e vermelha é necessário que esse nó tenha no máximo um filho que não seja folha, a maior preocupação na remoção está em não quebrar as regras básicas que fazem uma arvore ser preta e vermelha e falando principalmente sobre a regra da altura preta. O primeiro caso verifica se o pai do nó não é nulo, se for vai para o segundo caso. No segundo caso, se o nó e seu pai forem pretos e seu irmão for vermelho o pai deve ser pintado de vermelho e o irmão de preto e então se o nó for filho esquerdo, faz a rotação à esquerda de seu pai e vai pro próximo caso, se for filho direito, rotaciona o pai à direita e vai pro próximo caso. Nesse caso, se o pai do nó, o irmão, o filho esquerdo e direito do irmão forem todos pretos, pinta o irmão de vermelho e volte para o primeiro caso com o pai do nó, se não forem vai pro próximo caso. No quarto caso, se o irmão e o filho esquerdo e direito do irmão forem pretos e o pai do nó for vermelho, deve pintar o irmão de vermelho e o pai do nó de preto, se não deve prosseguir para o próximo caso. No quinto caso, se o nó for filho esquerdo e o filho direito do irmão for preto deverá pintar o irmão de vermelho e o filho esquerdo do irmão de preto e aí sim rotacionar à direita o irmão, mas se o nó for filho direito deverá pintar o irmão de vermelho e o filho direito do irmão de preto e então rotacionar para esquerda o irmão, indo para o último caso. Ao chegar no último caso deverá pintar o pai do nó de preto, caso o nó seja filho esquerdo, pinta o filho direito do irmão do nó de preto e rotaciona o pai do nó para a esquerda, se o nó for filho direito, pinta o filho esquerdo do irmão de preto e rotaciona o pai para direita. Ao sair do encadeamento de casos poderá ser feita a remoção do nó naturalmente. O algoritmo de remoção é *O(log n)*.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cores possíveis de nó"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "BLACK = 'BLACK'\n",
    "RED = 'RED'\n",
    "NIL = 'NIL'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Classe Nó"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \n",
    "    \"\"\"   \n",
    "    Método \"construtor\" do nó\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self, value, color, parent, left=None, right=None):\n",
    "        \n",
    "        self.value = value\n",
    "        self.color = color\n",
    "        self.parent = parent\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    \"\"\"  \n",
    "    Método de representação do nó\n",
    "  \n",
    "    \"\"\"\n",
    "    \n",
    "    def __repr__(self):\n",
    "        \n",
    "        return '{color} {val} Node'.format(color=self.color, val=self.value)\n",
    "    \n",
    "    \"\"\"\n",
    "    Método de iteração (mostra como está funcionando a árvore).\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    def __iter__(self):\n",
    "        \n",
    "        print(str(self.value) + \" (\" + str(self.color)+\")\")\n",
    "        \n",
    "        if self.left.color != NIL:\n",
    "            print('left ({})'.format(str(self.value)));\n",
    "            yield from self.left.__iter__()\n",
    "\n",
    "        if self.right.color != NIL:\n",
    "            print('right ({})'.format(str(self.value)));\n",
    "            yield from self.right.__iter__()\n",
    "    \n",
    "    \"\"\"\n",
    "    Método de controle de condições.\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        \n",
    "        if self.color == NIL and self.color == other.color:\n",
    "            return True\n",
    "\n",
    "        if self.parent is None or other.parent is None:\n",
    "            parents_are_same = self.parent is None and other.parent is None\n",
    "        else:\n",
    "            parents_are_same = self.parent.value == other.parent.value and self.parent.color == other.parent.color\n",
    "            \n",
    "        return self.value == other.value and self.color == other.color and parents_are_same\n",
    "    \n",
    "    \n",
    "    \"\"\"   \n",
    "    Verificação de existência de filho;\n",
    "    Retorna um boleano indicando se o nó tem filho;\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    def has_children(self) -> bool:\n",
    "        \n",
    "        return bool(self.get_children_count())\n",
    "    \n",
    "    \"\"\"\n",
    "    Contegem de filhos não NIL que o nó tem\n",
    "    Retorna a quantidade de filhos não NIL que o nó possuí.\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    def get_children_count(self) -> int:\n",
    "        \n",
    "        if self.color == NIL:\n",
    "            return 0\n",
    "        return sum([int(self.left.color != NIL), int(self.right.color != NIL)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classe da árvore Vermelho-Preto"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RedBlackTree:\n",
    "    \n",
    "    \"\"\"\n",
    "    Todo nó tem filhos nulos inicialmente, portanto, criar um objeto para isso facilitará\n",
    "    a manipulação na arvore.\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    NIL_LEAF = Node(value=None, color=NIL, parent=None)\n",
    "\n",
    "    def __init__(self):\n",
    "        \n",
    "        self.count = 0\n",
    "        self.root = None\n",
    "        \n",
    "        \"\"\"\n",
    "        Usado para condição e usa o relacionamento dos irmãos com seu pai como um guia para a rotação.\n",
    "        \n",
    "        \"\"\"\n",
    "        \n",
    "        self.ROTATIONS = {\n",
    "            'L': self._right_rotation,\n",
    "            'R': self._left_rotation\n",
    "        }\n",
    "\n",
    "    def __iter__(self):\n",
    "        \n",
    "        if not self.root:\n",
    "            return list()\n",
    "        yield from self.root.__iter__()\n",
    "\n",
    "    def __repr__(self):\n",
    "       \n",
    "        return self.root\n",
    "    \n",
    "    \"\"\"\n",
    "    Adiciona nó.\n",
    "    \"\"\"\n",
    "\n",
    "    def add(self, value):\n",
    "        \n",
    "        if not self.root:\n",
    "            self.root = Node(value, color=BLACK, parent=None, left=self.NIL_LEAF, right=self.NIL_LEAF)\n",
    "            self.count += 1\n",
    "            return\n",
    "        \n",
    "        parent, node_dir = self._find_parent(value)\n",
    "        \n",
    "        if node_dir is None:\n",
    "            return  # valor está na árvore\n",
    "        \n",
    "        new_node = Node(value=value, color=RED, parent=parent, left=self.NIL_LEAF, right=self.NIL_LEAF)\n",
    "        \n",
    "        if node_dir == 'L':\n",
    "            parent.left = new_node\n",
    "        else:\n",
    "            parent.right = new_node\n",
    "\n",
    "        self._try_rebalance(new_node)\n",
    "        self.count += 1\n",
    "\n",
    "    \"\"\"\n",
    "    Tenta pegar o nó com 0 ou 1 filho.\n",
    "    Ou o nó que nos é dado tem 0 ou 1 filhos ou obtemos o seu sucessor.\n",
    "    \"\"\"\n",
    "        \n",
    "    def remove(self, value):\n",
    "        \n",
    "        node_to_remove = self.find_node(value)\n",
    "        if node_to_remove is None:  # node is not in the tree\n",
    "            return\n",
    "        if node_to_remove.get_children_count() == 2:\n",
    "            # find the in-order successor and replace its value.\n",
    "            # then, remove the successor\n",
    "            successor = self._find_in_order_successor(node_to_remove)\n",
    "            node_to_remove.value = successor.value  # switch the value\n",
    "            node_to_remove = successor\n",
    "\n",
    "        # has 0 or 1 children!\n",
    "        self._remove(node_to_remove)\n",
    "        self.count -= 1\n",
    "\n",
    "    \"\"\" \n",
    "    Retorna um bool se indicando se o valor está contido ou não na árvore \n",
    "    \"\"\"\n",
    "\n",
    "    def contains(self, value) -> bool:\n",
    "        return bool(self.find_node(value))\n",
    "\n",
    "    \"\"\"\n",
    "    Dado um valor, retorna o valor mais próximo, que é igual ou maior que ele,\n",
    "    retornando None quando não houver.\n",
    "    \"\"\"\n",
    "    \n",
    "    def ceil(self, value) -> int or None:\n",
    "        \n",
    "        if self.root is None: return None\n",
    "        last_found_val = None if self.root.value < value else self.root.value\n",
    "\n",
    "        def find_ceil(node):\n",
    "            nonlocal last_found_val\n",
    "            if node == self.NIL_LEAF:\n",
    "                return None\n",
    "            if node.value == value:\n",
    "                last_found_val = node.value\n",
    "                return node.value\n",
    "            elif node.value < value:\n",
    "                # Vá para a direita\n",
    "                return find_ceil(node.right)\n",
    "            else:\n",
    "                # Este nó é o maior, salve o seu valor e vá para a esquerda\n",
    "                last_found_val = node.value\n",
    "\n",
    "                return find_ceil(node.left)\n",
    "        find_ceil(self.root)\n",
    "        return last_found_val\n",
    "\n",
    "    \"\"\"\n",
    "    Dado um valor, retorna o valor mais próximo, que é igual ou menor que ele,\n",
    "    retornando None quando não houver.\n",
    "    \"\"\"\n",
    "    \n",
    "    def floor(self, value) -> int or None:\n",
    "        \n",
    "        if self.root is None: return None\n",
    "        last_found_val = None if self.root.value > value else self.root.value\n",
    "\n",
    "        def find_floor(node):\n",
    "            nonlocal last_found_val\n",
    "            if node == self.NIL_LEAF:\n",
    "                return None\n",
    "            if node.value == value:\n",
    "                last_found_val = node.value\n",
    "                return node.value\n",
    "            elif node.value < value:\n",
    "                # Este valor é o menor, salve-o e vá para a direita, tentando encontrar um menor\n",
    "                last_found_val = node.value\n",
    "\n",
    "                return find_floor(node.right)\n",
    "            else:\n",
    "                return find_floor(node.left)\n",
    "\n",
    "        find_floor(self.root)\n",
    "        return last_found_val\n",
    "\n",
    "    \"\"\"\n",
    "    \n",
    "    Recebe um nó com 0 ou 1 filho (tipicamente algum sucessor)\n",
    "    e o remove de acordo com sua cor/filho.\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    def _remove(self, node):\n",
    "        \n",
    "        \"\"\"\n",
    "        :param node: nó com 0 ou 1 filho\n",
    "        \n",
    "        \"\"\"\n",
    "        \n",
    "        left_child = node.left\n",
    "        right_child = node.right\n",
    "        not_nil_child = left_child if left_child != self.NIL_LEAF else right_child\n",
    "        \n",
    "        if node == self.root:\n",
    "            if not_nil_child != self.NIL_LEAF:\n",
    "                # Se estivermos removendo a raiz e ela tiver um filho válido, ele se tornará a raiz\n",
    "                self.root = not_nil_child\n",
    "                self.root.parent = None\n",
    "                self.root.color = BLACK\n",
    "            else:\n",
    "                self.root = None\n",
    "                \n",
    "        elif node.color == RED:\n",
    "            \n",
    "            if not node.has_children():           \n",
    "                # RED node with no children, the simplest remove\n",
    "                self._remove_leaf(node)\n",
    "            else:\n",
    "                \"\"\"\n",
    "                Desde que o nó seja vermelho, ele não poderá ter um filho.\n",
    "                Para isso, deve-se trocar a cor para preto.\n",
    "                \"\"\"\n",
    "                raise Exception('Unexpected behavior')\n",
    "                \n",
    "        else:  # nó é preto\n",
    "            if right_child.has_children() or left_child.has_children():  #validação\n",
    "                raise Exception('The RED child of a black node with 0 or 1 children'\n",
    "                                ' cannot have children, otherwise the black height of the tree becomes invalid! ')\n",
    "            if not_nil_child.color == RED:\n",
    "                \"\"\"\n",
    "                Troque os valores com filho vermelho e remova-o (basicamente \"deslink isso\")\n",
    "                Desde que o nó possui um filho somente, pode-se ter certeza que há nenhum nó abaixo do\n",
    "                nó filho vermelho.\n",
    "                \"\"\"\n",
    "                node.value = not_nil_child.value\n",
    "                node.left = not_nil_child.left\n",
    "                node.right = not_nil_child.right\n",
    "            else:  # Filho preto\n",
    "                # 6 cases :\n",
    "                self._remove_black_node(node)\n",
    "\n",
    "    def _remove_leaf(self, leaf):\n",
    "        \"\"\" \n",
    "        Simplesmente remove uma folha fazendo seu pai virar um NIL\n",
    "        \"\"\"\n",
    "        if leaf.value >= leaf.parent.value:\n",
    "            leaf.parent.right = self.NIL_LEAF\n",
    "        else:\n",
    "            leaf.parent.left = self.NIL_LEAF\n",
    "\n",
    "    def _remove_black_node(self, node):\n",
    "        \"\"\"\n",
    "        Itere sobre cada caso recursivamente até o caso final ser encontrado.\n",
    "        O que nos resta é um nó de folha que está pronto para ser excluído sem conseqüências\n",
    "        \"\"\"\n",
    "        self.__case_1(node)\n",
    "        self._remove_leaf(node)\n",
    "\n",
    "    def __case_1(self, node):\n",
    "        \"\"\"\n",
    "        Caso 1:\n",
    "        \n",
    "        O novo nó N está na raiz da árvore. Neste caso, este nó é repintado de preto para satisfazer a Propriedade 2.\n",
    "        \n",
    "        Propriedade 2: A raiz é preta.\n",
    "        \n",
    "        Como esta ação adiciona um nó preto em todos os caminhos da árvore de uma só vez, a Propriedade 5 não é violada.\n",
    "        \n",
    "        Propriedade 5: Todo caminho de um dado nó para qualquer de seus nós folhas descendentes contem o mesmo número de nós pretos.\n",
    "        \n",
    "            __|10B|__                  __10B__\n",
    "           /         \\      ==>       /       \\\n",
    "          9B         20B            9B        20B\n",
    "          \n",
    "        \"\"\"\n",
    "        if self.root == node:\n",
    "            node.color = BLACK\n",
    "            return\n",
    "        \n",
    "        self.__case_2(node)\n",
    "\n",
    "    def __case_2(self, node):\n",
    "        \"\"\"\n",
    "        Caso 2 é aplicado quando:\n",
    "        \n",
    "            O pai do novo nó é preto;\n",
    "            O filho é vermelho;\n",
    "            Os filhos do filho são pretos ou nil;\n",
    "        \n",
    "        A Propriedade 5 tampouco é ameaçada pois o novo nó N tem como filhos dois nós-folha pretos, \n",
    "        e sendo N vermelho, os caminhos passando por cada um dos seus filhos têm o mesmo número de nós \n",
    "        pretos - da mesma forma que os caminhos que passavam pelo nó-folha preto que foi substituído por N. \n",
    "        Por fim, neste caso, a árvore continua válida após a inserção, não sendo necessária mais alterações.\n",
    "            \n",
    "        Pega o filho e o rotaciona.\n",
    "        \n",
    "                         40B                                              60B\n",
    "                        /   \\                                            /   \\\n",
    "                    |20B|   60R                                        40R   80B\n",
    "                           /   \\                                      /   \\\n",
    "                         50B    80B                                |20B|  50B\n",
    "\n",
    "        \"\"\"\n",
    "        parent = node.parent\n",
    "        sibling, direction = self._get_sibling(node)\n",
    "        \n",
    "        if sibling.color == RED and parent.color == BLACK and sibling.left.color != RED and sibling.right.color != RED:\n",
    "            self.ROTATIONS[direction](node=None, parent=sibling, grandfather=parent)\n",
    "            parent.color = RED\n",
    "            sibling.color = BLACK\n",
    "            return self.__case_1(node)\n",
    "        self.__case_3(node)\n",
    "\n",
    "    def __case_3(self, node):\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "        Caso 3:\n",
    "            o pai é preto\n",
    "            o filho é preto\n",
    "            os filhos dos filhos são pretos\n",
    "\n",
    "        Então, nós tornamos os filhos vermelhos e passamos nós pretos para cima:\n",
    "\n",
    "                            Pai preto\n",
    "               ___50B___    Filho é preto                          ___50B___\n",
    "              /         \\   Filhos dos filhos são pretos          /         \\\n",
    "           30B          80B        CASE 3                       30B        |80B|  Continua com os outros casos\n",
    "          /   \\        /   \\        ==>                        /  \\        /   \\\n",
    "        20B   35R    70B   |90B|<---REMOVE                   20B  35R     70R   X\n",
    "              /  \\                                               /   \\\n",
    "            34B   37B                                          34B   37B\n",
    "            \n",
    "        \"\"\"\n",
    "        \n",
    "        parent = node.parent\n",
    "        sibling, _ = self._get_sibling(node)\n",
    "        \n",
    "        if (sibling.color == BLACK and parent.color == BLACK\n",
    "           and sibling.left.color != RED and sibling.right.color != RED):\n",
    "            sibling.color = RED\n",
    "            return self.__case_1(parent)  # start again\n",
    "\n",
    "        self.__case_4(node)\n",
    "\n",
    "    def __case_4(self, node):\n",
    "        \"\"\"\n",
    "        Caso 4:\n",
    "        \n",
    "        Se o pai é vermelho e o filho é preto sem nenhum filho vermelho\n",
    "\n",
    "        PD-Preto Duplo\n",
    "        \n",
    "                __10R__                   __10B__        \n",
    "               /       \\                 /       \\       \n",
    "             DB        15B      ===>    X        15R     \n",
    "                      /   \\                     /   \\\n",
    "                    12B   17B                 12B   17B\n",
    "        \"\"\"\n",
    "        parent = node.parent\n",
    "        if parent.color == RED:\n",
    "            sibling, direction = self._get_sibling(node)\n",
    "            if sibling.color == BLACK and sibling.left.color != RED and sibling.right.color != RED:\n",
    "                parent.color, sibling.color = sibling.color, parent.color  # switch colors\n",
    "                return  # Terminating\n",
    "        self.__case_5(node)\n",
    "\n",
    "    def __case_5(self, node):\n",
    "        \"\"\"\n",
    "        Caso 5:\n",
    "        \n",
    "        É uma rotação que muda as circunstâncias para que possamos fazer um caso 6\n",
    "        Se o nó mais próximo estiver vermelho e o externo BLACK ou NIL, fazemos uma rotação\n",
    "        esquerda / direita, dependendo da orientação\n",
    "        Isso mostrará quando a direção do nó mais próximo for direita.\n",
    "        \n",
    "              ___50B___                                                    __50B__\n",
    "             /         \\                                                  /       \\\n",
    "           30B        |80B|  <-- Preto duplo                           35B      |80B|        \n",
    "          /  \\        /   \\      Mais próximo nó RED- 35R             /   \\      /           \n",
    "        20B  35R     70R   X                                        30R    37B  70R           \n",
    "            /   \\                                                  /   \\                      \n",
    "          34B  37B                                               20B   34B\n",
    "        \"\"\"\n",
    "        sibling, direction = self._get_sibling(node)\n",
    "        closer_node = sibling.right if direction == 'L' else sibling.left\n",
    "        outer_node = sibling.left if direction == 'L' else sibling.right\n",
    "        if closer_node.color == RED and outer_node.color != RED and sibling.color == BLACK:\n",
    "            if direction == 'L':\n",
    "                self._left_rotation(node=None, parent=closer_node, grandfather=sibling)\n",
    "            else:\n",
    "                self._right_rotation(node=None, parent=closer_node, grandfather=sibling)\n",
    "            closer_node.color = BLACK\n",
    "            sibling.color = RED\n",
    "\n",
    "        self.__case_6(node)\n",
    "\n",
    "    def __case_6(self, node):\n",
    "        \"\"\"\n",
    "        Caso 6 requer\n",
    "             FILHO PARA SER PRETO\n",
    "             NÓS EXTERIOR  ser VERMELHO\n",
    "         Então, faz uma rotação direita / esquerda no irmão\n",
    "         Isso mostrará quando a direção do filho está à ESQUERDA\n",
    "\n",
    "                            Double Black\n",
    "                    __50B__       |                               __35B__\n",
    "                   /       \\      |                              /       \\\n",
    "      SIBLING--> 35B      |80B| <-                             30R       50R\n",
    "                /   \\      /                                  /   \\     /   \\\n",
    "             30R    37B  70R                                20B   34B 37B    80B\n",
    "            /   \\                                                            /\n",
    "         20B   34B                                                         70R\n",
    "        \"\"\"\n",
    "        sibling, direction = self._get_sibling(node)\n",
    "        outer_node = sibling.left if direction == 'L' else sibling.right\n",
    "\n",
    "        def __case_6_rotation(direction):\n",
    "            parent_color = sibling.parent.color\n",
    "            self.ROTATIONS[direction](node=None, parent=sibling, grandfather=sibling.parent)\n",
    "            # new parent is sibling\n",
    "            sibling.color = parent_color\n",
    "            sibling.right.color = BLACK\n",
    "            sibling.left.color = BLACK\n",
    "\n",
    "        if sibling.color == BLACK and outer_node.color == RED:\n",
    "            return __case_6_rotation(direction)  # terminating\n",
    "\n",
    "        raise Exception('We should have ended here, something is wrong')\n",
    "\n",
    "    def _try_rebalance(self, node):\n",
    "        \"\"\"\n",
    "        Dado um nó filho vermelho, determine se há necessidade de rebalancear a arvore (se o pai é vermelho)\n",
    "        Caso seja necessário, rebalanceie\n",
    "        \"\"\"\n",
    "        parent = node.parent\n",
    "        value = node.value\n",
    "        if (parent is None  # what the fuck? (should not happen)\n",
    "           or parent.parent is None  # parent is the root\n",
    "           or (node.color != RED or parent.color != RED)):  # no need to rebalance\n",
    "            return\n",
    "        grandfather = parent.parent\n",
    "        node_dir = 'L' if parent.value > value else 'R'\n",
    "        parent_dir = 'L' if grandfather.value > parent.value else 'R'\n",
    "        uncle = grandfather.right if parent_dir == 'L' else grandfather.left\n",
    "        general_direction = node_dir + parent_dir\n",
    "\n",
    "        if uncle == self.NIL_LEAF or uncle.color == BLACK:\n",
    "            # rotate\n",
    "            if general_direction == 'LL':\n",
    "                self._right_rotation(node, parent, grandfather, to_recolor=True)\n",
    "            elif general_direction == 'RR':\n",
    "                self._left_rotation(node, parent, grandfather, to_recolor=True)\n",
    "            elif general_direction == 'LR':\n",
    "                self._right_rotation(node=None, parent=node, grandfather=parent)\n",
    "                # due to the prev rotation, our node is now the parent\n",
    "                self._left_rotation(node=parent, parent=node, grandfather=grandfather, to_recolor=True)\n",
    "            elif general_direction == 'RL':\n",
    "                self._left_rotation(node=None, parent=node, grandfather=parent)\n",
    "                # due to the prev rotation, our node is now the parent\n",
    "                self._right_rotation(node=parent, parent=node, grandfather=grandfather, to_recolor=True)\n",
    "            else:\n",
    "                raise Exception(\"{} is not a valid direction!\".format(general_direction))\n",
    "        else:  # uncle is RED\n",
    "            self._recolor(grandfather)\n",
    "\n",
    "    def __update_parent(self, node, parent_old_child, new_parent):\n",
    "        \"\"\"\n",
    "        O nó novo troca de lugar com o filho velho\n",
    "        Aponta o pai para o nó.\n",
    "        Se o novo pai for None, isso significa que nosso nó se tornou a raiz da arvore.\n",
    "        \n",
    "        \"\"\"\n",
    "        node.parent = new_parent\n",
    "        if new_parent:\n",
    "            # Determine the old child's position in order to put node there\n",
    "            if new_parent.value > parent_old_child.value:\n",
    "                new_parent.left = node\n",
    "            else:\n",
    "                new_parent.right = node\n",
    "        else:\n",
    "            self.root = node\n",
    "\n",
    "    def _right_rotation(self, node, parent, grandfather, to_recolor=False):\n",
    "        \n",
    "        grand_grandfather = grandfather.parent\n",
    "        self.__update_parent(node=parent, parent_old_child=grandfather, new_parent=grand_grandfather)\n",
    "\n",
    "        old_right = parent.right\n",
    "        parent.right = grandfather\n",
    "        grandfather.parent = parent\n",
    "\n",
    "        grandfather.left = old_right  # save the old right values\n",
    "        old_right.parent = grandfather\n",
    "\n",
    "        if to_recolor:\n",
    "            parent.color = BLACK\n",
    "            node.color = RED\n",
    "            grandfather.color = RED\n",
    "\n",
    "    def _left_rotation(self, node, parent, grandfather, to_recolor=False):\n",
    "        \n",
    "        grand_grandfather = grandfather.parent\n",
    "        self.__update_parent(node=parent, parent_old_child=grandfather, new_parent=grand_grandfather)\n",
    "\n",
    "        old_left = parent.left\n",
    "        parent.left = grandfather\n",
    "        grandfather.parent = parent\n",
    "\n",
    "        grandfather.right = old_left  # save the old left values\n",
    "        old_left.parent = grandfather\n",
    "\n",
    "        if to_recolor:\n",
    "            parent.color = BLACK\n",
    "            node.color = RED\n",
    "            grandfather.color = RED\n",
    "\n",
    "    def _recolor(self, grandfather):\n",
    "        \n",
    "        grandfather.right.color = BLACK\n",
    "        grandfather.left.color = BLACK\n",
    "        if grandfather != self.root:\n",
    "            grandfather.color = RED\n",
    "        self._try_rebalance(grandfather)\n",
    "\n",
    "    def _find_parent(self, value):\n",
    "        \n",
    "        \"\"\" Encontra o lugar para os valores na árvore\"\"\"\n",
    "        \n",
    "        def inner_find(parent):\n",
    "            \"\"\"\n",
    "            Retorna o nó pai apropriado para o novo nó assim como a sua direção\n",
    "            \n",
    "            \"\"\"\n",
    "            if value == parent.value:\n",
    "                return None, None\n",
    "            elif parent.value < value:\n",
    "                if parent.right.color == NIL:  # no more to go\n",
    "                    return parent, 'R'\n",
    "                return inner_find(parent.right)\n",
    "            elif value < parent.value:\n",
    "                if parent.left.color == NIL:  # no more to go\n",
    "                    return parent, 'L'\n",
    "                return inner_find(parent.left)\n",
    "\n",
    "        return inner_find(self.root)\n",
    "\n",
    "    def find_node(self, value):\n",
    "        \n",
    "        def inner_find(root):\n",
    "            if root is None or root == self.NIL_LEAF:\n",
    "                return None\n",
    "            if value > root.value:\n",
    "                return inner_find(root.right)\n",
    "            elif value < root.value:\n",
    "                return inner_find(root.left)\n",
    "            else:\n",
    "                return root\n",
    "\n",
    "        found_node = inner_find(self.root)\n",
    "        return found_node\n",
    "\n",
    "    def _find_in_order_successor(self, node):\n",
    "        \n",
    "        right_node = node.right\n",
    "        left_node = right_node.left\n",
    "        if left_node == self.NIL_LEAF:\n",
    "            return right_node\n",
    "        while left_node.left != self.NIL_LEAF:\n",
    "            left_node = left_node.left\n",
    "        return left_node\n",
    "\n",
    "    def _get_sibling(self, node):\n",
    "        \"\"\"\n",
    "        Retorna o filho do nó, assim como a sua direção\n",
    "        \n",
    "            20 (A)\n",
    "           /     \\\n",
    "        15(B)    25(C)\n",
    "        _get_sibling(25(C)) => 15(B), 'R'\n",
    "        \"\"\"\n",
    "        parent = node.parent\n",
    "        if node.value >= parent.value:\n",
    "            sibling = parent.left\n",
    "            direction = 'L'\n",
    "        else:\n",
    "            sibling = parent.right\n",
    "            direction = 'R'\n",
    "        return sibling, direction\n",
    "    \n",
    "    def _build_tree_string(self, root=None, curr_index=0, index=False, delimiter='-'):\n",
    "\n",
    "        if curr_index == 0:\n",
    "            root = self.root\n",
    "            \n",
    "        if root is None:\n",
    "            return [], 0, 0, 0\n",
    "\n",
    "        line1 = []\n",
    "        line2 = []\n",
    "        \n",
    "        if index:\n",
    "            node_repr = '{}{}{}'.format(curr_index, delimiter, root.value)\n",
    "        else:\n",
    "            node_repr = str(root.value)\n",
    "\n",
    "        if node_repr == 'None':\n",
    "            node_repr = 'NIL'\n",
    "        \n",
    "        new_root_width = gap_size = len(node_repr)\n",
    "        \n",
    "        if root.color == 'RED':\n",
    "            node_repr = ('\\033[30m'+ '\\033[41m'+ node_repr +'\\033[0;0m')\n",
    "\n",
    "        \n",
    "        # Get the left and right sub-boxes, their widths, and root repr positions\n",
    "        l_box, l_box_width, l_root_start, l_root_end = \\\n",
    "            self._build_tree_string(root.left, 2 * curr_index + 1, index, delimiter)\n",
    "        r_box, r_box_width, r_root_start, r_root_end = \\\n",
    "            self._build_tree_string(root.right, 2 * curr_index + 2, index, delimiter)\n",
    "\n",
    "        # Draw the branch connecting the current root node to the left sub-box\n",
    "        # Pad the line with whitespaces where necessary\n",
    "        if l_box_width > 0:\n",
    "            l_root = (l_root_start + l_root_end) // 2 + 1\n",
    "            line1.append(' ' * (l_root + 1))\n",
    "            line1.append('_' * (l_box_width - l_root))\n",
    "            line2.append(' ' * l_root + '/')\n",
    "            line2.append(' ' * (l_box_width - l_root))\n",
    "            new_root_start = l_box_width + 1\n",
    "            gap_size += 1\n",
    "        else:\n",
    "            new_root_start = 0\n",
    "\n",
    "        # Draw the representation of the current root node\n",
    "        line1.append(str(node_repr))\n",
    "        line2.append(' ' * new_root_width)\n",
    "\n",
    "        # Draw the branch connecting the current root node to the right sub-box\n",
    "        # Pad the line with whitespaces where necessary\n",
    "        if r_box_width > 0:\n",
    "            r_root = (r_root_start + r_root_end) // 2\n",
    "            line1.append('_' * r_root)\n",
    "            line1.append(' ' * (r_box_width - r_root + 1))\n",
    "            line2.append(' ' * r_root + '\\\\')\n",
    "            line2.append(' ' * (r_box_width - r_root))\n",
    "            gap_size += 1\n",
    "            \n",
    "        new_root_end = new_root_start + new_root_width - 1\n",
    "\n",
    "        # Combine the left and right sub-boxes with the branches drawn above\n",
    "        gap = ' ' * gap_size\n",
    "        new_box = [''.join(line1), ''.join(line2)]\n",
    "        for i in range(max(len(l_box), len(r_box))):\n",
    "            l_line = l_box[i] if i < len(l_box) else ' ' * l_box_width\n",
    "            r_line = r_box[i] if i < len(r_box) else ' ' * r_box_width\n",
    "            new_box.append(l_line + gap + r_line)\n",
    "       \n",
    "        len_new_box = len(new_box[0])\n",
    "        if root.color == 'RED':\n",
    "            len_new_box = len(new_box[0]) - 16\n",
    "\n",
    "        # Return the new box, its width and its root repr positions\n",
    "        return new_box, len_new_box, new_root_start, new_root_end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Definição da árvore"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "            __________3______________________                                                             \n",
      "           /                                 \\                                                            \n",
      "      ____1____                     __________\u001b[30m\u001b[41m7\u001b[0;0m_________________                                          \n",
      "     /         \\                   /                            \\                                         \n",
      "   _0_         _2_            ____5____                     _____11___________                            \n",
      "  /   \\       /   \\          /         \\                   /                  \\                           \n",
      "NIL   NIL   NIL   NIL      _4_         _6_            ____10_             _____\u001b[30m\u001b[41m13\u001b[0;0m___________              \n",
      "                          /   \\       /   \\          /       \\           /                  \\             \n",
      "                        NIL   NIL   NIL   NIL      _\u001b[30m\u001b[41m8\u001b[0;0m_       NIL       _12_             _____15____       \n",
      "                                                  /   \\               /    \\           /           \\      \n",
      "                                                NIL   NIL           NIL    NIL       _\u001b[30m\u001b[41m14\u001b[0;0m_          _\u001b[30m\u001b[41m16\u001b[0;0m_   \n",
      "                                                                                    /    \\        /    \\  \n",
      "                                                                                  NIL    NIL    NIL    NIL\n",
      "                                                                                                          \n"
     ]
    }
   ],
   "source": [
    "arvore = RedBlackTree()\n",
    "\n",
    "for i in range(17):\n",
    "    arvore.add(i)\n",
    "    \n",
    "arvore.remove(9)\n",
    "\n",
    "for linha in arvore._build_tree_string()[0]:\n",
    "    \n",
    "    print(linha)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}