数据结构基础14———非线性数据结构之自平衡二叉查找树之伸展树

伸展树(英语:Splay Tree)是一种能够自我平衡的二叉查找树,它能在均摊O(log n)的时间内完成基于伸展(Splay)操作的插入、查找、修改和删除操作。由丹尼尔·斯立特(Daniel Sleator)和罗伯特·塔扬在1985年发明的。

在伸展树上的一般操作都基于伸展操作:假设想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法,在每次查找之后对树进行调整,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。

场景:
继AVL树之后,我们给出了2-3树和红黑树。虽然红黑树将2-3树的实现变成了二叉查找树结构,但对于红黑树本身其实还是是引入新的信息表明红还是黑色,并不够纯粹。红红黑黑花里胡哨的,强迫症又犯了怎么办?我们希望要一个纯粹的二叉树
实现而不需要去管这些红黑颜色,不需要去保存额外的信息,有没有其他的方案呢?

伸展树的出发点是这样的:考虑到局部性原理(刚被访问的内容下次可能仍会被访问,查找次数多的内容可能下一次会被访问,也就是我们通常所说的"二八"法则),为了使整个查找时间更小,被查频率高的那些节点应当经常处于靠近树根的位置。这样,很容易得想到以下这个方案:每次查找节点之后对树进行重构,把被查找的节点搬移到树根,这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后,它均会通过旋转的方法把被访问节点旋转到树根的位置。

为了将当前被访问节点旋转到树根,我们通常将节点自底向上旋转,直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系(指中序遍历结果是全序的)情况下,所有基本操作的平摊复杂度仍为O(log n)(平摊复杂度,摊返分析见后面章节)

优点

1.伸展树的自我平衡使其拥有良好的性能,因为频繁访问的节点会被移动到更靠近根节点,进而获得更快的访问速度。

2.可靠的性能——它的平均效率不输于其他平衡树

3.存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息,相对于其他平衡树,内存占用要小。

缺点:
伸展树最显著的缺点是它有可能会变成一条链。例如,在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率,操作的实际时间效率可能很低。然而均摊的最坏情况是对数级的——O(log n)。

即使以“只读”方式(例如通过查找操作)访问伸展树,其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言,如果允许多个线程同时执行查找操作,则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用,尽管用于实现优先级队列的方式不多。

伸展(splay)

当一个节点x被访问过后,伸展操作会将x移动到根节点。为了进行伸展操作,我们会进行一系列的旋转,每次旋转会使x离根节点更近。通过每次访问节点后的伸展操作,最近访问的节点都会离根节点更近,且伸展树也会大致平衡,这样我们就可以得到期望均摊时间复杂度的下界——均摊O(log n)。

每次旋转操作由三个因素决定:

x是其父节点p的左儿子还是右儿子;
p是否为根;
p是其父节点g(x的祖父节点)的左儿子还是右儿子。
在每次旋转操作后,设置g的儿子为x是很重要的。如果g为空,那么x显然就是根节点了。

共有三种旋转操作,每种都有左旋(Zig)和右旋(Zag)两种情况。为了简单起见,对每种旋转操作只展示一种情况(因为是对称的,程序上是6种但是逻辑上是3种)。这些旋转操作是:

Zig:当p为根节点时进行。Zig通常只在伸展操作的最后一步进行。
(单旋转)


Zig-zig和Zag-zag:当p不为根节点且x和p都为左儿子或都为右儿子时进行。下图为x和p都为左儿子时的情况(即Zig-zig),需先将p右旋到g的位置,再将x右旋到p的位置。
(一字型旋转)

Zig-zag和Zag-zig:当p不为根节点且x为左儿子而p为右儿子时进行,反之亦然。下图为前述情况(即Zig-zag),需先将x左旋到p到的位置,再将x右旋到g的位置。
(之字形旋转)

连接(join)

给出两棵树S和T,且S的所有元素都比T的元素要小。下面的步骤可以把它们连接成一棵树:

伸展S中最大的节点。现在这个节点变为S的根节点,且没有右儿子。
令T的根节点变为其右儿子。

分割(split)

给出一棵树和一个元素x,返回两棵树:一棵中所有的元素均小于等于x,另一棵中所有的元素大于x。下面的步骤可以完成这个操作:

伸展x。这样的话x成为了这棵树的根所以它的左子树包含了所有比x小的元素,右子树包含了所有比x大的元素。
把x的右子树从树中分割出来。

插入(insert)

插入操作是一个比较复杂的过程,具体步骤如下: 我们假定要插入的值为k。

