Understanding Red-Black Tree Traversal of STL multiset in GDB

Question

I am trying to understand the RB-tree traversal in the following GDB script

define pset
    if $argc == 0
        help 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> to see the elements in the 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 to understand the internals of the RB-tree but could't get it. These are my following doubts-

1. Is it iterative in-order traversal thats happening here?

2. How can $end = $tree._M_t._M_impl._M_header. I thought _M_header is the root node. If not which is the root node?

3. If its inorder traversal then why are we first going down the right sub-tree of the tree by doing if $node._M_right != 0 set $node = $node._M_right. Also, we are printing out the element right at the beginning of the while loop as we do in pre-order. But when I run this script in GDB, it does print the elements in sorted order which makes me speculate that its in-order.

4. When it comes to traversal, isn't an RB-tree the same as a normal BST? Cant an RB-tree traversed with just left and right pointers? Why is parent pointer being used here?

Answer 1

I think I figured it out.

All my above questions can be answered with one observation- "tree._M_t._M_impl._M_header is NOT the root node. It is a node that acts like a cache for the RB-tree. That is tree._M_t._M_impl._M_header._M_Left points to the leftmost node of the tree, tree._M_t._M_impl._M_header._M_Right points to the rightmost node and tree._M_t._M_impl._M_header._M_parent points to the root node of the tree.

Now, we can see how the given code is indeed doing an in-order traversal. The reason as to why normal BST traversal is not used here is to gain speed. By caching the leftmost node of the tree, things like iterator.begin() can be implemented in O(1) instead of O(h) where h is the height of the tree.