{"id":493,"date":"2014-07-17T07:00:48","date_gmt":"2014-07-17T05:00:48","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=493"},"modified":"2015-05-01T09:02:42","modified_gmt":"2015-05-01T07:02:42","slug":"insercion-en-arboles-binarios-de-busqueda","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/insercion-en-arboles-binarios-de-busqueda\/","title":{"rendered":"Inserci\u00f3n en \u00e1rboles binarios de b\u00fasqueda"},"content":{"rendered":"<pre lang=\"text\">\n-- Un \u00e1rbol binario de b\u00fasqueda (ABB) es un \u00e1rbol binario tal que el de\n-- cada nodo es mayor que los valores de su sub\u00e1rbol izquierdo y es\n-- menor que los valores de su sub\u00e1rbol derecho y, adem\u00e1s, ambos\n-- sub\u00e1rboles son \u00e1rboles binarios de b\u00fasqueda. Por ejemplo, al\n-- almacenar los valores de [8,4,2,6,3] en un ABB se puede obtener el\n-- siguiente ABB:\n-- \n--       5 \n--      \/ \\\n--     \/   \\ \n--    2     6 \n--         \/ \\ \n--        4   8 \n-- \n-- Los ABB se pueden representar como tipo de dato algebraico:\n--    data ABB = V\n--             | N Int ABB ABB\n--             deriving (Eq, Show)\n-- Por ejemplo, la definici\u00f3n del ABB anteriore es\n--    ej :: ABB\n--    ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))\n--\n-- Definir la funci\u00f3n \n--    inserta :: Int -> ABB -> ABB\n-- tal que (inserta v a) es el \u00e1rbol binario de b\u00fasqueda \n-- obtenido a\u00f1adiendo el valor v al ABB a, si no es uno \n-- de sus valores. Por ejemplo, \n--    ghci>  inserta 5 ej\n--    N 3 (N 2 V V) (N 6 (N 4 V (N 5 V V)) (N 8 V V))\n--    ghci>  inserta 1 ej\n--    N 3 (N 2 (N 1 V V) V) (N 6 (N 4 V V) (N 8 V V))\n--    ghci>  inserta 2 ej\n--    N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\ndata ABB = V\n         | N Int ABB ABB\n         deriving (Eq, Show)\n\nej :: ABB \nej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))\n\ninserta :: Int -> ABB -> ABB\ninserta v1 V = N v1 V V\ninserta v1 (N v i d) \n    | v1 == v   = N v i d\n    | v1 < v    = N v (inserta v1 i) d\n    | otherwise = N v i (inserta v1 d)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>&#8212; Un \u00e1rbol binario de b\u00fasqueda (ABB) es un \u00e1rbol binario tal que el de &#8212; cada nodo es mayor que los valores de su sub\u00e1rbol izquierdo y es &#8212; menor que los valores de su sub\u00e1rbol derecho y, adem\u00e1s, ambos &#8212; sub\u00e1rboles son \u00e1rboles binarios de b\u00fasqueda. Por ejemplo, al &#8212; almacenar los valores&#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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/493"}],"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=493"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/493\/revisions"}],"predecessor-version":[{"id":661,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/493\/revisions\/661"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=493"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=493"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=493"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}