{"id":2802,"date":"2025-06-01T13:47:03","date_gmt":"2025-06-01T13:47:03","guid":{"rendered":"https:\/\/diznr.com\/?p=2802"},"modified":"2025-06-01T13:47:03","modified_gmt":"2025-06-01T13:47:03","slug":"aad-optimal-binary-search-tree-with-practical-example-for-deeper-understanding-part-25","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/aad-optimal-binary-search-tree-with-practical-example-for-deeper-understanding-part-25\/","title":{"rendered":"AAD- Optimal Binary Search Tree With Practical Example ( for Deeper Understanding) Part 25."},"content":{"rendered":"<p>AAD- Optimal Binary Search Tree With Practical Example ( for Deeper Understanding) Part 25.<\/p>\n<p>[fvplayer id=&#8221;120&#8243;]<\/p>\n<h3 data-start=\"0\" data-end=\"83\"><strong data-start=\"4\" data-end=\"81\">Optimal Binary Search Tree (OBST) \u2013 Advanced Analysis &amp; Practical Example<\/strong><\/h3>\n<h4 data-start=\"85\" data-end=\"148\"><strong data-start=\"90\" data-end=\"146\">1. Introduction to Optimal Binary Search Tree (OBST)<\/strong><\/h4>\n<p data-start=\"149\" data-end=\"338\">An <strong data-start=\"152\" data-end=\"189\">Optimal Binary Search Tree (OBST)<\/strong> is a specialized <strong data-start=\"207\" data-end=\"235\">Binary Search Tree (BST)<\/strong> that is structured in a way that minimizes the expected search cost (or total weighted path length).<\/p>\n<p data-start=\"340\" data-end=\"575\">When searching for elements in a <strong data-start=\"373\" data-end=\"380\">BST<\/strong>, the cost depends on how frequently each element is accessed. Instead of constructing a standard BST, OBST minimizes the average search time based on given probabilities of searching for keys.<\/p>\n<h3 data-start=\"582\" data-end=\"615\"><strong data-start=\"586\" data-end=\"613\">2. Why Do We Need OBST?<\/strong><\/h3>\n<p data-start=\"616\" data-end=\"737\">A regular BST does not always guarantee an optimal search time. If the tree is unbalanced, the search cost may be high.<\/p>\n<ul data-start=\"738\" data-end=\"972\">\n<li data-start=\"738\" data-end=\"860\">OBST ensures that frequently accessed elements are placed <strong data-start=\"798\" data-end=\"820\">closer to the root<\/strong>, reducing <strong data-start=\"831\" data-end=\"846\">search cost<\/strong> on average.<\/li>\n<li data-start=\"861\" data-end=\"972\">This is useful in <strong data-start=\"881\" data-end=\"970\">database indexing, compiler design (syntax trees), and information retrieval systems.<\/strong><\/li>\n<\/ul>\n<h3 data-start=\"979\" data-end=\"1010\"><strong data-start=\"983\" data-end=\"1008\">3. Problem Definition<\/strong><\/h3>\n<p data-start=\"1011\" data-end=\"1121\">Given <strong data-start=\"1017\" data-end=\"1027\">n keys<\/strong> <span class=\"katex\"><span class=\"katex-mathml\">K1,K2,&#8230;,KnK_1, K_2, &#8230;, K_n<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">1<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mpunct\">,<\/span><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mpunct\">,<\/span><span class=\"mord\">&#8230;<\/span><span class=\"mpunct\">,<\/span><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">n<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> in <strong data-start=\"1056\" data-end=\"1072\">sorted order<\/strong>, and their respective probabilities of access:<\/p>\n<ul data-start=\"1122\" data-end=\"1332\">\n<li data-start=\"1122\" data-end=\"1212\"><strong data-start=\"1124\" data-end=\"1148\">Search probabilities<\/strong>: <span class=\"katex\"><span class=\"katex-mathml\">p1,p2,&#8230;,pnp_1, p_2, &#8230;, p_n<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">p<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">1<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mpunct\">,<\/span><span class=\"mord\"><span class=\"mord mathnormal\">p<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mpunct\">,<\/span><span class=\"mord\">&#8230;<\/span><span class=\"mpunct\">,<\/span><span class=\"mord\"><span class=\"mord mathnormal\">p<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">n<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> (probability of searching each key)<\/li>\n<li data-start=\"1213\" data-end=\"1332\"><strong data-start=\"1215\" data-end=\"1244\">Dummy keys&#8217; probabilities<\/strong>: <span class=\"katex\"><span class=\"katex-mathml\">q0,q1,&#8230;,qnq_0, q_1, &#8230;, q_n<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">0<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mpunct\">,<\/span><span class=\"mord\"><span class=\"mord mathnormal\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">1<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mpunct\">,<\/span><span class=\"mord\">&#8230;<\/span><span class=\"mpunct\">,<\/span><span class=\"mord\"><span class=\"mord mathnormal\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">n<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> (probability of searching between keys or missing elements)<\/li>\n<\/ul>\n<p data-start=\"1334\" data-end=\"1430\">The goal is to construct a <strong data-start=\"1361\" data-end=\"1383\">binary search tree<\/strong> that minimizes the <strong data-start=\"1403\" data-end=\"1427\">expected search cost<\/strong>:<\/p>\n<p><span class=\"katex-display\"><span class=\"katex\"><span class=\"katex-mathml\">C(T)=\u2211i=1n(Depth(Ki)\u00d7Probability(Ki))C(T) = \\sum_{i=1}^{n} (Depth(K_i) \\times Probability(K_i))<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">C<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">T<\/span><span class=\"mclose\">)<\/span><span class=\"mrel\">=<\/span><\/span><span class=\"base\"><span class=\"mop op-limits\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">i<\/span><span class=\"mrel mtight\">=<\/span>1<\/span><\/span><span class=\"mop op-symbol large-op\">\u2211<\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">n<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">De<\/span><span class=\"mord mathnormal\">pt<\/span><span class=\"mord mathnormal\">h<\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">i<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><span class=\"mbin\">\u00d7<\/span><\/span><span class=\"base\"><span class=\"mord mathnormal\">P<\/span><span class=\"mord mathnormal\">ro<\/span><span class=\"mord mathnormal\">babi<\/span><span class=\"mord mathnormal\">l<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mord mathnormal\">t<\/span><span class=\"mord mathnormal\">y<\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">i<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">))<\/span><\/span><\/span><\/span><\/span><\/p>\n<p data-start=\"1498\" data-end=\"1564\">where <strong data-start=\"1504\" data-end=\"1518\">Depth(K_i)<\/strong> is the level of node <span class=\"katex\"><span class=\"katex-mathml\">KiK_i<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">i<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> in the tree.<\/p>\n<h3 data-start=\"1571\" data-end=\"1621\"><strong data-start=\"1575\" data-end=\"1619\">4. Dynamic Programming Approach for OBST<\/strong><\/h3>\n<p data-start=\"1623\" data-end=\"1635\">We define:<\/p>\n<ul data-start=\"1636\" data-end=\"1891\">\n<li data-start=\"1636\" data-end=\"1735\"><strong data-start=\"1638\" data-end=\"1655\"><span class=\"katex\"><span class=\"katex-mathml\">e[i][j]e[i][j]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span><\/strong> \u2192 Expected search cost for subtree containing keys <strong data-start=\"1707\" data-end=\"1733\"><span class=\"katex\"><span class=\"katex-mathml\">KiK_i<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">i<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> to <span class=\"katex\"><span class=\"katex-mathml\">KjK_j<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">j<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/strong><\/li>\n<li data-start=\"1736\" data-end=\"1816\"><strong data-start=\"1738\" data-end=\"1755\"><span class=\"katex\"><span class=\"katex-mathml\">w[i][j]w[i][j]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span><\/strong> \u2192 Sum of all probabilities from <strong data-start=\"1788\" data-end=\"1814\"><span class=\"katex\"><span class=\"katex-mathml\">KiK_i<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">i<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> to <span class=\"katex\"><span class=\"katex-mathml\">KjK_j<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">j<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/strong><\/li>\n<li data-start=\"1817\" data-end=\"1891\"><strong data-start=\"1819\" data-end=\"1839\"><span class=\"katex\"><span class=\"katex-mathml\">root[i][j]root[i][j]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">roo<\/span><span class=\"mord mathnormal\">t<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span><\/strong> \u2192 Root of the OBST for <strong data-start=\"1863\" data-end=\"1889\"><span class=\"katex\"><span class=\"katex-mathml\">KiK_i<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">i<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> to <span class=\"katex\"><span class=\"katex-mathml\">KjK_j<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">K<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">j<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/strong><\/li>\n<\/ul>\n<h4 data-start=\"1893\" data-end=\"1924\"><strong data-start=\"1898\" data-end=\"1922\">Recurrence Relation:<\/strong><\/h4>\n<p><span class=\"katex-display\"><span class=\"katex\"><span class=\"katex-mathml\">e[i][j]=min\u2061r\u2208[i,j](e[i][r\u22121]+e[r+1][j]+w[i][j])e[i][j] = \\min_{r \\in [i,j]} (e[i][r-1] + e[r+1][j] + w[i][j])<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><span class=\"mrel\">=<\/span><\/span><span class=\"base\"><span class=\"mop op-limits\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">r<\/span><span class=\"mrel mtight\">\u2208<\/span><span class=\"mopen mtight\">[<\/span><span class=\"mord mathnormal mtight\">i<\/span><span class=\"mpunct mtight\">,<\/span><span class=\"mord mathnormal mtight\">j<\/span><span class=\"mclose mtight\">]<\/span><\/span><\/span><span class=\"mop\">min<\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">r<\/span><span class=\"mbin\">\u2212<\/span><\/span><span class=\"base\"><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">r<\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">])<\/span><\/span><\/span><\/span><\/span><\/p>\n<p data-start=\"1994\" data-end=\"2053\">where <strong data-start=\"2000\" data-end=\"2011\"><span class=\"katex\"><span class=\"katex-mathml\">rr<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">r<\/span><\/span><\/span><\/span><\/strong> is the root node considered at that step.<\/p>\n<h3 data-start=\"2060\" data-end=\"2090\"><strong data-start=\"2064\" data-end=\"2088\">5. Practical Example<\/strong><\/h3>\n<h4 data-start=\"2092\" data-end=\"2114\"><strong data-start=\"2097\" data-end=\"2112\">Given Data:<\/strong><\/h4>\n<p data-start=\"2115\" data-end=\"2169\">Keys: <strong data-start=\"2121\" data-end=\"2135\">K1, K2, K3<\/strong><br data-start=\"2135\" data-end=\"2138\" \/>Sorted Keys: <strong data-start=\"2151\" data-end=\"2167\">(10, 20, 30)<\/strong><\/p>\n<table data-start=\"2171\" data-end=\"2318\">\n<thead data-start=\"2171\" data-end=\"2210\">\n<tr data-start=\"2171\" data-end=\"2210\">\n<th data-start=\"2171\" data-end=\"2177\">Key<\/th>\n<th data-start=\"2177\" data-end=\"2187\">K1 (10)<\/th>\n<th data-start=\"2187\" data-end=\"2197\">K2 (20)<\/th>\n<th data-start=\"2197\" data-end=\"2210\">K3 (30)<\/th>\n<\/tr>\n<\/thead>\n<tbody data-start=\"2231\" data-end=\"2318\">\n<tr data-start=\"2231\" data-end=\"2274\">\n<td>Probability <span class=\"katex\"><span class=\"katex-mathml\">pp<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">p<\/span><\/span><\/span><\/span><\/td>\n<td>0.3<\/td>\n<td>0.4<\/td>\n<td>0.3<\/td>\n<\/tr>\n<tr data-start=\"2275\" data-end=\"2318\">\n<td>Dummy <span class=\"katex\"><span class=\"katex-mathml\">qq<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">q<\/span><\/span><\/span><\/span><\/td>\n<td>0.1<\/td>\n<td>0.1<\/td>\n<td>0.1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h4 data-start=\"2325\" data-end=\"2379\"><strong data-start=\"2330\" data-end=\"2377\">Step 1: Compute Weight Matrix <span class=\"katex\"><span class=\"katex-mathml\">w[i][j]w[i][j]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span><\/strong><\/h4>\n<p><span class=\"katex-display\"><span class=\"katex\"><span class=\"katex-mathml\">w[i][j]=pi+pi+1+&#8230;+pj+qi\u22121+qjw[i][j] = p_i + p_{i+1} + &#8230; + p_j + q_{i-1} + q_j<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><span class=\"mrel\">=<\/span><\/span><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">p<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">i<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">p<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">i<\/span><span class=\"mbin mtight\">+<\/span>1<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord\">&#8230;<\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">p<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">j<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">i<\/span><span class=\"mbin mtight\">\u2212<\/span>1<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord\"><span class=\"mord mathnormal\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\"><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">j<\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n<table data-start=\"2440\" data-end=\"2705\">\n<thead data-start=\"2440\" data-end=\"2501\">\n<tr data-start=\"2440\" data-end=\"2501\">\n<th data-start=\"2440\" data-end=\"2452\"><strong data-start=\"2442\" data-end=\"2451\">i \u2192 j<\/strong><\/th>\n<th data-start=\"2452\" data-end=\"2466\"><strong data-start=\"2454\" data-end=\"2465\">w[i][i]<\/strong><\/th>\n<th data-start=\"2466\" data-end=\"2482\"><strong data-start=\"2468\" data-end=\"2481\">w[i][i+1]<\/strong><\/th>\n<th data-start=\"2482\" data-end=\"2501\"><strong data-start=\"2484\" data-end=\"2497\">w[i][i+2]<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody data-start=\"2562\" data-end=\"2705\">\n<tr data-start=\"2562\" data-end=\"2631\">\n<td><span class=\"katex\"><span class=\"katex-mathml\">w[1][1]w[1][1]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.4<\/td>\n<td><span class=\"katex\"><span class=\"katex-mathml\">w[1][2]w[1][2]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">2<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.9<\/td>\n<td><span class=\"katex\"><span class=\"katex-mathml\">w[1][3]w[1][3]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">3<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 1.3<\/td>\n<td><\/td>\n<\/tr>\n<tr data-start=\"2632\" data-end=\"2679\">\n<td><span class=\"katex\"><span class=\"katex-mathml\">w[2][2]w[2][2]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">2<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">2<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.5<\/td>\n<td><span class=\"katex\"><span class=\"katex-mathml\">w[2][3]w[2][3]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">2<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">3<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.9<\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr data-start=\"2680\" data-end=\"2705\">\n<td><span class=\"katex\"><span class=\"katex-mathml\">w[3][3]w[3][3]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">3<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">3<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h4 data-start=\"2712\" data-end=\"2766\"><strong data-start=\"2717\" data-end=\"2764\">Step 2: Compute Expected Cost <span class=\"katex\"><span class=\"katex-mathml\">e[i][j]e[i][j]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span><\/strong><\/h4>\n<p data-start=\"2768\" data-end=\"2780\">Base Case:<\/p>\n<p><span class=\"katex-display\"><span class=\"katex\"><span class=\"katex-mathml\">e[i][i]=w[i][i]e[i][i] = w[i][i]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mrel\">=<\/span><\/span><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span><\/span><\/p>\n<p data-start=\"2806\" data-end=\"2866\">For multiple elements, choose <span class=\"katex\"><span class=\"katex-mathml\">rr<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">r<\/span><\/span><\/span><\/span> (root) that minimizes:<\/p>\n<p><span class=\"katex-display\"><span class=\"katex\"><span class=\"katex-mathml\">e[i][j]=e[i][r\u22121]+e[r+1][j]+w[i][j]e[i][j] = e[i][r-1] + e[r+1][j] + w[i][j]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><span class=\"mrel\">=<\/span><\/span><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">r<\/span><span class=\"mbin\">\u2212<\/span><\/span><span class=\"base\"><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">r<\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><span class=\"mbin\">+<\/span><\/span><span class=\"base\"><span class=\"mord mathnormal\">w<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">i<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord mathnormal\">j<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span><\/span><\/p>\n<table data-start=\"2917\" data-end=\"3218\">\n<thead data-start=\"2917\" data-end=\"2978\">\n<tr data-start=\"2917\" data-end=\"2978\">\n<th data-start=\"2917\" data-end=\"2929\"><strong data-start=\"2919\" data-end=\"2928\">i \u2192 j<\/strong><\/th>\n<th data-start=\"2929\" data-end=\"2943\"><strong data-start=\"2931\" data-end=\"2942\">e[i][i]<\/strong><\/th>\n<th data-start=\"2943\" data-end=\"2959\"><strong data-start=\"2945\" data-end=\"2958\">e[i][i+1]<\/strong><\/th>\n<th data-start=\"2959\" data-end=\"2978\"><strong data-start=\"2961\" data-end=\"2974\">e[i][i+2]<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody data-start=\"3039\" data-end=\"3218\">\n<tr data-start=\"3039\" data-end=\"3132\">\n<td><span class=\"katex\"><span class=\"katex-mathml\">e[1][1]e[1][1]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.4<\/td>\n<td><span class=\"katex\"><span class=\"katex-mathml\">e[1][2]e[1][2]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">2<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.9 (root = K1)<\/td>\n<td><span class=\"katex\"><span class=\"katex-mathml\">e[1][3]e[1][3]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">3<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 1.3 (root = K2)<\/td>\n<td><\/td>\n<\/tr>\n<tr data-start=\"3133\" data-end=\"3192\">\n<td><span class=\"katex\"><span class=\"katex-mathml\">e[2][2]e[2][2]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">2<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">2<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.5<\/td>\n<td><span class=\"katex\"><span class=\"katex-mathml\">e[2][3]e[2][3]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">2<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">3<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.9 (root = K2)<\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr data-start=\"3193\" data-end=\"3218\">\n<td><span class=\"katex\"><span class=\"katex-mathml\">e[3][3]e[3][3]<\/span><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"mord mathnormal\">e<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">3<\/span><span class=\"mclose\">]<\/span><span class=\"mopen\">[<\/span><span class=\"mord\">3<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span> = 0.4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h3 data-start=\"3225\" data-end=\"3264\"><strong data-start=\"3229\" data-end=\"3264\">6. Constructing the Optimal BST<\/strong><\/h3>\n<p data-start=\"3265\" data-end=\"3282\">From the table:<\/p>\n<ul data-start=\"3283\" data-end=\"3416\">\n<li data-start=\"3283\" data-end=\"3345\"><strong data-start=\"3285\" data-end=\"3313\">K2 (20) becomes the root<\/strong> (it minimizes expected cost).<\/li>\n<li data-start=\"3346\" data-end=\"3380\"><strong data-start=\"3348\" data-end=\"3378\">K1 (10) is the left child.<\/strong><\/li>\n<li data-start=\"3381\" data-end=\"3416\"><strong data-start=\"3383\" data-end=\"3414\">K3 (30) is the right child.<\/strong><\/li>\n<\/ul>\n<p data-start=\"3418\" data-end=\"3452\">Final <strong data-start=\"3424\" data-end=\"3449\">Optimal BST Structure<\/strong>:<\/p>\n<div class=\"contain-inline-size rounded-md border-[0.5px] border-token-border-medium relative bg-token-sidebar-surface-primary dark:bg-gray-950\">\n<div class=\"flex items-center text-token-text-secondary px-4 py-2 text-xs font-sans justify-between rounded-t-[5px] h-9 bg-token-sidebar-surface-primary dark:bg-token-main-surface-secondary select-none\">markdown<\/div>\n<div class=\"sticky top-9 md:top-[5.75rem]\">\n<div class=\"absolute bottom-0 right-2 flex h-9 items-center\">\n<div class=\"flex items-center rounded bg-token-sidebar-surface-primary px-2 font-sans text-xs text-token-text-secondary dark:bg-token-main-surface-secondary\"><span class=\"\" data-state=\"closed\"><button class=\"flex gap-1 items-center select-none px-4 py-1\" aria-label=\"Copy\">Copy<\/button><\/span><span class=\"\" data-state=\"closed\"><button class=\"flex select-none items-center gap-1\">Edit<\/button><\/span><\/div>\n<\/div>\n<\/div>\n<div class=\"overflow-y-auto p-4\" dir=\"ltr\"><code class=\"!whitespace-pre\"><span class=\"hljs-code\">        20<br \/>\n\/   \\<br \/>\n10    30<br \/>\n<\/span><\/code><\/div>\n<\/div>\n<h3 data-start=\"3506\" data-end=\"3537\"><strong data-start=\"3510\" data-end=\"3537\">7. Applications of OBST<\/strong><\/h3>\n<p data-start=\"3538\" data-end=\"3742\">\u2714 <strong data-start=\"3540\" data-end=\"3561\">Database Indexing<\/strong> (e.g., indexing frequently accessed records efficiently).<br data-start=\"3619\" data-end=\"3622\" \/>\u2714 <strong data-start=\"3624\" data-end=\"3643\">Compiler Design<\/strong> (syntax trees in parsers).<br data-start=\"3670\" data-end=\"3673\" \/>\u2714 <strong data-start=\"3675\" data-end=\"3702\">Artificial Intelligence<\/strong> (decision trees in machine learning).<\/p>\n<h3 data-start=\"3749\" data-end=\"3772\"><strong data-start=\"3753\" data-end=\"3770\">8. Conclusion<\/strong><\/h3>\n<p data-start=\"3773\" data-end=\"4001\">The <strong data-start=\"3777\" data-end=\"3814\">Optimal Binary Search Tree (OBST)<\/strong> ensures efficient searching by minimizing the expected search cost using <strong data-start=\"3888\" data-end=\"3911\">dynamic programming<\/strong>. This is especially useful in applications where search frequencies vary significantly.<\/p>\n<p data-start=\"4003\" data-end=\"4073\" data-is-last-node=\"\" data-is-only-node=\"\">Would you like a <strong data-start=\"4020\" data-end=\"4043\">code implementation<\/strong> of OBST in <strong data-start=\"4055\" data-end=\"4069\">C++\/Python<\/strong>?<\/p>\n<h3 data-start=\"4003\" data-end=\"4073\"><a href=\"https:\/\/epgp.inflibnet.ac.in\/epgpdata\/uploads\/epgp_content\/S000007CS\/P001064\/M017077\/ET\/1469091511Q1-etext-module29.pdf\" target=\"_blank\" rel=\"noopener\">AAD- Optimal Binary Search Tree With Practical Example ( for Deeper Understanding) Part 25.<\/a><\/h3>\n<h3 class=\"LC20lb MBeuO DKV0Md\"><a href=\"https:\/\/jmlr.org\/papers\/volume23\/20-520\/20-520.pdf\" target=\"_blank\" rel=\"noopener\">Optimal Decision Trees via Dynamic Programming and &#8230;<\/a><\/h3>\n<h3 class=\"LC20lb MBeuO DKV0Md\"><a href=\"https:\/\/community.wvu.edu\/~krsubramani\/courses\/fa16\/Aaoa\/lecnotes\/obst.pdf\" target=\"_blank\" rel=\"noopener\">Optimal binary search trees<\/a><\/h3>\n<h3 class=\"LC20lb MBeuO DKV0Md\"><a href=\"https:\/\/www.ksrmce.ac.in\/NAAC\/naac2020\/cri6\/DAA.pdf\" target=\"_blank\" rel=\"noopener\">Optimal Binary Search Tree<\/a><\/h3>\n<h3>\u2705 AAD \u2013 Optimal Binary Search Tree (OBST)<\/h3>\n<p><strong>Part 25: With Practical Example for Deeper Understanding<\/strong><br \/>\n<em>(AAD = Advanced Algorithm Design \u2013 relevant to GATE CSE\/IT)<\/em><\/p>\n<hr \/>\n<h2>\ud83d\udcd8 What is an Optimal Binary Search Tree?<\/h2>\n<p>An <strong>Optimal Binary Search Tree (OBST)<\/strong> is a <strong>binary search tree<\/strong> built from a set of <strong>sorted keys<\/strong>, such that:<\/p>\n<ul>\n<li><strong>Search cost is minimized<\/strong> based on the <strong>frequency\/probability<\/strong> of accessing each key.<\/li>\n<li>Frequently accessed keys are placed <strong>closer to the root<\/strong>.<\/li>\n<li>Used when <strong>search frequencies<\/strong> are known in advance (e.g., in compilers, symbol tables, etc.).<\/li>\n<\/ul>\n<hr \/>\n<h2>\ud83d\udd39 Why OBST?<\/h2>\n<p>In a normal BST, the structure depends only on the order of insertion.<br \/>\nBut in OBST, we want to <strong>minimize the weighted search time<\/strong>, i.e.:<\/p>\n<p><span class=\"katex\">Expected\u00a0Cost=\u2211i=1nfi\u22c5depth(ki)\\text{Expected Cost} = \\sum_{i=1}^{n} f_i \\cdot \\text{depth}(k_i)<\/span><\/p>\n<p>Where:<\/p>\n<ul>\n<li><span class=\"katex\">fif_i<\/span> = frequency of accessing key <span class=\"katex\">kik_i<\/span><\/li>\n<\/ul>\n<hr \/>\n<h2>\ud83e\udde0 Problem Statement<\/h2>\n<p>Given:<\/p>\n<ul>\n<li>A sorted list of keys <span class=\"katex\">K={k1,k2,&#8230;,kn}K = \\{k_1, k_2, &#8230;, k_n\\}<\/span><\/li>\n<li>Their corresponding <strong>search probabilities<\/strong> <span class=\"katex\">P={p1,p2,&#8230;,pn}P = \\{p_1, p_2, &#8230;, p_n\\}<\/span><\/li>\n<li>And <strong>dummy keys (for unsuccessful searches)<\/strong> with probabilities <span class=\"katex\">Q={q0,q1,&#8230;,qn}Q = \\{q_0, q_1, &#8230;, q_n\\}<\/span><\/li>\n<\/ul>\n<p>Construct an OBST that minimizes the <strong>expected cost of searching<\/strong>.<\/p>\n<hr \/>\n<h2>\ud83d\udd27 Dynamic Programming Solution<\/h2>\n<p>We build two tables:<\/p>\n<ul>\n<li><strong>Cost[i][j]<\/strong>: Minimum cost of a BST that can be formed from <span class=\"katex\">kik_i<\/span> to <span class=\"katex\">kjk_j<\/span><\/li>\n<li><strong>Root[i][j]<\/strong>: Root of the subtree containing <span class=\"katex\">kik_i<\/span> to <span class=\"katex\">kjk_j<\/span><\/li>\n<\/ul>\n<hr \/>\n<h2>\u2705 Practical Example<\/h2>\n<p>Let&#8217;s say we have 3 keys:<\/p>\n<table>\n<thead>\n<tr>\n<th>Key<\/th>\n<th>Probability (p)<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>A (k\u2081)<\/td>\n<td>0.15<\/td>\n<\/tr>\n<tr>\n<td>B (k\u2082)<\/td>\n<td>0.10<\/td>\n<\/tr>\n<tr>\n<td>C (k\u2083)<\/td>\n<td>0.05<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Dummy keys: <span class=\"katex\">q0=0.05,q1=0.10,q2=0.05,q3=0.05q_0 = 0.05, q_1 = 0.10, q_2 = 0.05, q_3 = 0.05<\/span><\/p>\n<h3>Step 1: Initialize Tables<\/h3>\n<p>We use 0-based indexing for cost and root tables:<\/p>\n<ul>\n<li><strong>Cost[i][j]<\/strong> for i &gt; j = <span class=\"katex\">qiq_i<\/span> (base case)<\/li>\n<li>Start filling lengths from 1 to n (bottom-up DP)<\/li>\n<\/ul>\n<hr \/>\n<h3>Step 2: Fill Cost and Root Tables<\/h3>\n<p>We use the recurrence:<\/p>\n<p><span class=\"katex\">Cost[i][j]=min\u2061r=ij{Cost[i][r\u22121]+Cost[r+1][j]+W(i,j)}Cost[i][j] = \\min_{r=i}^{j} \\{ Cost[i][r-1] + Cost[r+1][j] + W(i,j) \\}<\/span><\/p>\n<p>Where:<\/p>\n<p><span class=\"katex\">W(i,j)=\u2211l=ijpl+\u2211l=i\u22121jqlW(i, j) = \\sum_{l=i}^{j} p_l + \\sum_{l=i-1}^{j} q_l<\/span><\/p>\n<p>This is the <strong>total weight (probability mass)<\/strong> from i to j.<\/p>\n<hr \/>\n<h3>Step 3: Final Result<\/h3>\n<p>After filling the DP tables, the value <strong>Cost[1][n]<\/strong> gives the <strong>minimum search cost<\/strong>, and you can reconstruct the tree using the <strong>Root[i][j]<\/strong> table.<\/p>\n<hr \/>\n<h2>\ud83c\udf33 OBST Tree Construction (Visual Representation)<\/h2>\n<p>For this example, the <strong>optimal root<\/strong> may be key B, with A as left child and C as right child \u2014 this gives the <strong>lowest weighted cost<\/strong>.<\/p>\n<pre><code>        B\n       \/ \\\n      A   C\n<\/code><\/pre>\n<hr \/>\n<h2>\ud83d\udd0d Real-world Use Case<\/h2>\n<ul>\n<li><strong>Compilers\/Symbol Tables<\/strong> \u2013 frequently accessed variables or function names are accessed quickly.<\/li>\n<li><strong>Database Indexing<\/strong> \u2013 when access pattern is known, OBST gives faster search than regular BST.<\/li>\n<li><strong>Predictive text\/input systems<\/strong> \u2013 keys with higher selection probability are placed closer to root.<\/li>\n<\/ul>\n<hr \/>\n<h2>\ud83d\udca1 Key Takeaways<\/h2>\n<table>\n<thead>\n<tr>\n<th>Concept<\/th>\n<th>Summary<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>OBST<\/td>\n<td>BST optimized for search cost<\/td>\n<\/tr>\n<tr>\n<td>Goal<\/td>\n<td>Minimize expected search time<\/td>\n<\/tr>\n<tr>\n<td>Approach<\/td>\n<td>Dynamic Programming<\/td>\n<\/tr>\n<tr>\n<td>Time Complexity<\/td>\n<td><span class=\"katex\">O(n3)O(n^3)<\/span>, can be optimized to <span class=\"katex\">O(n2)O(n^2)<\/span><\/td>\n<\/tr>\n<tr>\n<td>Application<\/td>\n<td>Databases, Compilers, AI trees<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<hr \/>\n<p>Would you like a <strong>step-by-step Python implementation<\/strong> of OBST with this example or want to try a <strong>GATE-style question<\/strong>?<\/p>\n<h3><a href=\"https:\/\/publikationen.sulb.uni-saarland.de\/bitstream\/20.500.11880\/26727\/1\/thesis_kozma.pdf\" target=\"_blank\" rel=\"noopener\">AAD- Optimal Binary Search Tree With Practical Example ( for Deeper Understanding) Part 25.<\/a><\/h3>\n<h3 class=\"LC20lb MBeuO DKV0Md\"><a href=\"https:\/\/sites.cs.ucsb.edu\/~suri\/cs130b\/optBST.pdf\" target=\"_blank\" rel=\"noopener\">Optimal Binary Search Trees<\/a><\/h3>\n","protected":false},"excerpt":{"rendered":"<p>AAD- Optimal Binary Search Tree With Practical Example ( for Deeper Understanding) Part 25. [fvplayer id=&#8221;120&#8243;] Optimal Binary Search Tree (OBST) \u2013 Advanced Analysis &amp; Practical Example 1. Introduction to Optimal Binary Search Tree (OBST) An Optimal Binary Search Tree (OBST) is a specialized Binary Search Tree (BST) that is structured in a way that [&hellip;]<\/p>\n","protected":false},"author":71,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-2802","post","type-post","status-publish","format-standard","hentry","category-algorithm-analysis-and-design"],"_links":{"self":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts\/2802","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/users\/71"}],"replies":[{"embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/comments?post=2802"}],"version-history":[{"count":0,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts\/2802\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/media?parent=2802"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/categories?post=2802"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/tags?post=2802"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}