Я должен доказать, что в двоичном дереве поиска число узлов с двумя дочерними элементами меньше числа листьев. Я нашел некоторые доказательства по индукции в Интернете, но я хотел меньше подойти к этой проблеме «математически». Поэтому я подумал об этом:Двоичное дерево поиска доказывает количество листьев
- у нас есть только один корень (который является листом), поэтому у нас есть 1 лист и 0 узлов с двумя детьми, ОК.
-когда у нас есть узел без каких-либо дочерних элементов, и мы добавляем к нему ребенка - количество листьев остается одинаковым (узел, который мы добавили, больше не является листом, а новым является дочерним) и количество узлов с двое детей остаются прежними.
-когда у нас есть узел с 1 ребенком, и мы добавляем к нему второго ребенка, количество листьев увеличивается, но количество узлов с двумя детьми также увеличивается, так что +1 здесь и +1 есть, все же разница в 1 , ОК.
И все, нет другой возможности для добавления. Итак, с самого начала это свойство «работает» только для одного листа (root), а затем, независимо от того, как мы добавляем к этому дереву, свойство все равно будет сохранено. Достаточно ли этого, чтобы доказать, что есть еще один лист, чем узлы с двумя детьми? Должен ли я что-то добавить (возможно, упоминание об удалении)? Я знаю, что это, вероятно, может быть написано как нормальная математическая индукция каким-то образом, но я хотел избежать слишком большой формальности, так ли это «законный» способ доказать этот факт? Заранее спасибо.