Mettre en œuvre un immuable deque qu'un équilibre de l'arbre binaire?

Question

J'ai pensé pendant un certain temps sur la façon d'aller sur la mise en œuvre d'un deque (c'est un double-ended queue) comme des données immuables de la structure.

Il semble y avoir différentes façons de le faire. Autant que je sache, immuable structures de données sont généralement hiérarchique, de sorte qu'une grande partie de celui-ci peut être réutilisé après la modification des opérations telles que l'insertion ou la suppression d'un élément.

Eric Lippert a deux articles sur son blog à propos de ce sujet, ainsi que des exemples d'implémentations en C#.

Ses deux implémentations me paraît plus complexe qu'est réellement nécessaire. Ne pouvait pas deques simplement être mis en œuvre comme des arbres binaires, où les éléments ne peuvent être insérés ou retirés sur le très "à gauche" (le front) et sur les très "à droite" (le dos) de l'arbre?

                               o
                              / \
                             …   …
                            /     \
                           …       …
                          / \     / \
              front -->  L   …   …   R  <-- back

En outre, l'arbre pourrait être raisonnablement équilibré avec des rotations:

• droit des rotations lors de l'insertion à l'avant ou à l'enlèvement de l'arrière, et
• gauche rotations lors de l'enlèvement de l'avant ou de l'insertion à l'arrière.

Eric Lippert est, à mon avis, une personne très intelligente qui je respecte profondément, mais il n'a apparemment pas envisager cette approche. Donc je me demande, c'est pour une bonne raison? Mon approche proposée de la mise en œuvre de deques naïf?

Answer 1

Si vous utilisez un arbre binaire équilibré, des insertions et des suppressions sur les deux extrémités sont O(lg N) (en moyenne et au pire des cas). L'approche utilisée dans Eric Lippert implémentations est plus efficace, il exécute en temps constant dans la moyenne des cas (le pire des cas encore est O(lg N)).

Rappelez-vous que la modification d'une immuable arbre implique la réécriture de tous les parents du nœud que vous souhaitez modifier. Donc, pour un deque, vous ne voulez pas que l'arbre soit équilibré; au contraire, vous voulez L et R nœuds pour être au plus près de la racine que possible, tandis que les nœuds dans le milieu de l'arbre peut être plus loin.

Answer 2

Les autres réponses sont toutes géniales. Je vais ajouter que j'ai choisi le doigt de l'arbre de la mise en œuvre d'une deque parce qu'il fait inhabituel et intéressant d'utiliser le type générique du système. La plupart des structures de données récursives dans leur structure, mais cette technique met la récursivité aussi dans le type de système dont je n'avais pas vu avant; j'ai pensé qu'il pourrait être d'intérêt général.

Answer 3

Ne pouvait pas deques simplement être mis en œuvre comme des arbres binaires, où les éléments peuvent seulement être inséré ou supprimé sur le très "à gauche" (le front) et sur le très "à droite" (le dos) de l'arbre?

Absolument. Une version modifiée d'une hauteur équilibrée arbre AVL arbres en particulier, il serait très facile à mettre en œuvre. Cependant il moyen de remplissage des arbres de la file d'attente avec n éléments exige O(n lg n) du temps -- vous devriez tirer pour une deque qui a les mêmes caractéristiques de performance que la mutable homologue.

Vous pouvez créer un simple immuable deque avec amorti de la constante de temps des opérations pour toutes les grandes opérations à l'aide de deux piles, une à gauche et à droite de la pile. PushLeft et PushRight correspondent à pousser des valeurs à gauche et à droite de la pile respectivement. Vous pouvez obtenir Deque.Hd et Deque.Tl de la LeftStack.Hd et LeftStack.Tl; si votre LeftStack est vide, mis LeftStack = RightStack.Inverse et RightStack = pile vide.

type 'a deque = Node of 'a list * 'a list    // '

let peekFront = function
    | Node([], []) -> failwith "Empty queue"
    | Node(x::xs, ys) -> x
    | Node([], ys) -> ys |> List.rev |> List.head
let peekRear = function
    | Node([], []) -> failwith "Empty queue"
    | Node(xs, y::ys) -> y
    | Node(xs, []) -> xs |> List.rev |> List.head
let pushFront v = function
    | Node(xs, ys) -> Node(v::xs, ys)
let pushRear v = function
    | Node(xs, ys) -> Node(xs, v::ys)
let tl = function
    | Node([], []) -> failwith "Empty queue"
    | Node([], ys) -> Node(ys |> List.rev |> List.tail, [])
    | Node(x::xs, ys) -> Node(xs, ys)

C'est un très commun de la mise en œuvre, et il est très facile à optimiser pour de meilleures performances.