In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Arne Andersson in 1989 and again by Igal Galperin and Ronald L. Rivest in 1993. It provides worst-case {\displaystyle {\color {Blue}O(\log n)}} lookup time... Wikipedia