关于数据结构中的一些Tree

最近涉及到了平衡树相关的内容,觉得自己之前零零散散的看了很多东西,隐约觉得这些算法不应该是这么零碎的感觉,所以尝试着整理一下……

从二叉树开始讲起
作为搜索的结构化结果

B树

在正式说平衡树之前,先说一下B树,从而引出后面的2-3-4树

红黑树

平衡树的一个重要实现方式,由于相较于AVL树存储信息更少(可以通过一些trick一样?)所以在工业界中大量使用,std的map,set,Linux的进程调度等。
红黑树要求:

  • 每个节点是红色的,或是黑色的
  • 根节点是黑色的
  • 每个叶子节点是黑色的
  • 如果一个节点是红色的,则它的两个子节点都是黑色的
  • 对每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点

红黑树的平衡由下面的引理来保证:

  • 一颗有n个内部节点的红黑树的高度至多为
  • 证明:首先证明以任一节点x为根的子树中至少包含 个内部节点(递推)。然后即有 , 整理即

AVL树

Treap

非旋转Treap&持久化Treap

可持久化Treap与Treap的区别在于哪里?
维持平衡的方式用Split和Merge,而Treap使用rotate
Other:可以分裂(Split)和合并(Merge)

主席树

函数式(可持久化)线段树

笛卡尔树

建树很快,后续用Treap操作插入
每个节点有2个关键字key、value。从key的角度看,这是一颗二叉搜索树,每个节点的左子树的key都比它小,右子树都比它大;从value的角度看,这是一个堆。

题意:以字符串为关键字key,数字为关键字value,构造一个二叉搜索大堆,最后按要求中序遍历 笛卡尔树的构造。

建立笛卡尔树的O(n)的算法:

  从别人博客里拷贝过来的,这里给出链接:http://hi.baidu.com/yy17yy/item/cd4edcf963944f6a3d148553

  首先按key关键字进行排序,这样建树的时候从左下角往右下角建。根据定义可知,每个数组的末尾节点必是位于树的最右路上且不可能有右孩子。 在建立树的过程中每次加入一个元素A[X],则该节点一定位于此时的树的最右路上且无右孩子。所以只要沿着A[X-1]节点向上走, 找到比A[X]大的第一个节点A[K],则A[X]是A[K]的右孩子,且A[K]原来的右孩子此时将成为A[X]的左孩子。 若找不到A[K]则此时的树的根将作为A[X]的左孩子,A[X]将成为树的新的根节点。

R树(区域树)

实际上应该称作Rectangle Tree,而不是Region Tree

线段树

区间树

基数树

左偏树

斜堆

Top Tree

划分树

势能分析