AiSD Lista 6

http://books.google.pl/books?id=oaVq6dbw37kC&lpg=PA283&ots=VikmbLYx8z&dq=IQSort%20without%20stack&hl=fr&pg=PA283#v=onepage&q&f=false

aisd02.pdf

W każdym nodzie trzymać 2 wskaźniki na prev i next.

Odpowiednio aktualizować je przy insert i delete (odpowiednio od liści do korzenia \Rightarrow 2 razy przechodzimy ścieżkę \Rightarrow dalej O(log n).

Podczas balansowania zachowujemy porzadek inorder, wiec nic nie musimy zmieniac.

• http://en.wikipedia.org/wiki/Longest_increasing_subsequence
• http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
• http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.c

#include <stdio.h>
#include <stdlib.h>

int lcs(int *a, int N) {
        int     *best,
                *prev,
                *num,
                 i,
                 j,
                 max = 0;
        best    = malloc(sizeof(int) * 3 * N);
        prev    = best + N + 1;
        num     = prev + N + 1;

        for (i = 0; i < N; i++) {
                best[i] = 1;
                prev[i] = i;
                num[i]  = 1;
        }

        for (i = 1; i < N; i++) {
                int t = 1;
                for (j = 0; j < i; j++) {
                        if (a[j] < a[i]) {
                                if (best[j] + 1 > t) {
                                        best[i] = t = best[j] + 1;
                                        prev[i] = j;
                                        num[i] = num[j];
                                } else if (best[j] + 1 == t) {
                                        num[i] += num[j];
                                }
                        }
                }
        }

        j = 0;
        for (i = 0; i < N; i++) {
                if (best[j] < best[i]) {
                        j = i;
                        max = num[j];
                } else if (best[j] == best[i]) {
                        max += num[j];
                }
        }

        free(best);

        return max;
}
 
int main(){
        int b[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
        printf("%d\n", lcs(b, sizeof(b)/sizeof(int)));
        return 0;
}

PyAVL
Procedura split tam jest, wlepiłbym plik, ale nie można uploadować plików bez rozszerzeń, z rozszerzeniami .txt albo .c