{"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":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","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":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-126: Adaptive Structuring of Binary Search Trees Using Conditional Rotations\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/\">Technical Report<\/a> <strong>TR-126<\/strong><br>\nOctober 1987<\/p>\n\n\n\n<h2 id=\"adaptive-structuring-of-binary-search-trees-using-conditional-rotations\" class=\"wp-block-heading tr_t1\">Adaptive Structuring of Binary Search Trees Using Conditional Rotations<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">P. Cheetham, B.J. Oommen , D.T.H. Ng<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<p>Consider a set= {A1 , A2, &#8230; , AN} of records, where each record is identified by<br>\na unique key. The records are accessed based on a set of access probabilities<br>\ni&gt;={s1 ,s2, &#8230; , sN } and are to be arranged lexicographically using a binary search tree. If i&gt; is known a priori, it is well known [7] that an optimal binary search tree may be constructed using  and i&gt;. We consider the case when i&gt; 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\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/tr-126.pdf\">TR-126.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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, &#8230; , AN} of records, where each record is identified by a unique key. The records are accessed based on a set of access probabilities [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11827,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12654","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12654","targetHints":{"allow":["GET"]}}],"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\/2"}],"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"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12654"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}