Определение непрерывной реализации на базе вектора. Непрерывные реализации двух и трёх стеков, ограниченных в совокупности. Оценки эффективности основных операций.

Определение: Реализация на базе вектора называется непрерывной, если все элементы контейнера хранятся в векторе непрерывным куском и порядок элементов в имитируемой структуре (если он существует) соответствует порядку элементов в векторе.

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

Идеально сбалансированные и АВЛ-деревья. Построение идеально сбалансированного дерева с заданным числом узлов (реализация). Три варианта обхода двоичного дерева поиска (реализация).

Двоичное дерево поиска является сбалансированным, если его высота логарифмически зависит от n - количества эл-тов в дереве (или в каждом узле дерева высота левого и правого поддерева отличается не более чем на 1).
Московские математики Г.М.Адельсон-Вельский и Е.М.Ландис предложили в 1962г. схему самобалансирующегося поискового дерева; эта схема известна сейчас как АВЛ-дерево. Их конструкция позволяет поддерживать приблизительное равенство (см. опр. сбалансированного дерева) левой и правой ветвей двоичного дерева во всех его узлах с помощью небольших преобразований (так называемых левого и правого поворота), затрагивающих каждый раз не более трёх узлов:
  положим x - указатель на узел; y - x.right. Тогда левый поворот вокруг x может быть осуществлён всего в два действия:
x.right = y.left;
y.left = x;
Правый поворот выполняется аналогично.

Построение идеально сбалансированного дерева с заданным числом узлов (реализация)

public class Balans_tree {
 private Node2 root;

 public Balans_tree (int size){
  root=new_node(size);
}
 public Node2 new_node(int size){
  if (size==0) return null;
  if (size==1) return new Node2(1,null,null);
  if (size==2) return new Node2(2,new_node(1),null);
  return new Node2(size,new_node(size/2),new_node(size-1-size/2));
 }
}

Три варианта обхода двоичного дерева поиска (реализация):
RAB - сверху вниз;
ABR - снизу вверх;
ARB - слева направо.

RAB	ABR	ARB
void print(Node2 x) {  if (x != null) {   System.out.println(x.val);   print(x.left);   print(x.right);  } }	void print(Node2 x) {  if (x != null) {   print(x.left);   print(x.right);   System.out.println(x.val);  } }	void print(Node2 x) {  if (x != null) {   print(x.left);   System.out.println(x.val);   print(x.right);  } }

Сортировки
Исходники: Starting.java | Sort.java | Sort (версия для печати)

public class Sort {

 //BUBBLE SORT
	static void BubbleSort(int a[]) {
		for (int i = a.length; --i >= 0; ) {
			for (int j = 0; j < i; j++) {
				if (a[j] > a[j+1]) {
				    int T = a[j];
				    a[j] = a[j+1];
				    a[j+1] = T;
				}
			}
		}
	}

 //SELECTION SORT

	static void SelectionSort(int a[]) {
		for (int i = 0; i < a.length; i++) {
		    int min = i;
	        for (int j = i + 1; j < a.length; j++) {
		        if (a[j] < a[min]) {min = j;}
		    }
	        int T = a[min];
	        a[min] = a[i];
	        a[i] = T;
	    }
	}

 //INSERTION SORT

	static void InsertionSort(int a[]) {
		for (int i = 1; i < a.length; i++) {
		    int j = i;
		    int B = a[i];
		    while ((j > 0) && (a[j-1] > B)) {
	            a[j] = a[j-1];
		        j--;
		    }
		    a[j] = B;
	    }
	}

 //SHELL SORT

	static void ShellSort(int a[]) {
		int h = 1;
        /*
         * find the largest h value possible
         */
        while ((h * 3 + 1) < a.length) {h = 3 * h + 1;}
        /*
         * while h remains larger than 0
         */

        while( h > 0 ) {
            /*
             * for each set of elements (there are h sets)
             */
            for (int i = h - 1; i < a.length; i++) {
                /*
                 * pick the last element in the set
                 */
                int B = a[i];
                int j = i;
                /*
                 * compare the element at B
                 * to the one before it in the set
                 * if they are out of order continue this loop, moving
                 * elements "back" to make room for B to be inserted.
                 */

                for(j = i; j >= h && a[j-h] > B; j -= h) {a[j] = a[j-h];}
                /*
                 *  insert B into the correct place
                 */
                a[j] = B;
            }
            /*
             * all sets h-sorted, now decrease set size
             */
            h = h / 3;
        }
     }

 //HEAP SORT

	static void HeapSort(int a[]) {
		int N = a.length;
		for (int k = N/2; k > 0; k--) {
		    downheap(a, k, N);
	    }
		do {
            int T = a[0];
            a[0] = a[N - 1];
            a[N - 1] = T;
            N = N - 1;
		    downheap(a, 1, N);
		} while (N > 1);
	}
        static void downheap(int a[], int k, int N) {
		int T = a[k - 1];
		while (k <= N/2) {
	            int j = k + k;
	            if ((j < N) && (a[j - 1] < a[j])) {
		        j++;
		    }
		    if (T >= a[j - 1]) {
			break;
		    } else {
                a[k - 1] = a[j - 1];
                k = j;
	        }
		}
	    a[k - 1] = T;
	}

    //QUICK SORT

    static void QuickSort(int a[], int lo0, int hi0) {
    	int lo = lo0;
    	int hi = hi0;
    	if (lo >= hi) {return;}
        else if( lo == hi - 1 ) {
                /*
                 *  sort a two element list by swapping if necessary
                 */

                if (a[lo] > a[hi]) {
                    int T = a[lo];
                    a[lo] = a[hi];
                    a[hi] = T;
                }
                return;
    	}
            /*
             *  Pick a pivot and move it out of the way
             */
    	int pivot = a[(lo + hi) / 2];
            a[(lo + hi) / 2] = a[hi];
            a[hi] = pivot;
        while( lo < hi ) {
                /*
                 *  Search forward from a[lo]
                 * until an element is found that
                 *  is greater than the pivot or lo >= hi
                 */
                while (a[lo] <= pivot && lo < hi) {lo++;}
                /*
                 *  Search backward from a[hi] until element is found that
                 *  is less than the pivot, or lo >= hi
                 */

                while (pivot <= a[hi] && lo < hi ) {hi--;}
                /*
                 *  Swap elements a[lo] and a[hi]
                 */
                if( lo < hi ) {
                    int T = a[lo];
                    a[lo] = a[hi];
                    a[hi] = T;
                }
    	}
            /*
             *  Put the median in the "center" of the list
             */

        a[hi0] = a[hi];
        a[hi]  = pivot;
            /*
             *  Recursive calls, elements a[lo0]
             *  to a[lo-1] are less than or
             *  equal to pivot, elements a[hi+1]
             *  to a[hi0] are greater than
             *  pivot.
             */
        QuickSort(a, lo0, lo-1);
        QuickSort(a, hi+1, hi0);
    }

}