"O(1) expected restructuring" doesn't imply "O(1) expected insert/search/delete". My read of your quoted text is "This has the same average time complexity as

"O(1) expected restructuring" doesn't imply "O(1) expected insert/search/delete". My read of your quoted text is "This has the same average time complexity as WAVL/red-black trees, but is a simpler algorithm", which puts the search/insert/delete time complexity at O(log(n)). Being top-down means log(n) time complexity since that's the lower bound on the height of the tree.