c++ - Understanding Red-Black Tree Traversal of STL multiset in GDB -


i trying understand rb-tree traversal in following gdb script

define pset     if $argc == 0         pset     else         set $tree = $arg0         set $i = 0         set $node = $tree._m_t._m_impl._m_header._m_left         set $end = $tree._m_t._m_impl._m_header         set $tree_size = $tree._m_t._m_impl._m_node_count         if $argc == 1             printf "set "             whatis $tree             printf "use pset <variable_name> <element_type> see elements in set.\n"         end         if $argc == 2             while $i < $tree_size                 set $value = (void *)($node + 1)                 printf "elem[%u]: ", $i                 p *($arg1*)$value                 if $node._m_right != 0                     set $node = $node._m_right                     while $node._m_left != 0                         set $node = $node._m_left                     end                 else                     set $tmp_node = $node._m_parent                     while $node == $tmp_node._m_right                         set $node = $tmp_node                         set $tmp_node = $tmp_node._m_parent                     end                     if $node._m_right != $tmp_node                         set $node = $tmp_node                     end                 end                 set $i++             end         end

i went through stl_tree.h understand internals of rb-tree could't it. these following doubts-

  1. is iterative in-order traversal thats happening here?

  2. how can $end = $tree._m_t._m_impl._m_header. thought _m_header root node. if not root node?

  3. if inorder traversal why first going down right sub-tree of tree doing if $node._m_right != 0 set $node = $node._m_right. also, printing out element right @ beginning of while loop in pre-order. when run script in gdb, print elements in sorted order makes me speculate in-order.

  4. when comes traversal, isn't rb-tree same normal bst? cant rb-tree traversed left , right pointers? why parent pointer being used here?

i think figured out.

all above questions can answered 1 observation- "tree._m_t._m_impl._m_header not root node. node acts cache rb-tree. tree._m_t._m_impl._m_header._m_left points leftmost node of tree, tree._m_t._m_impl._m_header._m_right points rightmost node , tree._m_t._m_impl._m_header._m_parent points root node of tree.

now, can see how given code indeed doing in-order traversal. reason why normal bst traversal not used here gain speed. caching leftmost node of tree, things iterator.begin() can implemented in o(1) instead of o(h) h height of tree.


-

Comments

Post a Comment

Popular posts from this blog

facebook - android ACTION_SEND to share with specific application only -

in android application have 4 buttons facebook , viber , telegram , whatsapp , want share different content based on each button. for example if user clicks on viber button want user action_send share content viber only. i found this explains how facebook , twitter seems it's calling specific class name of application don't know applications wanna use except facebook. all android apps have unique id, first have check if these apps installed in user's device , can pass unique id via intent sharing. according below: unique ids different apps : viber : com.viber.voip telegram : org.telegram.messenger whatsapp : com.whatsapp check if these apps installed , if installed send messages through intent. private void sendmessage(context context,string message, string appids) { final boolean isappinstalled =isappavailable(context, appids); if (isappinstalled) { intent myintent = new intent(intent.action_send); myintent.settype("text/p...
Read more

python - Creating a new virtualenv gives a permissions error -

i'm getting following output when running virtualenv newvenv . traceback (most recent call last): file "/usr/local/bin/virtualenv", line 5, in <module> pkg_resources import load_entry_point file "/usr/lib/python2.7/dist-packages/pkg_resources.py", line 2727, in <module> add_activation_listener(lambda dist: dist.activate()) file "/usr/lib/python2.7/dist-packages/pkg_resources.py", line 700, in subscribe callback(dist) file "/usr/lib/python2.7/dist-packages/pkg_resources.py", line 2727, in <lambda> add_activation_listener(lambda dist: dist.activate()) file "/usr/lib/python2.7/dist-packages/pkg_resources.py", line 2227, in activate self.insert_on(path) file "/usr/lib/python2.7/dist-packages/pkg_resources.py", line 2334, in insert_on self.check_version_conflict() file "/usr/lib/python2.7/dist-packages/pkg_resources.py", line 2373, in check_version_conflict...
Read more

javascript - cocos2d-js draw circle not instantly -

i wondering how draw circles (or other shapes also) not instantly. so far tried drawcircle(args...) in ccdrawnode.js , drawcircle(args...) in cc.drawingprimitivecanvas class, , draw circles popping out instantly on screen. what if want achieve effect circular progressive bar, completes circle based on percentage of initialization? or more generally, if want draw circle respect prolonged period? thinking there drawcircle function elapsed time argument fail find any. or have implement own? thanks suggestions, far out of ideas. i think have implement own. think can achieve update circle drawing on each time update() function called.
Read more