{"id":12654,"date":"2021-11-15T18:18:01","date_gmt":"2021-11-15T23:18:01","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12654"},"modified":"2021-11-15T18:18:01","modified_gmt":"2021-11-15T23:18:01","slug":"tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/","title":{"rendered":"TR-126: Adaptive Structuring of Binary Search Trees Using Conditional Rotations"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-126<\/strong>
\nOctober 1987<\/p>\n

Adaptive Structuring of Binary Search Trees Using Conditional Rotations<\/h2>\n
\n
\n
P. Cheetham, B.J. Oommen , D.T.H. Ng<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n

Consider a set= {A1 , A2, … , AN} of records, where each record is identified by
\na unique key. The records are accessed based on a set of access probabilities
\ni>={s1 ,s2, … , sN } and are to be arranged lexicographically using a binary search tree. If i> is known a priori, it is well known [7] that an optimal binary search tree may be constructed using and i>. We consider the case when i> is not known a priori. A new restructuring heuristic is introduced that requires three extra integer memory Iocations per record, and this restructuring of the tree is performed only if it decreases the weighted path length of. the overall resultant tree. We also present a space optimized version of the latter restructuring mechanism which requires only one extra integer field per record. We show that the cost of the tree is reduced by each restructuring operation, and present experimental results to demonstrate the superiority of our algorithm over all other efficient static and dynamic schemes that exist in the literature.<\/p>\n<\/div>\n

TR-126.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-126 October 1987 Adaptive Structuring of Binary Search Trees Using Conditional Rotations P. Cheetham, B.J. Oommen , D.T.H. Ng Abstract Consider a set= {A1 , A2, … , AN} of records, where each record is identified by a unique key. The records are accessed based on a set of access probabilities […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11827,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-126: Adaptive Structuring of Binary Search Trees Using Conditional Rotations - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-126 October 1987 Adaptive Structuring of Binary Search Trees Using Conditional Rotations P. Cheetham, B.J. Oommen\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/\",\"name\":\"TR-126: Adaptive Structuring of Binary Search Trees Using Conditional Rotations - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-15T23:18:01+00:00\",\"dateModified\":\"2021-11-15T23:18:01+00:00\",\"description\":\"Carleton University Technical Report TR-126 October 1987 Adaptive Structuring of Binary Search Trees Using Conditional Rotations P. Cheetham, B.J. Oommen\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1987\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-126: Adaptive Structuring of Binary Search Trees Using Conditional Rotations\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-126: Adaptive Structuring of Binary Search Trees Using Conditional Rotations - School of Computer Science","description":"Carleton University Technical Report TR-126 October 1987 Adaptive Structuring of Binary Search Trees Using Conditional Rotations P. Cheetham, B.J. Oommen","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/","name":"TR-126: Adaptive Structuring of Binary Search Trees Using Conditional Rotations - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-15T23:18:01+00:00","dateModified":"2021-11-15T23:18:01+00:00","description":"Carleton University Technical Report TR-126 October 1987 Adaptive Structuring of Binary Search Trees Using Conditional Rotations P. Cheetham, B.J. Oommen","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-126-adaptive-structuring-of-binary-search-trees-using-conditional-rotations\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1987","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/"},{"@type":"ListItem","position":5,"name":"TR-126: Adaptive Structuring of Binary Search Trees Using Conditional Rotations"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12654"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12654"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12654\/revisions"}],"predecessor-version":[{"id":12655,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12654\/revisions\/12655"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11827"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12654"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}