Деревья и списки

[Sidoy]

Добрый день!

Нужна помощь в таком вопросе, есть задача реализовать бинарное дерево(у каждого узла только два потомка), вот у меня вопрос, первый потомок обязательно должен быть слева или потомок должен быть слева, когда он меньше родителя?

Второй вопрос касается списков, хочу реализовать свой класс-список, неунаследованый ни от какого другого класса. Сразу напишу, что задача стоит в том что-бы класс обеспечивал простые списковые операция(добавление, вставка,...). Источником хранения данных в классе будет массив определенной величины (так как в C# и Java нет возможности динамически менять размер массива) поэтому я решил завести второй массив, временный, т.е. когда нужно добавить новый элемент в массив, я инициализирую временный массив размерностью такой же как первый+1, заполняю его, потом переинициализирую основной массив(делаю его тоже размера первый+1) и копирую в него значения с первого массива. Вот такой вот способ я придумал, но может посоветуете что-то более универсальное?

[Тролль]

Sidoy:

Ну, правое и левое - понятия относительные (если не считать квантовой физики), но принято, что в левом дереве при спуске по нему значения уменьшаются, начиная с самого корня, значит, первый потомок должен быть слева, когда он меньше предка. Иначе он будет правым.

Реализацию, при которой весь список при добавлении или удалении элемента приходится переписывать, сделать, конечно, можно, но смысла в ней немного. Тогда проще и экономичнее обычный отсортированный массив.

А обычно в учебных проектах список реализуется так, что при внесении нового элемента в список у системы каждый раз запрашивается под него память, а при удалении элемента - отдается обратно системе. Но выделение памяти системой - довольно длительная операция, поэтому в профессиональных реализациях обычно запрашивают память сразу массивом на много элементов, размещают в ней только новые элементы, пока она не кончится, а потом при необходимости запрашивают снова. Но у тебя реализация учебная, так что можно сделать с отдельным запросом у системы памяти для каждого нового элемента.

P.S. Точнее сказать, не в левом дереве, а при спуске по левой стороне дерева.

Edited August 14, 2010 by Тролль

[Sidoy]

Тролль:

Ну, правое и левое - понятия относительные (если не считать квантовой физики), но принято, что в левом дереве при спуске по нему значения уменьшаются, начиная с самого корня, значит, первый потомок должен быть слева, когда он меньше предка. Иначе он будет правым.

Я тут слегка разобрался, меня интересует "полное бинарное дерево", т.е. порядок значение не имеет, а единственное что важно это что-бы потомков либо не было, либо была 2. То что левое меншье корня это свойственно "Двоичному дереву поиска". Это всё как я понял согласно Википедии. Если у Вас есть другие аргументы, то прошу написать.

[Тролль]

Sidoy:

С "полным двоичным деревом" в русском языке некоторая неразбериха, так как иногда говорят о "полном двоичном дереве", в котором обязательно есть все листья, и "почти полном двоичном дереве", в котором на последнем уровне могут быть не все листья, но его часто тоже называют "полным двоичным деревом". Обычно так: "Полное дерево (complete tree) содержит максимально возможное число узлов на каждом уровне, кроме нижнего. Все узлы на нижнем уровне сдвигаются влево." (http://bookz.ru/authors/stivens-rod/vbalg/page-11-vbalg.html)

P.S. А лучше всего ссылаться на признанного авторитета, например, Дональда Кнута, написавшего, так сказать, библию алгоритмов - "Искусство программирования", там в первом томе "Основные алгоритмы" на стр. 493 дается такое определение полного бинарного дерева:

Edited August 15, 2010 by Тролль