Arbre rouge-noir pour l'édition de texte

Question

Je lisais this great article par Joaquin Cuenca Abela. Il parle d'utiliser un arbre rouge-noir pour implémenter une table de pièces, plutôt qu'une liste doublement chaînée.

J'ai quelques difficultés à comprendre comment cela pourrait se rapporter à un tampon subissant des changements. Par exemple, prenez ces deux tampons (original, ajoutez):

Hello!\0 Original 
y   Append 

Et disons que la table de pièce ressemble à ceci:

buffer start length 
original 0  2 
original 5  2 
append 0  1 

Nous devrions finir avec:

Hey!\0 

En utilisant une liste doublement chaînée, ceci pourrait être implémenté comme ceci:

------------------ ------------------- ---------------- 
Buffer = ORIGINAL| |Buffer = ORIGINAL| |Buffer = APPEND 
Start = 0  |<--|Start = 5  |<--|Start = 0 
Length = 2  | |Length = 2  | |Length = 1 
Next = 0x01 |-->|Next = 0x02 |-->|Next = NULL 
Previous = NULL | |Previous = 0x01 | |Previous = 0x01 
------------------ ------------------- ---------------- 

Si le fichier est initialement chargé en tant que tableau char, ou quelque chose, cela semble vraiment trivial et rapide à exécuter après une modification. D'autre part, pour autant que je le comprends, l'arbre rouge-noir ressemblerait à ceci:

     ------------------ 
         size  = 2 
         size_left = 1 
         size_right = 2 
         colour  = black 
         ------------------ 
         /   \ 
        /    \ 
        /    \ 
      ----------------  ---------------- 
      size  = 1  size  = 2 
      size_left = 0  size_left = 0 
      size_right = 0  size_right = 0 
      colour  = red  colour  = red 
      ----------------  ---------------- 
      /  \   /   \ 
      /   \   /   \ 
     NULL   NULL  NULL   NULL 

Je ne vois pas de façon claire pour repeindre le reste du document après une édition. Bien sûr, insérer/supprimer/rechercher serait plus rapide pour ajouter des morceaux à l'arbre. Mais il me manque comment on pourrait construire le tampon édité pour l'affichage.

Qu'est-ce qui me manque? Si j'avais un éditeur, et que j'ai supprimé/inséré un morceau de texte, comment pourrais-je traverser l'arbre pour repeindre le tampon et refléter correctement cette édition? Et, comment cela serait-il plus rapide que la complexité de temps O (n) offerte par la liste chaînée?

Answer 1

