了解 GDB 中 STL 多重集的红黑树遍历

Question

我试图理解下面的RB树遍历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

我通过 stl_tree.h 了解 RB 树的内部结构，但无法理解。以下是我的疑惑-

这是迭代中序遍历吗？
怎么可能$end = $tree._M_t._M_impl._M_header。我以为 _M_header 是根节点。如果不是哪个是根节点？
如果它是中序遍历那么我们为什么要先通过做if $node._M_right != 0 set $node = $node._M_right沿着树的右子树向下。此外，我们在 while 循环的开头打印出元素，就像我们在预订时所做的那样。但是当我在 GDB 中运行这个脚本时，它确实按排序顺序打印元素，这让我推测它是有序的。
说到遍历，RB-tree不是和普通的BST一样吗？不能只用左右指针遍历 RB 树吗？为什么在这里使用父指针？

Answer 1

我想我明白了。

我上面的所有问题都可以用一个观察来回答- “tree._M_t._M_impl._M_header 不是根节点。它是一个充当 RB 树缓存的节点。即 tree._M_t._M_impl._M_header._M_Left 指向树的最左侧节点，tree._M_t._M_impl._M_header._M_Right 指向最右边的节点和 tree._M_t._M_impl._M_header._M_parent 指向树的根节点。

现在，我们可以看到给定的代码确实是如何进行中序遍历的。这里不使用正常的 BST 遍历的原因是为了提高速度。通过缓存树的最左边的节点，可以在 O(1) 中实现 iterator.begin() 而不是 O(h)，其中 h 是树的高度。

了解 GDB 中 STL 多重集的红黑树遍历

Understanding Red-Black Tree Traversal of STL multiset in GDB

c++

stl

gdb

red-black-tree