jlearning.cn

《数据结构与算法分析》(2)——树

  • 对于任意节点$n_i$,$n_i$的深度为从根到自身的惟一路径的长。
  • $n_i$的是从$n_i$到一片树叶的最长路径的长。
树的实现
  • 在数据结构种简历到个个儿子节点的连接会产生太多的空间浪费。
  • 将每个节点的所有儿子都放在树节点的链表中。
  • 每个节点都有一个指针指向儿子下一个兄弟
树的遍历及应用
  • 先序遍历——打印目录列表
  • 后序遍历——统计每个文件占用的磁盘空间

二叉树

实现
  • 类似双链表,一个节点就是关键字信息加上两个只想其他节点的指针
表达式树
  • 中序遍历
  • 构造过程(把后缀表达式转变成表达式树):
    • 一次一个符号读入表达式,如果是操作数就建立一个单节点数并将她的指针推入栈中;如果是操作符从栈中弹出指向两棵树T1和T2的那两个指针并形成一颗新的树,将这颗心书的指针压入栈中。

二叉查找树

  • 二叉树的平均深度是$O(logN)$
查找操作
  • 如果T种的关键字是X,那么就返回T,否则对树T的左子树或右子树进行递归调用。
  • 首先要对是否为空树进行测试,否则就可能在NULL指针上兜圈子。
  • 使得最不可能的情况安排在最后进行
最值查找
  • 递归实现
1
2
3
4
5
6
7
8
9
findMin(SearchTree T){
if(T==NULL)
return NULL;
else
if(T.left == NULL)
return T;
else
return findMin(T.left);
}
  • 非递归实现
1
2
3
4
5
6
findMax(SearchTree T){
if(T!=NULL)
while(T.right!=NULL)
T=T.right;
return T;
}
插入
  • 使用Find沿着树查找,找到就做一些更新,否则将X插入到遍历的路径上的最后一个点上。
  • 重复元的插入可以通过在节点记录中保留一个附加域,来指示发生的频率。
删除
  • 如果是一个树叶,立即删除。
  • 如果有一个儿子,节点可以在父节点调整指针,绕过该节点后删除。
  • 如果有两个儿子,用其右子树的最小的数据,代替该节点的数据,并递归的删除点。因为不可能有做儿子,所以可以按照上面一种情况处理。
  • 如果删除的次数不多,可以使用懒惰删除。仍留在书中,只做了被删除的记号。

AVL树

  • 每个节点左子树和右子树的高度最多差1
  • 不平衡情况分为四种:
    • LL
    • LR
    • RL
    • RR
  • 其中LL和RR使用单旋转
  • LR和RL使用双旋转

伸展树

  • 保证从空树开始任意连续M次对树的操作最多话费$O(MlogN)$时间。
  • 当M次操作的序列总是最坏情形运行时间为$O(MF(N))$时,我们就说它摊还运行时间为$O(F(N))$。
简单情形
  • 将在访问路径上的每一个节点和他们的父节点实施旋转。
  • 并没有明显地改变原先访问路径上其他节点的情况。
展开
  • 如果X的父节点是树根,旋转X和树根。
  • 否则将X与它的父亲(P)和祖父(G)执行AVL那样的双旋转。

树的遍历

  • 先序遍历——计算深度
  • 后序遍历——计算高度
  • 中序遍历——二叉查找树排序

B-树

阶为M的B-树的定义
  • 树的根或者是一片树叶,或者其儿子数在2到M之间。
  • 除根之外,所有非树叶节点的儿子数在$\lceil M/2 \rceil$ 到M之间
  • 所有的树叶都在相同的深度上
插入
  • 调整
  • 首先查找只有小于M个关键字的兄弟,编程复杂,但是空间浪费少。