avl trees , red black trees - built-in balancing mechanisms

 

algorithms for shifting while inserting or deleting built in to keep binary tree  "logarithmic in height"  rather than  "linear in height"

inserting into a balanced binary tree is indeed big O of logn , but that depends on the prerequisite of you keeping the binary search tree balanced

source: cs50