Просто відчуваю як я тупію від тестування в цілому, та від C# зокрема. Навіть забувати почав про теорію якої я і так небагато знав. І вирішив я написати реалізацію AVL-дерева.


По перше з'ясувалося що я не сильно пам'ятаю як і коли треба обертати таке дерево. Довелося лізти у вікіпедію. Ну коротше таки я його написав і навіть протестував швидкість у порівнянні з парою інших структур даних. Кому цікаво ось сорци - http://cid-b21290194214a37d.skydrive.live.com/self.aspx/public/AVLTree.7z.

Хто не пам'ятає (чи не знає) AVL-дерево це таке дерево яке росте в ширину, залишаючись збалансованим. Тобто різниця у висоті піддедрев для будь якого вузла дерева не може перевищувати 1. Досягається це обертанням піддерева уліво чи управо в залежності від того яка гілка переважує. Звісно після обертання баланс (висота піддерев) перераховується. Ось тут - http://www.csi.uottawa.ca/~stan/csi2514/applets/avl/BT.html знаходиться аплет що візуалізує доавання/вилучення елементів з AVL дерева.

Одразу скажу - в моїх сорцах основні гальма у функції InsertItem. Але брудні прийоми типу __fastcall я не використовува (: Вдосконалити фукнкцію можна для випадку коли елемента нема в дереві - замість спочатку його шукати, а потім, не знайшовши, вставляти - можна просто об'єднати GetItem та InsertItem в один метод. Хоча з іншого боку в збалансованому дереві на 1.000.000 елементів доведеться переглянути лише 20 елементів у найгіршому випадку, так що можна ще трохи подумати стосовно пришвидшення алгоритмів.

В мене вийшли такі результати:



Результати у тіках процесора моєї робочої машини. Кому цікаво - можете прикрутити якусь іншу структуру даних чи спробувати все це щастя скомпілювати і запустити на вашій тачці.

Якщо подивитись на табличку то видно що AVL-дерево лише трохи виграє у пошуку елементів. Це відбувається завдяки тому що мапи (як правило) ствоюються на основі червоно-чорних дерев в яких "легше" додавання елементів, але дерево не виходить таким ідеально збалансованим. Ну і звісно моя реалізація абсолютно не є ідеальною, думаю там багато чого можна вдосконалити (: Ось тільки б час знайти, хоча його і не так багато начебто треба.

Забув сказати що на написання всього цього щастя пішло десь 3 години (розтягнутих на 4 дні). А це дуже погано. Таке треба робити хоча б за 1.5 години. ):

Comments are wellcome!