平衡树 Balance Tree

「OI」平衡树

平衡树是 OI 中的重要内容,它可以根据不同的实现被分为很多种类。

平衡树本质上是二叉搜索树的进阶版本,平衡树通过了设定特定的规则防止了二叉搜索树不断插入结点造成的退化问题。

主要介绍三种平衡树:Splay、FHQ-Treap、替罪羊树。下面是方便的跳转链接。

Splay Z0

「OI」Splay

文艺平衡树 Splay,也叫伸展树、分裂树,是一种二叉排序树,它能快速完成插入、查找和删除操作。它是由丹尼尔·斯立特 Daniel Sleator 和 罗伯特·恩卓·塔扬 Robert Endre Tarjan 在 1985 年发明的。

Continue reading…