Before revision:  First, we show that a (1 + 1{t})-approximation of the optimal STT for a given search distribution can be computed in time O(n^{2t + 1}) for all integers t \geq 1. Second, we identify a broad family of STTs with linear rotation-distance, allowing the generalization of Splay trees to the STT setting.
After revision:  First, we show that a (1 + 1{t})-approximation of an optimal size-n STT for a given search distribution can be computed in time O(n^{2t + 1}) for all integers t \geq 1. Second, we identify a broad family of STTs with linear rotation-distance, allowing the generalization of Splay trees to the STT setting.