Динамические массивы? Такое есть в .net/C# ? 

Vit, я тебя прекрасно понимаю, как человека, который переходит с Delphi на C#. Сейчас сами переписываем огромный и слжный проект на C#.
По существу: ArrayList тебе поможет.

Добавлено через 40 секунд
PS. Дельфийские динамические массивы отдыхают по сравнению с функционалом местных массивов.

Ну а зачем сравнивать по функционалу массивы и коллекции? Ничего не отдыхает, насколько я понял колелкции C# точно такие же по функциональности как и в Дельфи...

В дельфи массивы тоже статические, при ресайзе память перевыделяется. В шарпе есть аналогичный Array.Resize .

А в C# вообще нет статических массивов. Все масивы динамические и память для них распределяется в куче. А абстрактный класс Array имеет методы для работы с массивоми. Жаль что Resize только для одномерных.
Есть еще такие прекрасные массивы как массивы массивов, изрезаные.
object[,] ar - двумерный
object[][] массив массивов 

 
Статические массивы могут организовываются в стеках с использованием stackalloc (однако это небезопасное средство предназначенное для оптимизации).

Информация по различным видам коллекций в С# - MSDN- System.Collections namespace

Разве int[] выделиться в куче?  Масив ссылочных типов - понятно, а valueble?

статические массивы, скорее исключение, а правилом является использование динамических массивов.

в C# массивы относятся к ссылочным типам. И не обязатально нужно знать размер во время компиляци. Память под него всеравно выделяется в куче, из каких элементов массив бы не состоял. Инициализировать можно по-разному:

int[] i = {1, 2, 3}
int[] i = new int[4];
а можно отложить - int[] i;

А чтобы небыло  упаковки и распаковки лучше использовать List<T>

Чем хуже ArrayList от List?

хотя бы отсутствием типизации
плюс, как было уже выше написано, все элементы преобразуются в object

Существует ли реализация дерева?
И возможно ли удаление элементов в коллекции за O(1), а не O(n)?

я в игноре? =)
Dictionary чем не устраивает?

невизуальных деревьев вроде бы (пните, если что) нет
да и было бы там что-то вроде

Dictionary тоже идёт с нумератором приудалении из середины или если из начала, происходит переиндексирование. Может я не так понимаю. Могу ошибаться. Объясни подробней. кстати насчёт деревьев нашёл статьи
http://msdn2.microsoft.com/en-us/library/ms379573.aspx
http://msdn2.microsoft.com/en-us/library/ms379574.aspx
http://msdn2.microsoft.com/en-us/library/ms379572.aspx
там что то описано интересное сейчас буду разбираться.

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