Operations Search $$O(n)$$ Insert $$O(log\ n)$$ Due to restoration Remove $$O(log\ n)$$ Due to restoration Peek $$O(1)$$ The root node