30
2019
08

如何理解splay树

本文参考资料:https://www.cnblogs.com/cjyyb/p/7499020.html学习splay树首先要学习SBT,即二叉搜索树,二叉搜索树,对于任意一个节点,左儿子的值比它小,右儿子的值比它大并且任意一棵子树单独拎出来也是一棵二叉搜索树二叉搜索树进行中序遍历后序列正好是有序的,查找复杂度o(lgn)。但是如果一开始给定的序列就是有序的,我们构造的SBT会是一条长链,查找复杂度就变会o(n)了。各位大佬们为了解决平衡树这个尴尬的问题,想出了各种方法。。也就是弄出了各种树,AV