the root, remembering to set MaxNodeCount to NodeCount. This gives deletion a worst-case performance of time, whereas the amortized time is . Sketch of proof for cost of deletion Suppose the scapegoat tree has elements and has just been rebuilt (in other words, it is a complete binary tree). At most deletions can be performed before the tree must be rebuilt. Each of these deletions take time (the amount of time to search for the element and flag it as deleted). The deletion causes the tree to be rebuilt and takes (or just ) time. Using aggregate analysis it becomes clear that the amortized cost of a deletion is : Etymology The name Scapegoat tree "[...] is based on the common wisdom that, when something goes wrong, the first thing people tend to do is find someone to blame (the scapegoat)." In the Bible, a scapegoat is an animal that is ritually burdened with the sins of others, and then driven away. See also Splay tree Trees Tree rotation AVL tree B-tree T-tree References External links Binary trees Search trees Amortized data structures