Построить левое поддерево с числом узлов n

@Igorokmen · Регистрация: 31.01.2013

Author24 — интернет-сервис помощи студентам

Чтоб построить сбалансированное дерево, нужно:

• Взять один узел в качестве корня.
• Построить левое поддерево с числом узлов n1=N div 2
• Построить правое поддерево с числом узлов n2=N-n1-1 //КАК ЭТО???

Я не понимаю почему чтоб построить правое поддерево нужно воспользоваться выражением n2=N-n1-1

????

@SatanaXIII · 28.08.2013, 13:07

Вероятно:
n2=N-n1-1 -> n2=N-(N div 2)-1 -> n2=~(N div 2)-1
То есть:
уже вычисленное значение n1, равное в общем случае половине (всем четным) значений, вычитается из общего количества. и остается только половина нечетных. Из которых, в свою очередь, вычитается единица - узел, уже использованная в качестве корня.

@Igorokmen 3 / 3 / 1 Регистрация: 31.01.2013 Сообщений: 108
		1
	Построить левое поддерево с числом узлов n 28.08.2013, 12:29. Показов 551. Ответов 1 Метки нет (Все метки) Чтоб построить сбалансированное дерево, нужно: • Взять один узел в качестве корня. • Построить левое поддерево с числом узлов n1=N div 2 • Построить правое поддерево с числом узлов n2=N-n1-1 //КАК ЭТО??? Я не понимаю почему чтоб построить правое поддерево нужно воспользоваться выражением n2=N-n1-1 ???? 0

@SatanaXIII Почетный модератор 5850 / 2861 / 392 Регистрация: 01.11.2011 Сообщений: 6,907
	28.08.2013, 13:07	2
	Вероятно: n2=N-n1-1 -> n2=N-(N div 2)-1 -> n2=~(N div 2)-1 То есть: уже вычисленное значение n1, равное в общем случае половине (всем четным) значений, вычитается из общего количества. и остается только половина нечетных. Из которых, в свою очередь, вычитается единица - узел, уже использованная в качестве корня. 1