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

Question

我试图理解以下 GDB script 中的 RB 树遍历

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 树的内部结构但无法理解。这些是我接下来的疑惑——

1. 这里发生的是迭代中序遍历吗？

2. 如何才能$end = $tree._M_t._M_impl._M_header .我以为_M_header是根节点。如果不是哪个是根节点？

3. 如果它是中序遍历那么为什么我们首先通过执行 if $node._M_right != 0 set $node = $node._M_right 向下遍历树的右子树？ .此外，我们在 while 循环的开头打印出元素，就像我们在预订时所做的那样。但是当我在 GDB 中运行这个脚本时，它确实按排序顺序打印元素，这让我推测它是有序的。

4. 说到遍历，RB 树不是和普通的 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 遍历的原因是为了提高速度。通过缓存树的最左边的节点，像 iterator.begin() 这样的事情可以在 O(1) 而不是 O(h) 中实现> 其中 h 是树的高度。