The Way 2 Inner Peace.

伸展树

在上一篇博文中提到的伸展树(splay tree).其实自己也没怎么明白.在网上找了半天也没有看懂.最终找到了这个.这是加州大学伯克利分校的CS 61B数据结构的一个公开课视频.讲的清楚极了.现部分整理如下.

一.伸展树是一种平衡二叉搜索树.它可以快速的获得最近操作的项目.对于伸展树.最基本的策略是旋转(Rotation).旋转分为左旋和右旋.如下:

二.伸展树的基本操作:

1.查找(K):和普通的二叉树没什么区别.然后让查找结束的节点X成为根(splay)(不管是否找到目标K.)

2.伸展(splay X):有三种情况.

  • Zig-zag:
    X是一个右节点的左节点.或者X是一个左节点的右节点.
    旋转X两次.
  • Zig-zig:
    X是一个左节点的左节点.或者X是一个右节点的右节点.
    旋转两次.但和Zig-zag的旋转顺序有差异.先旋转X的父节点.在旋转X.
  • Zig:
    X是根的子节点.
    那么就是一次旋转

   Zig-zag和Zig-zig都是对两层深度的操作.直到X成为根的子节点.就进行Zig操作.

下面是一个查找的例子.

首先.象普通的二叉搜索树一样.找到7.可见.7是一个右节点的右节点.那么就进行Zig-zig步骤.此时7是一个右节点的左节点.就进行Zig-zag步骤.再进行一个Zig步骤.一个查找7的操作就完成了.

3.插入(K):首先象普通的二叉搜索树一样将K插入.再将K伸展至根.

4.删除(K):象普通的二叉搜索树一样将K删除.然后将K的父节点X伸展至根.如果K没有在树内的话.那么就如同查找操作.即将最后一个访问的节点伸展至根.

 

这里有一个在线的示例:http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/SplayTree-Example.html

另一小段功能不全的测试代码..只能打印树的深度...(摊手)(摇头)

def inorder():
    d=dict()
    def inner_inorder(n,r):
        if n is None :
            return
        else:
            inner_inorder(n.left,r=r+1)
            if d.get(r) is None:
                d[r]=[n.key]
            else:
                d[r].append(n.key)
            inner_inorder(n.right,r=r+1)
    inner_inorder(t.root,0)
    return d

def print_tree():
    d=inorder()
    for i in d:
        print "%s"%d[i]

t=SplayTree()
for i in range(9):
    t.insert(i)

print_tree(t)

[scheme学习笔记]二叉树的遍历

 

将二叉树的节点定义为
(define-struct node (number value left right))
则树的定义数据定义是
binary-tree(简称BT)是下列两者之一
1. false;
2. (make-node num value lft rgt),
其中 num是数,value是符号,lft 和rgt 是BT。
 
 
则如图的二叉树可以表示为
(define BT1 (make-node 63 'a
                       (make-node 29 'b
                                  (make-node 15 'c
                                             (make-node 10 'd false false)
                                             (make-node 24 'e false false)) false)
                       (make-node 89 'f
                                  (make-node 77 'g false false)
                                  (make-node 95 'h false
                                             (make-node 99 'i false false)))))
(define BT2 (make-node 63 'a
                       (make-node 29 'b
                                  (make-node 15 'c
                                             (make-node 87 'd false false)
                                             (make-node 24 'e false false)) false)
                       (make-node 89 'f
                                  (make-node 33 'g false false)
                                  (make-node 95 'h false
                                             (make-node 99 'i false false)))))
 
如果从左到右读出这两棵树中的数.可以得到两个序列
其中数A是按照升序排列的.将有序排列的二叉树称为二叉搜索树.
接下来开发函数inorder.中序遍历.该函数读入一棵二叉树,返回树中所有number数组成的表。该表以
从左到右的顺序(上图顺序)列出这些数.
 
;;inorder:BT->list
(define (inorder BT)
  (cond
    ((boolean? BT) empty)
    (else
     (append
      (inorder (node-left BT))
      (list (node-ssn BT))
      (inorder (node-right BT))))))
中序遍历按照左根右的顺序进行历遍.即首先遍历左子树,然后访问根结点,最后遍历右子树.在遍历左,右子树时.仍然先遍历左子树,再访问根结点,最后遍历右子树
 
而前序遍历按照根左右的顺序进行遍历.
后续遍历按照左右根的顺序进行遍历.
同理即可得到前序遍历和后续遍历的函数.
(define (preorder BT)
  (cond
    ((boolean? BT) empty)
    (else
     (append
      (list(node-ssn BT))
      (preorder (node-left BT))
      (preorder (node-right BT))))))
(define (postorder BT)
  (cond
    ((boolean? BT) empty)
    (else
     (append
      (postorder (node-left BT))
      (postorder (node-right BT))
      (list(node-ssn BT))))))
 
可以发现对二叉搜索树来说.中序遍历返回的是有序排列的表.
 
 
 
ps.写个博客都要翻墙.蛋疼死啊..
ps2.用递归的函数写递归的数据结构真是太清晰了.感觉就是C语言写出来是个麻烦的东西.指针满天飞..