Je ne comprends pas vraiment le diagramme que vous fournissez de l'arbre, parce que (contrairement au diagramme de liste lié) ils ne semblent pas avoir de relation avec les données stockées. En pratique, ils auront essentiellement les mêmes champs de données (Buffer, Start et Length) plus un, Size, qui est la taille totale des pièces dans le sous-arbre dirigé par le noeud. Au lieu des pointeurs précédent et suivant, ils auront des pointeurs gauche et droit (enfant). Et, bien sûr, ils auront des données supplémentaires nécessaires pour maintenir l'arbre équilibré (un bit rouge/noir dans le cas des arbres rouges/noirs, mais je ne pense pas que le mécanisme pour maintenir l'équilibre est important ici, vous pouvez utiliser des arbres AVL au lieu d'arbres rouges/noirs, par exemple, donc je vais ignorer cette partie du nœud ici

Le champ Taille est nécessaire pour trouver les données à un moment donné. offset (et par conséquent, pourrait être omis s'il n'y avait jamais besoin de faire une telle recherche.) Je pense que l'article lié mesure Taille en morceaux, alors que j'ai tendance à mesurer la taille en caractères (ou même octets), ce qui est Comme le note l'article lié, le champ Taille peut facilement être maintenu en temps logarithmique précisément parce qu'il rs à la taille du sous-arbre, plutôt qu'à son emplacement dans le flux de données.

Vous utilisez le champ Taille pour rechercher un nœud par décalage de tampon. Si le décalage est inférieur à la taille de l'enfant gauche, vous recurerez dans l'enfant gauche; si c'est au moins la longueur actuelle plus la taille de l'enfant gauche, vous soustrayez cette somme du décalage et recourez dans l'enfant droit. Sinon, le nœud actuel contient le décalage souhaité. Cela ne peut pas prendre plus de temps que la profondeur maximale de l'arbre, qui est O (log N) si l'arbre est raisonnablement équilibré.

je aussi un peu confus par votre schéma de liste chaînée, qui me semble représenterai le tampon He|!\0|y, alors que je pense que ce soit He|y|!\0:

------------------ ------------------- ------------------- 
Buffer = ORIGINAL| |Buffer = APPEND | |Buffer = ORIGINAL| 
Start = 0  |<--|Start = 0  |<--|Start = 5  | 
Length = 2  | |Length = 1  | |Length = 2  | 
Next = 0x01 |-->|Next = 0x02 |-->|Next = NULL | 
Previous = NULL | |Previous = 0x01 | |Previous = 0x01 | 
------------------ ------------------- ------------------- 

L'arbre équilibré équivalent est:

     ------------------- 
         | Size = 5  | 
         | Buffer = APPEND | 
         | Start = 0  | 
         | Length = 1  | 
         ------------------- 
         /   \ 
        /    \ 
        /    \ 
      ------------------- ------------------- 
      |Size = 2  | |Size = 2  | 
      |Buffer = ORIGINAL| |Buffer = ORIGINAL| 
      |Start = 0  | |Start = 5  | 
      |Length = 2  | |Length = 2  | 
      ------------------- ------------------- 
      /  \   /   \ 
      /   \  /   \ 
      NULL   NULL NULL   NULL 

l'algorithme pour trouver le noeud suivant dans l'ordre à partir d'un noeud donné est la suivante:

1. Alors que le pointeur enfant droit est NULL, revenez au parent. Continuez à vous déplacer vers le parent jusqu'à ce qu'un noeud soit trouvé dont le pointeur enfant droit n'est ni NULL ni l'enfant renvoyé.

2. Déplacez-vous vers le bon enfant.

3. Alors que le pointeur de l'enfant gauche n'est pas NULL, passez à l'enfant gauche

une application donnée de cet algorithme pourrait évidemment prendre O (log N) itérations des étapes 1 et/ou 3. Cependant , applications répétées (comme dans le cas où vous traversez le tampon dans un certain nombre de nœuds) sera linéaire au total car un lien donné (parent ⇆ enfant) sera traversé exactement deux fois, une fois dans chaque direction. Ainsi, le nombre total de liens parcourus si vous parcourez tout l'arbre est le double du nombre de liens dans l'arbre. (Et l'arbre a un moins lien que les noeuds, car il est un arbre.)

---

Si vous mesurez la taille des caractères, vous pouvez éviter la nécessité pour le champ « Longueur », parce que la longueur de la Les données directement référencées par un nœud sont simplement la différence entre la taille de sous-arbre du nœud et la somme de ses tailles de sous-arbres enfants. Cela peut (presque) réduire la taille d'un nœud à la taille du nœud de liste liée, en supposant que vous pouvez trouver un moyen de coder le bit rouge/noir (ou d'autres informations d'équilibrage) dans ce qui serait autrement des bits de remplissage. D'autre part, il est assez fréquent de voir des implémentations d'arbre binaire avec des pointeurs parents, ainsi que deux pointeurs enfants. (Il est clair que cela peut aider en regardant l'algorithme de cheminement ci-dessus.) Cependant, il n'est pas nécessaire de stocker les pointeurs parents car ils peuvent, par exemple, être conservés pendant un chemin d'arbre donné dans un tableau de pointeurs parents indexés par profondeur dans l'arbre. Ce tableau n'est évidemment pas plus grand que la profondeur maximale de l'arbre, donc un petit tableau (~ 50) de longueur fixe peut être utilisé.

Ces optimisations sont également bien au-delà de cette réponse.

Answer 2

Si j'avais un éditeur, et que j'ai supprimé/inséré un morceau de texte, comment je traverserais l'arbre pour repeindre le tampon et refléter correctement cette édition? Et, comment cela serait-il plus rapide que la complexité de temps O (n) offerte par la liste chaînée?

Supposons que la table de pièces est grande et que le repeindre la partie du tampon visible sur l'écran nécessite généralement de visiter seulement quelques noeuds consécutifs. Supposons que les nœuds que vous devez visiter après une modification particulière se trouvent au milieu ou à la fin du document.Avec une liste à double liaison, vous devrez peut-être parcourir plusieurs noeuds à partir de la table de début pour accéder au début de la modification. C'est O (n). De là, vous marchez à travers les quelques nœuds suivants pour faire la peinture.

Avec un arbre équilibré, vous pouvez trouver ce premier noeud dans O (log_2 n). À partir de là, vous effectuez une traversée en ordre pour visiter les prochains nœuds nécessaires à la peinture.

La mise à jour des positions dans l'arborescence après l'ajout, la suppression ou la modification d'une pièce consiste simplement à ajouter/soustraire une valeur aux positions des ancêtres en commençant par le parent du nœud nouveau/modifié. Cela aussi est O (log_2 n).