SBT的定义是什么？

SBT的定义是什么？

SizeBalancedTree(以下简称SBT)是一种自平衡二叉搜索树，是计算机科学中使用的数据结构。由中国广东中山纪念中学陈启峰发明。2006年底，陈启峰完成了论文《SizeBalancedTree》，并在2007年全国青年信息学奥林匹克竞赛冬令营上发表。由于SBT的拼写很容易找到中文谐音，它经常被中国信息学竞赛选手和ACM/ICPC选手戏称为“傻B树”、“SuperBT”等。

SBT比红黑树、AVL树等自平衡二叉搜索树更容易实现。据陈启峰介绍，SBT是“到目前为止速度最快的高级二叉搜索树”。SBT可以在O(logn)所有二叉搜索树都在时间内完成（BST）与普通二叉搜索树相比，SBT只增加了简单的核心操作Maintain。由于SBT依赖于size域而不是其他“无用”域的平衡，因此在动态顺序统计中很容易实现select和rank操作。