Binary Search Tree
- The left subtree of a node contains only nodes with keys less than the node's key
- The right subtree of a node contains only nodes with keys greater than the node's key
- The left and right subtree each must also be a binary search tree.
Bisect
This module provides support for maintaining a list in sorted order without having to sort the list after each insertion.
bisect.bisect_left(a, x, lo=0, hi=len(a)) Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries.
bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))
Binary Indexed Tree
Super detail explanation: