JAVA 算法——树
1、二叉搜索树
二叉搜索树需满足以下四个条件:
- 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 任意节点的左、右子树也分别为二叉查找树;
- 没有键值相等的节点。
2、什么是伸展树(Splay Tree)
假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法,在每次查找之后对树进行重构,把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。
3、AVL树
4、节点自平衡树(Size Balanced Tree,简称SBT)
right [T] : 结点 T 的右儿子
s [T] : 以T为根的子树的结点个数(大小))
性质(b) s[ left[t] ]≥s[right[ right[t] ] ], s[ left[ right[t] ] ]
即.每棵子树的大小不小于其兄弟的子树大小。(对于数组来实现树不熟悉的童鞋,请把s[ left [ left[ t ] ] ] 翻译为s[ t->left->left ] 同样的,s[ right [ left[t] ] ]翻译为s[ t->left->right ] )
5、Treap
Treap是用来排序(Sort)的一种数据结构(Data Structure)。reap是随机查找二叉平衡树。 Treap发音为tree+ Heap。顾名思义, Treap把 BST和 Heap结合了起来。它和 BST一样满足许多优美的性质,而引入堆目的就是为了维护平衡。 Treap在 BST的基础上,添加了一个修正值。在满足 BST性质的上,Treap节点的修正值还满足最小堆性质。最小堆性质可以被描述为每个子树根节点都小于等于其子节点。
(1) Treap的特点 :1. Treap简明易懂。Treap只有两种调整方式,左旋和右旋。而且即使没有严密的数学证明和分析,Treap的构造方法啊,平衡原理也是不难理解的。只要能够理解 BST和堆的思想,理解 Treap当然不在话下。
2. Treap易于编写。Treap只需维护一个满足堆序的修正值,修正值一经生成无需修改。相
比较其他各种平衡树, Treap拥有最少的调整方式,仅仅两种相互对称的旋转。所以 Treap当之无愧是最易于编码调试的一种平衡树。
3. Treap稳定性佳。Treap的平衡性虽不如 AVL,红黑树, SBT等平衡树,但是 Treap也不会退化,可以保证期望 O(logN)的深度。Treap的稳定性取决于随机数发生器。
4. Treap具有严密的数学证明。Treap期望 O(logN)的深度,是有严密的数学证明的。但这不是介绍的重点,大多略去。
5. Treap具有良好的实践效果。各种实际应用中, Treap的稳定性表现得相当出色,没有因为任何的构造出的数据而退化。于是在信息学竞赛中,不少选手习惯于使用 Treap,均取得了不俗的表现。
一棵treap是一棵修改了结点顺序的二叉查找树,如图,显示一个例子,通常树内的每个结点x都有一个关键字值key[x],另外,还要为结点分配priority[x],它是一个独立选取的随机数。
假设所有的优先级是不同的,所有的关键字也是不同的。treap的结点排列成让关键字遵循二叉查找树性质,并且优先级(有的地方也叫修正值,是一个随机数)遵循最小堆顺序性质:
1.如果left是u的左孩子,则key[left] < key[u].2.如果right是u的右孩子,则key[right] > key[u].
3.如果child是u的孩子,则priority[child] > priority[u].
4.如果priority[vi] < priority[vj].则vi相对于vj而言更接近根节点。
这两个性质的结合就是为什么这种树被称为“treap”的原因,因为它同时具有二叉查找树和堆的特征。(在关键字上它满足二叉排序树,在优先级上他满足小顶堆)。
用以下方式考虑treap会有帮助。假设插入关联关键字的结点x1,x2,...,xn到一棵treap内。结果的treap是将这些结点以它们的优先级(随机选取)的顺序插入一棵正常的二叉查找树形成的,亦即priority[xi] < priority[xj]表示xi在xj之前被插入。
在算法导论的12.4节中,其证明了随机构造的二叉查找树的期望高度为O(lgn),因而treap的期望高度亦是O(lgn)。
1.treap插入操作:
1.按照二叉树的插入方法,将结点插入到树中
2.根据堆的性质(我们这里为最小堆)和优先级的大小调整结点位置。
2.treap删除操作:
1.找到相应的结点
2.若该结点为叶子结点,则直接删除;
若该结点为只包含一个叶子结点的结点,则将其叶子结点赋值给它;
若该结点为其他情况下的节点,则进行相应的旋转,直到该结点为上述情况之一,然后进行删除。