Scapegoat tree 替罪羊树
| Scapegoat tree |
|---|
| Type |
Tree |
| Invented |
1962 |
| Invented by |
Arne Andersson, Igal Galperin, Ronald L. Rivest |
Time complexity
in big O notation |
|
Average |
Worst case |
| Space |
O(n) |
O(n) |
| Search |
O(log n) |
O(log n) |
| Insert |
O(log n) |
amortized O(log n) |
| Delete |
O(log n) |
amortized O(log n) |
In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Arne Andersson and again by Igal Galperin and Ronald L. Rivest. It provides worst-case O(log n) lookup time, and O(log n) amortized insertion and deletion time.