{"id":5379,"date":"2016-03-31T18:11:05","date_gmt":"2016-03-31T16:11:05","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5379"},"modified":"2016-04-01T08:12:28","modified_gmt":"2016-04-01T06:12:28","slug":"i1m2015-el-tad-de-los-arboles-binarios-de-busqueda-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-el-tad-de-los-arboles-binarios-de-busqueda-en-haskell\/","title":{"rendered":"I1M2015: El TAD de los \u00e1rboles binarios de b\u00fasqueda en Haskell"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado el tipo abstracto de datos de los \u00e1rboles binarios de b\u00fasqueda.<\/p>\n<p>Un <a href=\"http:\/\/es.wikipedia.org\/wiki\/\u00c1rbol_binario_de_b\u00fasqueda\">\u00e1rbol binario de b\u00fasqueda (ABB)<\/a> (<a href=\"http:\/\/en.wikipedia.org\/wiki\/Binary_search_tree\">binary search tree<\/a>) en ingl\u00e9s) es un \u00e1rbol binario tal que el valor de cada nodo es mayor que los valores de su sub\u00e1rbol izquierdo y es menor que los valores de su sub\u00e1rbol derecho y, adem\u00e1s, ambos sub\u00e1rboles son \u00e1rboles binarios de b\u00fasqueda. Por ejemplo, al almacenar los valores de [2,3,4,5,6,8,9] en un ABB se puede obtener los siguientes ABB:<\/p>\n<pre lang=\"text\">\n    5                     5\n  \/   \\                 \/   \\\n 2     6               3     8\n  \\     \\             \/ \\   \/ \\\n   4     8           2   4 6   9\n  \/       \\\n 3         9\n<\/pre>\n<p>El objetivo principal de los ABB es reducir el tiempo de acceso a los valores.<\/p>\n<p>El contenido de la clase ha sido el siguiente:<\/p>\n<ul>\n<li>la signatura del TAD de los \u00e1rboles binarios de b\u00fasqueda;<\/li>\n<li>las propiedades del TAD de los \u00e1rboles binarios de b\u00fasqueda;<\/li>\n<li>la implementaci\u00f3n, en Haskell, de los \u00e1rboles binarios de b\u00fasqueda mediante tipos de datos algebraicos y<\/li>\n<li>la comprobaci\u00f3n con QuickCheck de sus propiedades.<\/li>\n<\/ul>\n<p>Las transparencias usadas en la clase son las del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\/temas\/tema-19.pdf\">tema 19<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos estudiado el tipo abstracto de datos de los \u00e1rboles binarios de b\u00fasqueda. Un \u00e1rbol binario de b\u00fasqueda (ABB) (binary search tree) en ingl\u00e9s) es un \u00e1rbol binario tal que el valor de cada nodo es mayor que&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[250],"tags":[270,310],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5379"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=5379"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5379\/revisions"}],"predecessor-version":[{"id":5380,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5379\/revisions\/5380"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5379"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5379"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5379"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}