分类：伸展树

2017
10-03

Java数据结构与算法解析——伸展树

伸展树简介伸展树(SplayTree)是特殊的二叉查找树。它的特殊是指，它除了本身是棵二叉查找树之外，它还具备一个特点:当某个节点被访问时，伸展树会通过旋转使该节点成为树根。这样做的好处是，下次要访问该节点时，能够迅速的访问到该节点。特性1.和普通的二叉查找树相比，具有任何情况下、任何操作的平摊O(log2n)的复杂度，时间性能上更好2.和一般的平衡二叉树比如红黑树、AVL树相比，维护更少的节点额... 继续阅读 >