Scapegoat tree

In this article, we will explore in detail about Scapegoat tree which is a Self Balancing Binary Tree without requiring any extra space which puts Scapegoat Tree at an unique advantage.

Table of contents

Binary treeSelf balancing binary treeScapegoat treePartial rebuildingIn-depth analysis of scapegoat treePython implementationComplexity analysis

Let us get started with Scapegoat tree.

Binary tree

When all non-leaf nodes of a tree data structure has atmost 2 children, then such a d...