{"id":4373,"date":"2018-12-05T06:00:20","date_gmt":"2018-12-05T04:00:20","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4373"},"modified":"2019-01-19T12:03:52","modified_gmt":"2019-01-19T10:03:52","slug":"posiciones-en-arboles-binarios-completos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/posiciones-en-arboles-binarios-completos\/","title":{"rendered":"Posiciones en \u00e1rboles binarios completos"},"content":{"rendered":"

Un \u00e1rbol binario completo<\/a> es un \u00e1rbol binario que tiene todos los nodos posibles hasta el pen\u00faltimo nivel, y donde los elementos del \u00faltimo nivel est\u00e1n colocados de izquierda a derecha sin dejar huecos entre ellos.<\/p>\n

La numeraci\u00f3n de los \u00e1rboles binarios completos se realiza a partir de la ra\u00edz, recorriendo los niveles de izquierda a derecha. Por ejemplo,<\/p>\n

\n                  1\n                 \/  \\\n                \/    \\\n               \/      \\\n              2        3\n             \/ \\      \/ \\\n            4   5    6   7\n           \/ \\    \n          8   9 \n<\/pre>\n
Los \u00e1rboles binarios se puede representar mediante el siguiente tipo<\/p>\n
\n   data Arbol = H\n              | N Integer Arbol Arbol\n     deriving (Show, Eq)\n<\/pre>\n
Cada posici\u00f3n de un elemento de un \u00e1rbol es una lista de movimientos hacia la izquierda o hacia la derecha. Por ejemplo, la posici\u00f3n de 9 en al \u00e1rbol anterior es [I,I,D].<\/p>\n
Los tipos de los movimientos y de las posiciones se definen por<\/p>\n
\n   data Movimiento = I | D deriving (Show, Eq)\n   type Posicion   = [Movimiento]\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   posicionDeElemento :: Integer -> Posicion\n<\/pre>\n
tal que (posicionDeElemento n) es la posici\u00f3n del elemento n en el \u00e1rbol binario completo. Por ejemplo,<\/p>\n
\n   posicionDeElemento 6  ==  [D,I]\n   posicionDeElemento 7  ==  [D,D]\n   posicionDeElemento 9  ==  [I,I,D]\n   posicionDeElemento 1  ==  []\n\n   length (posicionDeElemento (10^50000))  ==  166096\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Test.QuickCheck\n\ndata Arbol = H\n           | N Integer Arbol Arbol\n  deriving (Eq, Show)\n\ndata Movimiento = I | D deriving (Show, Eq)\n\ntype Posicion = [Movimiento]\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nposicionDeElemento :: Integer -> Posicion\nposicionDeElemento n =\n  head (posiciones n (arbolBinarioCompleto n))\n\n-- (arbolBinarioCompleto n) es el \u00e1rbol binario completo con n\n-- nodos. Por ejemplo, \n--    \u03bb> arbolBinarioCompleto 4\n--    N 1 (N 2 (N 4 H H) H) (N 3 H H)\n--    \u03bb> pPrint (arbolBinarioCompleto 9)\n--    N 1\n--      (N 2\n--         (N 4\n--            (N 8 H H)\n--            (N 9 H H))\n--         (N 5 H H))\n--      (N 3\n--         (N 6 H H)\n--         (N 7 H H))\narbolBinarioCompleto :: Integer -> Arbol\narbolBinarioCompleto n = aux 1\n  where aux i | i <= n    = N i (aux (2*i)) (aux (2*i+1))\n              | otherwise = H\n\n-- (posiciones n a) es la lista de las posiciones del elemento n\n-- en el \u00e1rbol a. Por ejemplo,\n--    posiciones 9 (arbolBinarioCompleto 9)  ==  [[I,I,D]]\nposiciones :: Integer -> Arbol -> [Posicion]\nposiciones n a = aux n a [[]]\n  where aux _ H _                      = []\n        aux n (N x i d) cs | x == n    = cs ++ ps\n                           | otherwise = ps\n          where ps = map (I:) (aux n i cs) ++\n                     map (D:) (aux n d cs)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nposicionDeElemento2 :: Integer -> Posicion\nposicionDeElemento2 1 = []\nposicionDeElemento2 n\n  | even n    = posicionDeElemento2 (n `div` 2) ++ [I]\n  | otherwise = posicionDeElemento2 (n `div` 2) ++ [D]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nposicionDeElemento3 :: Integer -> Posicion\nposicionDeElemento3 = reverse . aux\n  where aux 1 = []\n        aux n | even n    = I : aux (n `div` 2) \n              | otherwise = D : aux (n `div` 2) \n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nposicionDeElemento4 :: Integer -> Posicion\nposicionDeElemento4 n =\n  [f x | x <- tail (reverse (binario n))]\n  where f 0 = I\n        f 1 = D\n\n-- (binario n) es la lista de los d\u00edgitos de la representaci\u00f3n binaria\n-- de n. Por ejemplo,\n--    binario 11  ==  [1,1,0,1]\nbinario :: Integer -> [Integer]\nbinario n\n  | n < 2     = [n]\n  | otherwise = n `mod` 2 : binario (n `div` 2)\n\n-- Equivalencia\n-- ============\n\n-- La propiedad es\nprop_posicionDeElemento_equiv :: Positive Integer -> Bool\nprop_posicionDeElemento_equiv (Positive n) =\n  posicionDeElemento n == posicionDeElemento2 n &&\n  posicionDeElemento n == posicionDeElemento3 n &&\n  posicionDeElemento n == posicionDeElemento4 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_posicionDeElemento_equiv\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> posicionDeElemento (10^7)\n--    [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I]\n--    (5.72 secs, 3,274,535,328 bytes)\n--    \u03bb> posicionDeElemento2 (10^7)\n--    [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I]\n--    (0.01 secs, 189,560 bytes)\n--    \u03bb> posicionDeElemento3 (10^7)\n--    [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I]\n--    (0.01 secs, 180,728 bytes)\n--    \u03bb> posicionDeElemento4 (10^7)\n--    [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I]\n--    (0.01 secs, 184,224 bytes)\n--    \n--    \u03bb> length (posicionDeElemento2 (10^4000))\n--    13287\n--    (2.80 secs, 7,672,011,280 bytes)\n--    \u03bb> length (posicionDeElemento3 (10^4000))\n--    13287\n--    (0.03 secs, 19,828,744 bytes)\n--    \u03bb> length (posicionDeElemento4 (10^4000))\n--    13287\n--    (0.03 secs, 18,231,536 bytes)\n--    \n--    \u03bb> length (posicionDeElemento3 (10^50000))\n--    166096\n--    (1.34 secs, 1,832,738,136 bytes)\n--    \u03bb> length (posicionDeElemento4 (10^50000))\n--    166096\n--    (1.70 secs, 1,812,806,080 bytes)\n<\/pre>\n
Pensamiento<\/h4>\n
\nEl ojo que ves no es
\nojo porque t\u00fa lo veas;
\nes ojo porque te ve.<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
Un \u00e1rbol binario completo es un \u00e1rbol binario que tiene todos los nodos posibles hasta el pen\u00faltimo nivel, y donde los elementos del \u00faltimo nivel est\u00e1n colocados de izquierda a derecha sin dejar huecos entre ellos. La numeraci\u00f3n de los \u00e1rboles binarios completos se realiza a partir de la ra\u00edz, recorriendo los niveles de izquierda…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[269,8,91,71,10,11,6,32,45],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4373"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=4373"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4373\/revisions"}],"predecessor-version":[{"id":4584,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4373\/revisions\/4584"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4373"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4373"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4373"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}