Nearly Balanced Trees

There are a collection of algorithms that use special rules to decide which rotations to apply when inserting and deleting elements to ensure that the binary search tree stays nearly balanced.

Nearly balanced means, for example, that the number of nodes in the left or right subtree is never fewer than 1/3 of the total number of nodes. This holds for all levels.

$T(n) \le T(2n/3) + 1$... what is T(n)?

Example algorithms: red-black trees, 2-3 trees.

Insertion, deletion, find, all in $O(\log n)$, worst case.