# Corda (estrutura de dados)

Em programação de computadores, uma corda é uma estrutura de dados composta de pequenas sequências de caracteres que é usada de forma eficiente para armazenar e manipular uma cadeia muito longa. Por exemplo, um programa de edição de texto pode utilizar uma corda para representar o texto que está sendo editado, para que operações como inserção, exclusão, acesso aleatório possam ser realizadas de forma eficiente.

## Descrição

Uma corda é uma árvore binária onde cada nó folha contém uma cadeia de caracteres curta. Cada nó tem um peso de valor igual ao comprimento de sua cadeia somado com a adição de todos os pesos dos nós folha na subárvore à esquerda. O peso de um nó é o comprimento total de sua sequência de caracteres na sua subárvore à esquerda de um nó não folha, ou o comprimento de cadeia de si mesmo para um nó folha. Assim sendo, um nó com dois filhos, divide-se a sequência inteira em duas partes: a subárvore esquerda armazena a primeira parte da sequência de caracteres. A subárvore à direita armazena a segunda parte da sequência de caracteres. O peso deste nó é dado pela soma de do peso dos sub-nós à esquerda e o tamanho da sequência de caracteres.
A árvore binária pode ser vista como vários níveis de nós: o nível inferior contém todos os nós que contêm uma sequência de caracteres; níveis mais elevados têm cada vez menos de nós; o nível superior é composto de uma única "raiz", assim como uma árvore binária. A corda é construída colocando os nós com cadeias curtas no nível inferior, em seguida, anexa-se uma metade de nós aleatória para nós pais no próximo nível.

## Operações

Nas seguintes definições, N é o comprimento da corda.

### Índice

    Definição: Índice(i): retorna o caracter na posição i
    Tempo de complexidade: $O(\log N)$
Para obter o i-ésimo caractere, começamos uma busca recursiva a partir do nó raiz:
Por exemplo, para encontrar o caractere em i=10 na Figura 2.1, inicia-se no nó raiz (A), achar que 22 é maior que 10 e existe um nó filho à esquerda, então vá para este nó (B). 9 é menor do que 10, então, subtrai-se 9 de 10 (deixando-o i=1) e vá para a o filho à direita (D). Em seguida, porque 6 é maior que 1 e há um filho à esquerda, então vá para o nó filho à esquerda (G). 2 é maior que 1 e não há um nó filho à direita, então vá para a esquerda novamente (J). Finalmente, 2 é maior que 1, mas não há nó filho à esquerda, assim, o carácter de cada índice 1 da curta sequência de caracteres "na", é a resposta.

### Concatenação

    Definição: Concatenar(S1, S2): concatenar duas cordas, S$_1$ e S$_2$, em uma única corda.
    Tempo de complexidade: $O(1)$ (ou $O(\log N)$ tempo para calcular a raiz de peso)
Uma concatenação pode ser realizada simplesmente através da criação de um novo nó raiz com left = S1 e right = S2, que é a constante de tempo. O peso do nó pai é definida como o comprimento do filho à esquerda de S$_1$, o que levaria a $O(\log N)$ tempo, se a árvore é balanceada.
Como a maioria corda operações requerem árvores balanceadas, a árvore precisa ser re-equilibrada após a concatenação.

### Divisão

    Definição: Divisão(i, S): dividir a corda S em duas novas sequências de S$_1$ e S$_2$, onde S$_1$ = C$_1$, …, C$_i$ e S$_2$ = C$_{i+1}$, …, C$_m$.
    Tempo de complexidade: $O(\log N)$
Há dois casos que devem ser tratados:
* Se o ponto de divisão estiver no final de uma sequência de caracteres (por exemplo, após o último caractere de um nó folha)
* Se o ponto de divisão está no meio de uma sequência de caracteres.
O segundo caso reduz ao primeiro dividindo a corda no ponto de divisão para criar dois novos nós de folha e, em seguida, criar um novo nó que é o pai das duas cadeias componentes.
Por exemplo, para dividir a cadeia da corda ilustrada na Figura 2.3 em duas cordas iguais de comprimento 11, é necessário consultar o caracter 12 para localizar o nó K no nível inferior. Remove-se a ligação entre K e G e o algoritmo prossegue para o pai de G e subtrai o peso de K a partir do peso de D. Então, o algoritmo se move para cima na árvore e remover qualquer link direto para sub-árvores, cobrindo de caracteres passado posição 11, subtraindo-se o peso de K a partir de seus nós pais (somente o nó D e Um, neste caso). Finalmente, constrói-se os nós K e H ao concatená-los e a cria-se um novo pai P com peso igual ao comprimento da esquerda nó K.
Como a maioria corda operações requerem árvores balanceadas, a árvore precisa ser re-equilibradas após a divisão.

