C�������� ������. �������� ����������.

������ ������

������ ������ - ��� ������� ������, ������� ��������� ��� ���������� (skip) �������� ��������, ������� ����� � �������. ��� ��������� ���������� ����������� ����������������� ������, ����������� �������� ���������� �������������� ������ � �������. � �� �� ����� ������� � �������� �������� ������������ ������������. ������ �������� ������� ������ � ����� ������� ���� O(lg n). ��� ���������� ������ ������� �������� O(n), �� ������ ������ ������ ������������.

��� ��������� ����� ������ � �������� �������� ������������������� ��������� ������ � �������� ������������ AVL-tree.

������

����, ������� � ������ ������ �������, ����� ���������� �����, ������������ ��� ������ ���� � �������� ������. ����� ����� ���, �� ��������� ������ ��������, ������ ���������� �����, ������������ � ���� �����. �� ���. 3.8, ��������, ����� ������� ������ ������������ ������� ����������� ������. ������� ���� "�������" ������, �� ������� �����. ������� �� ���� �� ������� ������ 1, �����, ����� ������ �� ������� ������� ������, ������ �� ������� �������� ������.

��� ������� ���� ����� ���� ��������� - �� ����� �������� ������ ����� �������. ����� �� ���. 3.8 �� ����� ������ �������, ������� ��������� ��������� ��� ������� �������. ��� ������ �������� �� ��������� �� ����� ������, ���� �� ������ �� ������� ������� ������. ����� �� ��� ��������� �������� ����������������, �������� �� ������� 1-�� ������. ���� ����� ����� �� �������� �� ������� 0-�� ������.

�������� ����, �� ������ ����� ���������� ���������� ��������� �� ���� ������. ��� �������� ����� ����� �������� � �������������� ���������� ���������: ��� ���������� ������ ���� �� "������� ������", ����� ����������, ����� �� ��������� ��� �������. ��������, �� ����� ��������� ��������� ������ �� ��� ���, ���� �������� "�����". ���� ���������� ������ ���� �������, �� ����� ���� ���������� � ������� ������� � ����� ������ ���� O(n). ������, ���� ������� ����������� ����� �������, ������ ������ ����� ������� ������� � ������ �� ������ ������, � ��� ������ ����� ������ ���� O(lg n).

��������� ���������� ������ ������� �������� � ���� ��������� �������, ��� ������� ������ � ��� ��������������� ������������� �������. ��� ������� �������� ��� ������� �������� ����. ��������, ����� �� ���� ������� � ������ �� 1000 �����, ����������� ����, ��� ����� ������ �������� � 5 ��� ������ ��������, ����� ������� ��� 1/1,000,000,000,000,000,000.

����������

skiplist.pas - ���������� ����-������� �� ������� � ����������� ����������.

skiplist.c - ���������� ������ �� ����-�������� �� ��. ��������� typedef T, � ����� compLT � compEQ ������� �������� ���, ����� ��� ��������������� ������, �������� � ����� ������. ����� ����, ����������� ������� ��������� MAXLEVEL; �� �������� ���������� � ����������� �� ���������� ������ ������.

������� initList ���������� � ����� ������. ��� ������� ������ ��� ��������� ������ � �������������� ��� ����. ��������� ����, ��� ������ ����, ������� insertNode ������� ����� ���� � ��������� ��� � ������. �������, insertNode ������� ���������� ����� � ������, ���� ���� ������ ���� ��������. � ������� update ������� ��������� ������������� ������ �� ���� ������� �������. ��� ���������� � ���������� ������������ ��� ���������� ��������� ������ ������ ����. ��� ����� ����, � ������� ���������� ��������� �����, ������������ �������� newLevel, ����� ���� ��������� ������ ��� ����. ������ ������ ��������������� �� ����������, ���������� � ������� update. ������� deleteNode ������� ���� �� ������ � ����������� ���������� ��� ������. ��� ����������� ���������� ������� findNode � ��� �� ���� � ������ ��������� ����.

����� �� ��������, � ���������� � ���������.