如果当前树为空,则直接插入根。

如果当前节点的权值等于k则增加当前节点的大小并更新节点和父亲的信息,将当前节点进行splay操作。

否则按照二叉查找树的性质

public class SplayTree<T extends Comparable<T>> {

	private SplayTreeNode<T> mRoot; // 根结点

	public class SplayTreeNode<T extends Comparable<T>> {
		T key; // 关键字(键值)
		SplayTreeNode<T> left; // 左孩子
		SplayTreeNode<T> right; // 右孩子

		public SplayTreeNode() {
			this.left = null;
			this.right = null;
		}

		public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) {
			this.key = key;
			this.left = left;
			this.right = right;
		}
	}

	public SplayTree() {
		mRoot = null;
	}

	/*
	 * 前序遍历"伸展树"
	 */
	private void preOrder(SplayTreeNode<T> tree) {
		if (tree != null) {
			System.out.print(tree.key + " ");
			preOrder(tree.left);
			preOrder(tree.right);
		}
	}

	public void preOrder() {
		preOrder(mRoot);
	}

	/*
	 * 中序遍历"伸展树"
	 */
	private void inOrder(SplayTreeNode<T> tree) {
		if (tree != null) {
			inOrder(tree.left);
			System.out.print(tree.key + " ");
			inOrder(tree.right);
		}
	}

	public void inOrder() {
		inOrder(mRoot);
	}

	/*
	 * 后序遍历"伸展树"
	 */
	private void postOrder(SplayTreeNode<T> tree) {
		if (tree != null) {
			postOrder(tree.left);
			postOrder(tree.right);
			System.out.print(tree.key + " ");
		}
	}

	public void postOrder() {
		postOrder(mRoot);
	}

	/*
	 * (递归实现)查找"伸展树x"中键值为key的节点
	 */
	private SplayTreeNode<T> search(SplayTreeNode<T> x, T key) {
		if (x == null)
			return x;

		int cmp = key.compareTo(x.key);
		if (cmp < 0)
			return search(x.left, key);
		else if (cmp > 0)
			return search(x.right, key);
		else
			return x;
	}

	public SplayTreeNode<T> search(T key) {
		return search(mRoot, key);
	}

	/*
	 * (非递归实现)查找"伸展树x"中键值为key的节点
	 */
	private SplayTreeNode<T> iterativeSearch(SplayTreeNode<T> x, T key) {
		while (x != null) {
			int cmp = key.compareTo(x.key);

			if (cmp < 0)
				x = x.left;
			else if (cmp > 0)
				x = x.right;
			else
				return x;
		}

		return x;
	}

	public SplayTreeNode<T> iterativeSearch(T key) {
		return iterativeSearch(mRoot, key);
	}

	/*
	 * 查找最小结点:返回tree为根结点的伸展树的最小结点。
	 */
	private SplayTreeNode<T> minimum(SplayTreeNode<T> tree) {
		if (tree == null)
			return null;

		while (tree.left != null)
			tree = tree.left;
		return tree;
	}

	public T minimum() {
		SplayTreeNode<T> p = minimum(mRoot);
		if (p != null)
			return p.key;

		return null;
	}

	/*
	 * 查找最大结点:返回tree为根结点的伸展树的最大结点。
	 */
	private SplayTreeNode<T> maximum(SplayTreeNode<T> tree) {
		if (tree == null)
			return null;

		while (tree.right != null)
			tree = tree.right;
		return tree;
	}

	public T maximum() {
		SplayTreeNode<T> p = maximum(mRoot);
		if (p != null)
			return p.key;

		return null;
	}

	/*
	 * 旋转key对应的节点为根节点,并返回根节点。
	 *
	 * 注意: (a):伸展树中存在"键值为key的节点"。 将"键值为key的节点"旋转为根节点。 (b):伸展树中不存在"键值为key的节点",并且key <
	 * tree.key。 b-1 "键值为key的节点"的前驱节点存在的话,将"键值为key的节点"的前驱节点旋转为根节点。 b-2
	 * "键值为key的节点"的前驱节点存在的话,则意味着,key比树中任何键值都小,那么此时,将最小节点旋转为根节点。
	 * (c):伸展树中不存在"键值为key的节点",并且key > tree.key。 c-1
	 * "键值为key的节点"的后继节点存在的话,将"键值为key的节点"的后继节点旋转为根节点。 c-2
	 * "键值为key的节点"的后继节点不存在的话,则意味着,key比树中任何键值都大,那么此时,将最大节点旋转为根节点。
	 */
	private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) {
		if (tree == null) {
			return tree;			
		}

		SplayTreeNode<T> N = new SplayTreeNode<T>();
		SplayTreeNode<T> l = N;
		SplayTreeNode<T> r = N;
		SplayTreeNode<T> c;

		while(true) {
			int cmp = key.compareTo(tree.key);
			if (cmp < 0) {
				if (tree.left == null) {
					break;					
				}

				if (key.compareTo(tree.left.key) < 0) {
					c = tree.left; /* rotate right */
					tree.left = c.right;
					c.right = tree;
					tree = c;
					if (tree.left == null)
						break;
				}
				r.left = tree; /* link right */
				r = tree;
				tree = tree.left;
			} else if (cmp > 0) {

				if (tree.right == null)
					break;

				if (key.compareTo(tree.right.key) > 0) {
					c = tree.right; /* rotate left */
					tree.right = c.left;
					c.left = tree;
					tree = c;
					if (tree.right == null)
						break;
				}

				l.right = tree; /* link left */
				l = tree;
				tree = tree.right;
			} else {
				break;
			}
		}

		l.right = tree.left; /* assemble */
		r.left = tree.right;
		tree.left = N.right;
		tree.right = N.left;

		return tree;
	}

	public void splay(T key) {
		mRoot = splay(mRoot, key);
	}

	/*
	 * 将结点插入到伸展树中,并返回根节点
	 *
	 * 参数说明: tree 伸展树的 z 插入的结点
	 */
	private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) {
		int cmp;
		SplayTreeNode<T> y = null;
		SplayTreeNode<T> x = tree;

		// 查找z的插入位置
		while (x != null) {
			y = x;
			cmp = z.key.compareTo(x.key);
			if (cmp < 0)
				x = x.left;
			else if (cmp > 0)
				x = x.right;
			else {
				System.out.printf("不允许插入相同节点(%d)!\n", z.key);
				z = null;
				return tree;
			}
		}

		if (y == null)
			tree = z;
		else {
			cmp = z.key.compareTo(y.key);
			if (cmp < 0)
				y.left = z;
			else
				y.right = z;
		}

		return tree;
	}

	public void insert(T key) {
		SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null);

		// 如果新建结点失败,则返回。
		if ((z = new SplayTreeNode<T>(key, null, null)) == null)
			return;

		// 插入节点
		mRoot = insert(mRoot, z);
		// 将节点(key)旋转为根节点
		mRoot = splay(mRoot, key);
	}

	/*
	 * 删除结点(z),并返回被删除的结点
	 *
	 * 参数说明: bst 伸展树 z 删除的结点
	 */
	private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) {
		SplayTreeNode<T> x;

		if (tree == null)
			return null;

		// 查找键值为key的节点,找不到的话直接返回。
		if (search(tree, key) == null)
			return tree;

		// 将key对应的节点旋转为根节点。
		tree = splay(tree, key);

		if (tree.left != null) {
			// 将"tree的前驱节点"旋转为根节点
			x = splay(tree.left, key);
			// 移除tree节点
			x.right = tree.right;
		} else
			x = tree.right;

		tree = null;

		return x;
	}

	public void remove(T key) {
		mRoot = remove(mRoot, key);
	}

	/*
	 * 销毁伸展树
	 */
	private void destroy(SplayTreeNode<T> tree) {
		if (tree == null)
			return;

		if (tree.left != null)
			destroy(tree.left);
		if (tree.right != null)
			destroy(tree.right);

		tree = null;
	}

	public void clear() {
		destroy(mRoot);
		mRoot = null;
	}

	/*
	 * 打印"伸展树"
	 *
	 * key -- 节点的键值 direction -- 0,表示该节点是根节点; -1,表示该节点是它的父结点的左孩子; 1,表示该节点是它的父结点的右孩子。
	 */
	private void print(SplayTreeNode<T> tree, T key, int direction) {

		if (tree != null) {

			if (direction == 0) // tree是根节点
				System.out.printf("%2d is root\n", tree.key);
			else // tree是分支节点
				System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");

			print(tree.left, tree.key, -1);
			print(tree.right, tree.key, 1);
		}
	}

	public void print() {
		if (mRoot != null)
			print(mRoot, mRoot.key, 0);
	}
}

更新时间:2020-02-13 15:36:39

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构基础14非线性数据结构之自平衡二叉查找树之伸展树
最后更新:2020-02-13 15:36:39

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×