{"id":4377,"date":"2018-12-06T06:00:00","date_gmt":"2018-12-06T04:00:00","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4377"},"modified":"2019-01-17T15:46:10","modified_gmt":"2019-01-17T13:46:10","slug":"elemento-del-arbol-binario-completo-segun-su-posicion","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/elemento-del-arbol-binario-completo-segun-su-posicion\/","title":{"rendered":"Elemento del \u00e1rbol binario completo seg\u00fan su posici\u00f3n"},"content":{"rendered":"<p>Un <a href=\"http:\/\/bit.ly\/2DUr53g\">\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<p>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<pre lang=\"text\">\n                  1\n                 \/  \\\n                \/    \\\n               \/      \\\n              2        3\n             \/ \\      \/ \\\n            4   5    6   7\n           \/ \\ \n          8   9 \n<\/pre>\n<p>Los \u00e1rboles binarios se puede representar mediante el siguiente tipo<\/p>\n<pre lang=\"text\">\n   data Arbol = H\n              | N Integer Arbol Arbol\n     deriving (Show, Eq)\n<\/pre>\n<p>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<p>Los tipos de los movimientos y de las posiciones se definen por<\/p>\n<pre lang=\"text\">\n   data Movimiento = I | D deriving (Show, Eq)\n   type Posicion   = [Movimiento]\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   elementoEnPosicion :: Posicion -> Integer\n<\/pre>\n<p>tal que (elementoEnPosicion ms) es el elemento en la posici\u00f3n ms. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   elementoEnPosicion [D,I]    ==  6\n   elementoEnPosicion [D,D]    ==  7\n   elementoEnPosicion [I,I,D]  ==  9\n   elementoEnPosicion []       ==  1\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\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\nelementoEnPosicion :: Posicion -> Integer\nelementoEnPosicion ms =\n  aux ms (arbolBinarioCompleto (2^(1 + length ms)))\n  where aux []     (N x _ _) = x\n        aux (I:ms) (N _ i _) = aux ms i\n        aux (D:ms) (N _ _ d) = aux ms d\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-- 2\u00aa soluci\u00f3n\n-- ===========\n\nelementoEnPosicion2 :: Posicion -> Integer\nelementoEnPosicion2 = aux . reverse\n  where aux []     = 1\n        aux (I:ms) = 2 * aux ms\n        aux (D:ms) = 2 * aux ms + 1\n\n-- Equivalencia\n-- ============\n\n-- La propiedad es\nprop_elementoEnPosicion_equiv :: Positive Integer -> Bool\nprop_elementoEnPosicion_equiv (Positive n) =\n  elementoEnPosicion  ps == n &&\n  elementoEnPosicion2 ps == n \n  where ps = posicionDeElemento n\n\n-- tal que (posicionDeElemento n) es la posici\u00f3n del elemento n en el\n-- \u00e1rbol binario completo. Por ejemplo,\n--    posicionDeElemento 6  ==  [D,I]\n--    posicionDeElemento 7  ==  [D,D]\n--    posicionDeElemento 9  ==  [I,I,D]\n--    posicionDeElemento 1  ==  []\nposicionDeElemento :: Integer -> Posicion\nposicionDeElemento 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-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_elementoEnPosicion_equiv\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> length (show (elementoEnPosicion (replicate (3*10^5) D)))\n--    90310\n--    (1.96 secs, 11,518,771,016 bytes)\n--    \u03bb> length (show (elementoEnPosicion2 (replicate (3*10^5) D)))\n--    90310\n--    (14.32 secs, 11,508,181,176 bytes)\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nLas m\u00e1s hondas palabras<br \/>\ndel sabio nos ense\u00f1an<br \/>\nlo que el silbar del viento cuando sopla<br \/>\no el sonar de las aguas cuando ruedan.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>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&#8230;<\/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\/4377"}],"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=4377"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4377\/revisions"}],"predecessor-version":[{"id":4581,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4377\/revisions\/4581"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4377"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4377"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4377"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}