伸展树(splay tree)的可视化

参考书籍 《[数据结构与算法分析_Java语言描述(第2版)].韦斯》code on github

按照书里面的方法，伸展树里面不能像AVL那样直接在某个节点上旋转，而必须考虑父节点和祖父节点。 所以这就加大了实现难度，如果我们不存储某个节点的父节点和祖父节点的话，那么必须在遍历的时候 找到孙子节点（这样当前节点就是祖父节点，下一个节点就是父节点）。

另外伸展树需要区分对待zig-zag和zig-zig的情况，这点书里面给了具体的示例

Pasted-Image-20231225104522.png

书里面给了一个具体示例，首先插入1-32所有数字并且确保都在左子树上（所以插入顺序必须是逆序）。 然后分别遍历1-7这些数字观察树的旋转情况。只要数字在树里面，那么每次访问数字最终都能到根节点上。 虽然我的代码跑这个结果和书里面的不太一样，但是我觉得我的更好(不过没有完整测试，可能还是有bug) 

def uplift_left(r, rl):
    r.left = rl.right
    rl.right = r
    return rl


def uplift_right(r, rr):
    r.right = rr.left
    rr.left = r
    return rr


def left_zig_zig(r, rl, rll):
    rl.left = rll.right
    r.left = rl.right
    rl.right = r
    rll.right = rl
    return rll


def left_zig_zag(r, rl, rll):
    rl.right = rll.left
    r.left = rll.right
    rll.left = rl
    rll.right = r
    return rll


def right_zig_zig(r, rr, rrr):
    rr.right = rrr.left
    r.right = rr.left
    rr.left = r
    rrr.left = rr
    return rrr


def right_zig_zag(r, rr, rrl):
    r.right = rrl.left
    rr.left = rrl.right
    rrl.left = r
    rrl.right = rr
    return rrl


def access_tree_node(r: TreeNode, val):
    if r is None or r.val == val:
        return r

    if val < r.val:
        rl = r.left

        if rl is None:
            return r

        elif val == rl.val:
            return uplift_left(r, rl)

        elif val < rl.val:
            rll = rl.left
            if rll is None:
                return uplift_left(r, rl)
            else:
                rll = rl.left = access_tree_node(rll, val)
                return left_zig_zig(r, rl, rll)

        else:
            rlr = rl.right
            if rlr is None:
                return uplift_left(r, rl)
            else:
                rlr = rl.right = access_tree_node(rlr, val)
                return left_zig_zag(r, rl, rlr)

    else:
        rr = r.right
        if rr is None:
            return r

        elif val == rr.val:
            return uplift_right(r, rr)

        elif val < rr.val:
            rrl = rr.left
            if rrl is None:
                return uplift_right(r, rr)
            else:
                rrl = rr.left = access_tree_node(rrl, val)
                return right_zig_zag(r, rr, rrl)

        else:
            rrr = rr.right
            if rrr is None:
                return uplift_right(r, rr)
            else:
                rrr = rr.right = access_tree_node(rrr, val)
                return right_zig_zig(r, rr, rrr)

    raise RuntimeError('unexpected condition')

为了能够很好地观察树的变化，最好能够以可视化的方式将树展示出来（最好是图片或者是动画，而不是字符）。 所以我编写了一个工具，可以将树输出成为.dot格式，然后使用graphviz输出成为图片。另外graphviz不支持 输出多个graph, 如果要将多个graph放在一个图片里面需要使用gvpack工具。具体代码可以看 tree_util.py.

驱动方式也很简单：

  1. 创建一个stream/stringio
  2. 调用 `tree_to_dot` 传入节点，graph名称和stream
  3. 最后将stream输出并且调用gvpack+graphviz产生图片。
def test_pprint_tree():
    root = None
    stream = StringIO()
    for val in range(32, 0, -1):
        root = insert_tree_node(root, TreeNode(val))
    for x in (1,2,3,4):
        root = access_tree_node(root, x)
        tree_to_dot(root, 'find {}'.format(x), stream)
    dot_to_graph('/tmp/example', stream.getvalue(), type='png')


test_pprint_tree()

Pasted-Image-20231225104910.png