### Inserção

    Definição: Inserir(i, S'): inserir a cadeia de caracteres "S", começando na posição i da string s, para formar uma nova sequência de caracteres C$_1$, …, C$_i$, S', C$_{i+1}$, …, C$_m$.
    Tempo de complexidade: $O(\log N)$.
Esta operação pode ser feita por uma operação de Divisão e duas operações de Concatenar. O custo é a soma dos três.

### Remover

    Definição: Remover(i, j): eliminar a subsequência de caracteres C$_i$, …, C$_{i+j−1}$, a partir de s para formar uma nova sequência de caracteres C$_1$, …, C$_{i−1}$, C$_{i+j}$, …, C$_m$.
    Tempo de complexidade: $O(\log N)$.
Esta operação pode ser feita por duas operações de Divisão e uma operação de Concatenar operação. Primeiro, divide-se a corda em três, pelo i-ésimo e i+j-ésimo caractere respectivamente, onde se extrai a sequência de caracteres para excluir um nó separado. Então, concatene os outros dois nós.

### Relatório

    Definição: Relatório(i, j): saída a sequência de caracteres C$_i$, …, C$_{i+j−1}$.
    Tempo de complexidade: $O(j+\log N)$
Para reportar a sequência de caracteres C$_i$, …, C$_{i+j−1}$, localize o nó u que contém C$_i$ e peso(u) &gt;= je, em seguida, atravesse T iniciando no nó u. Saída C$_i$, …, C$_{i+j−1}$.

## Comparação com vetores monolítico

Desempenho$^[$ :
| Operação | Corda | Cadeia |
| Índice | O(log n) | O(1) |
| Divisão | O(log n) | O(1) |
| Concatenar (destrutiva) | O(log n) sem rebalancear / O(n) pior caso | O(n) |
| Concatenar (não destrutiva) | O(n) | O(n) |
| Iterar sobre cada caractere | O(n) | O(n) |
| Inserir | O(log n) sem rebalancear / O(n) pior caso | O(n) |
| Anexar | O(log n) sem rebalancear / O(n) pior caso | O(1) |
| Remover | O(log n) | O(n) |
| Relatório | O(j + log n) | O(1) |
| Construção | O(n) | O(n) |
Vantagens:
* Cordas permitem fazer operações de inserção e exclusão de texto mais rápido que vetores monolíticos de sequência de caracteres, nos operações tem complexidade de tempo O(n).
* Cordas não requerem O(n) memória extra para realizar operações (vetores precisam de memória extra para as operações de cópia).
* Cordas não exigem grande de espaço contíguo de memória.
* Se apenas versões não-destrutivas de operações são usadas, a corda é um estrutura de dados persistente. Para o programa de edição de texto, por exemplo, resulta em fácil suporte para desfazer múltiplos níveis.
Desvantagens:
* Cordas usam mais espaço quando não estão sendo operadas, principalmente para armazenar os nós do pai. Existe uma troca entre o quanto de memória total sobrecarrega e como redações de longas cadeias de dados estão sendo processados como sequências de caracteres. As sequências de caracteres em números de exemplo acima são inacreditavelmente curtas em arquiteturas modernas. A sobrecarga é sempre de O(n), mas essa constante pode ser feito arbitrariamente pequena.
* Aumento no tempo para gerenciar o armazenamento extra.
* O aumento de complexidade do código-fonte; maior risco de bugs
A tabela compara os algoritmos para vetores monolíticos e implementações para cordas, e não a sua velocidade bruta. Sequência de caracteres, baseadas em vetores, tem menor sobrecarga, de modo que, operações de concatenação e divisão são mais rápidas em pequenos conjuntos de dados. No entanto, quando esta implementação é usada para cadeias mais longas, o tempo, a complexidade e o uso de memória para inserir e eliminar caracteres tornar-se inaceitavelmente grande. Em contraste, uma estrutura de dados de corda tem o desempenho estável, independentemente do tamanho dos dados. Além disso, o espaço complexidade para cordas e vetores são O(n). Em resumo, as cordas são preferíveis quando o volume dados é grande e modificado frequentemente.