2015-08-12
436
Пусть дан корень 
с левым и правым поддеревьями 
и 
. Предположим, что в включается новый элемент, вызывая увеличение его высоты на единицу.
Возможны три исходных случая:
1. 
: и становятся неравной высоты, но критерий сбалансированности не нарушается.
2. 
: и приобретают равную высоту, т.е. баланс становится даже лучше.
3. 
: критерий сбалансированности нарушается, и дерево необходимо перестроить.
