Вставка в АВЛ-дерево вершины 
с ключом 
при условии, что такой вершины в этом дереве нет, осуществляется следующим образом:
- находится вершина
, ребенком которой должна стать вершина ;
- вершина делается ребенком вершины ;
- производится подъем от вершины к корню, при этом, если какая-то из вершин несбалансирована, производится, в зависимости от значения баланса, левый или правый поворот.
Первый этап нуждается в пояснении. Спуск до будущего родителя вершины осуществляется, начиная от корня, следующим образом:
- Пусть ключ текущей вершины равен
.
- Если
и у текущей вершины есть левый ребенок, переходим к левому ребенку.
- Если и у текущей вершины нет левого ребенка, то останавливаемся, текущая вершина будет родителем новой вершины.
- Если
и у текущей вершины есть правый ребенок, переходим к правому ребенку.
- Если и у текущей вершины нет правого ребенка, то останавливаемся, текущая вершина будет родителем новой вершины.
Отдельно рассматривается следующий крайний случай -- если до вставки дерево было пустым, то вставка новой вершины осуществляется проще: новая вершина становится корнем дерева.
Входной файл содержит описание двоичного дерева, а также ключ вершины, которую требуется вставить в дерево.
В первой строке файла находится число 
(
) -- число вершин в дереве. В последующих строках файла находятся описания вершин дерева. В 
-ой строке файла (
) находится описание 
-ой вершины, состоящее из трех чисел 
, 
, 
, разделенных пробелами -- ключа в -ой вершине (
), номера левого ребенка -ой вершины (
или 
, если левого ребенка нет) и номера правого ребенка -ой вершины (
или 
, если правого ребенка нет).
Все ключи различны. Гарантируется, что данное дерево является корректным АВЛ-деревом.
В последней строке содержится число (
) -- ключ вершины, которую требуется вставить в дерево. Гарантируется, что такой вершины в дереве нет.
Выведите в том же формате дерево после осуществления операции вставки. Нумерация вершин может быть произвольной при условии соблюдения формата.
input.txt
output.txt
AVLTreeInsert.scala