If we have a binary tree, how do we determine if a key is in the tree?\u00c2\u00a0Or another way, how do we know it was inserted correctly? We need to\u00c2\u00a0visit every node.<\/p>\n
This is a recursive problem and hard to do in gdb. The\u00c2\u00a0convenience<\/span> variables are very simple and we can not implement a stack with them.\u00c2\u00a0Since they are effectively global, we can not even hide them in\u00c2\u00a0stack frames. What we can do is use concatenation and a node-id\u00c2\u00a0to generate uniqe names.<\/p>\n Note that you have to do all variable name declarations before\u00c2\u00a0you do any recursion. That statement will make sense when you\u00c2\u00a0violate it and wonder why your output looks strange.<\/p>\n Contrast that against a very simple algorithm to find if the\u00c2\u00a0key is in the tree (with the assumption the tree is valid).<\/p>\n Recursion is not needed as we lop of a branch with each\u00c2\u00a0iteration.<\/p>\n If we have a binary tree, how do we determine if a key is in the tree?\u00c2\u00a0Or another way, how do we know it was inserted...<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18],"tags":[],"class_list":["post-80","post","type-post","status-publish","format-standard","hentry","category-tricks"],"_links":{"self":[{"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=\/wp\/v2\/posts\/80","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=80"}],"version-history":[{"count":7,"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=\/wp\/v2\/posts\/80\/revisions"}],"predecessor-version":[{"id":380,"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=\/wp\/v2\/posts\/80\/revisions\/380"}],"wp:attachment":[{"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=80"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=80"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blogs.tulsalabs.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=80"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}define indentby\r\n printf \"%*c\", $arg0+1, 0\r\nend\r\n\r\ndefine walk_btree\r\n set $node_$arg0 = ($arg1)\r\n set $fnum_$arg0 = ($arg2)\r\n set $branch_$arg0 = ($arg3)\r\n set $space_$arg0 = ($arg4)\r\n set $leftid_$arg0 = $arg0 + 1\r\n set $rightid_$arg0 = $arg0 + 2\r\n\r\n indentby $space_$arg0\r\n printf \"%d %u (btree *)%p\\n\", $branch_$arg0, $node_$arg0->e_type[$fnum_$arg0].key, $node_$arg0\r\n\r\n set $space_$arg0 = $space_$arg0 + 1\r\n if $node_$arg0->e_type[$fnum_$arg0].left\r\n walk_btree $leftid_$arg0 $node_$arg0->e_type[$fnum_$arg0].left $fnum_$arg0 0 $space_$arg0\r\n end\r\n if $node_$arg0->e_type[$fnum_$arg0].right\r\n walk_btree $rightid_$arg0 $node_$arg0->e_type[$fnum_$arg0].right $fnum_$arg0 1 $space_$arg0\r\n end\r\nend\r\ndocument walk_btree\r\n NODE-ID NODE FNUM BRANCH INDENTBY\r\n Recursively walk the binary tree printing out the key for the fnum'ed entry\r\nend\r\n\r\ndefine start_walk_btree\r\n walk_btree 0 $arg0 $arg1 3 1\r\nend\r\ndocument start_walk_btree\r\n NODE FNUM\r\n Recursively walk the binary tree printing out the key for the fnum'ed entry\r\nend<\/pre>\n
define find_btree\r\n set $node = $arg0\r\n set $fnum = $arg1\r\n set $key = $arg2\r\n set $process = 1\r\n\r\n while $node && $process\r\n if $key == $node->e_type[$fnum].key\r\n set $process = 0\r\n else\r\n\r\n if $key < $node->e_type[$fnum].key\r\n $node = $node->e_type[$fnum].left\r\n else\r\n $node = $node->e_type[$fnum].right\r\n end\r\n end\r\n end\r\n\r\n if $node\r\n printf \"Found match on (btree *)%p\\n\", $node\r\n else\r\n printf \"No matching node in the binary tree\\n\"\r\n end\r\nend<\/pre>\n","protected":false},"excerpt":{"rendered":"