Understanding Clojure's Persistent Vectors, pt. 1 (2013)
Les vecteurs persistants de Clojure, conçus par Rich Hickey, sont des structures arborescentes équilibrées et ordonnées où chaque modification crée un nouveau vecteur sans modifier l'ancien. Les opérations de mise à jour (assoc, update-in) se font par copie de chemin : on clone les nœuds le long du chemin vers la feuille et on remplace la valeur dans la feuille copiée. L'ajout en fin (conj) suit trois cas : il y a de la place dans la feuille droite, il faut générer des nœuds intermédiaires inexistants, ou la racine déborde et on crée une nouvelle racine, l'overflow se produisant quand la taille est une puissance du facteur de branchement. La suppression de la dernière valeur (pop) est symétrique : on copie le chemin et enlève l'élément si possible, on supprime et propage les nœuds vides vers le haut, et on remplace la racine par son unique enfant si nécessaire. Avec un facteur de branchement élevé (32 dans Clojure) les arbres restent très peu profonds et les opérations sont en pratique quasi-constantes (O(log_32 n)), et des optimisations comme la queue, les transients et subvec seront traitées dans des articles ultérieurs.