sbt什么特點？

Size Balanced Tree（簡稱SBT）是一自平衡二叉查找樹，是在計算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)。它是由中國廣東中山紀(jì)念中學(xué)的陳啟峰發(fā)明的。

陳啟峰于2006年底完成論文《Size Balanced Tree》，并在2007年的全國青少年信息學(xué)奧林匹克競賽冬令營中發(fā)表。由于SBT的拼寫很容易找到中文諧音，它常被中國的信息學(xué)競賽選手和ACM/ICPC選手們戲稱為“傻B樹”、“Super BT”等。相比紅黑樹、AVL樹等自平衡二叉查找樹，SBT更易于實現(xiàn)。

據(jù)陳啟峰在論文中稱，SBT是“目前為止速度最快的高級二叉搜索樹”。SBT能在O(log n)的時間內(nèi)完成所有二叉搜索樹（BST）的相關(guān)操作，而與普通二叉搜索樹相比，SBT僅僅加入了簡潔的核心操作Maintain。

由于SBT賴以保持平衡的是size域而不是其他“無用”的域，它可以很方便地實現(xiàn)動態(tài)順序統(tǒng)計中的select和rank操作。