TRINGULAR ARRAY (ARRAY SEGITIGA)

TRINGULAR ARRAY (ARRAY SEGITIGA)

Akan kita tinjau beberapa aspek pelinearan suatu array yang khusus, yakni tringular
array. Tringular array dapat merupakan upper tringular (seluruh elemen di bawah
diagonal utama = 0) ataupun lower tringular (seluruh elemen di atas diagonal utama =0).

Dalam array lower triangular dengan N baris, jumlah maksimum elemen <> 0 pada
baris ke-I adalah 1, karenanya total elemen <> 0, tidak lebih dari :

N
Σ I = N(N+1)/2
I = 1

Gambar 2.10 menunjukkan triangular array berorder 6 x 6.
X X X X X X X 0 0 0 0 0
0 X X X X X X X 0 0 0 0
0 0 X X X X X X X 0 0 0
0 0 0 X X X X X X X 0 0
0 0 0 0 X X X X X X X 0
0 0 0 0 0 X X X X X X X
(a) (b)

Gambar 2.10 (a) Upper triangular array (b) Lower triangular array
Rumus ini berlaku pula untuk array upper tringular dengan N baris. Kalau N besar,
alangkah baiknya kalau elemen nol tidak usah kita simpan dalam memori. Suatu
pendekatan terhadap problema ini adalah dengan pelinearan array, dan dengan hanya
menyimpan bagian array yang tidak nol. Misalkan kita menyimpan array upper tringular T secara baris dalam array satu dimensi S, dengan batas subscript I sampai N(N+I)/2. Elemen T(1,1) disimpan sebagai S(1), elemen T(1,2) sebagai S(2) dan seterusnya, sehingga elemen T(1,N) disimpan sebagai S(N). Maka elemen T(2,2) disimpan sebagai S(N+1) (karena T(2,1) = 0).

Terakhir sekali, elemen T(N,N) akan disimpan sebagai S(N(N+1)/2). Kadang-kadang suatu program menggunakan lebih dari satu array tringular. Untuk itu kita dapat menyimpan 2 array sekaligus. Misalnya array A upper triangular berorder
N x N dan array B lower triangular berorder (N-1) x (N-1). Mereka dapat kita simpan sebagai array C berorder N x N. Di sini C(l,J) = A(l,J) untuk I <= J dan C(I+1,J) = B(I,J) untuk I >= J.

Sekarang apabila array A upper tringular berorder N x N sedangkan array B lower
tringular, juga berorder N x N, maka array C yang mengandung keduanya harus berorder
N x (N+1). Di sini elemen A(I,J) disimpan sebagai C(I,J+1) untuk I <= J, dan B(I,J)
disimpan sebagai C(I,J) untuk I >= J.

Perhatikan contoh berikut array A berorder (3 x 3) merupakan upper tringular.

1 2 3
0 4 5
0 0 6

Array B berorder (2 x 2) merupakan lower tringular,

7 0
8 9


maka mereka disimpan bersama dalam array C sebagai

1 2 3
7 4 5
8 9 6

Contoh berikut,

1 2 3 7 0 0
A = 0 4 5 B = 8 9 0
0 0 6 11 12 13

dapat disimpan sebagai array C berorder (3 x 4)

7 1 2 3
8 9 4 5
11 12 13 6

Misalkan sekarang ada 2 array, sama-sama upper tringular, yakni array A1 dan A2.
Kita dapat menyimpan mereka bersama-sama dengan melakukan transpose terhadap salah
satu array tersebut, misalnya A2 menjadi A2T. A2T adalah array lower tringular. Array C berorder N x (N+1) akan menyimpan elemen A1(I,J) sebagai C(I,J+1) untuk I <= J, dan elemen A2(I,J) akan disimpan sebagai C(J,I) untuk I >= J.

Sebagai contoh adalah array :

1 2 3 7 8 9
A1 = 0 4 5 A2 = 0 11 12
0 0 6 0 0 13

7 0 0
maka A2T = 8 11 0
9 12 13

dan mereka tersimpan sebagai :

7 1 2 3
C = 8 11 4 5
9 12 13 6