Tam dengeli ağaçlar kullanmanın bir avantajı, bunların basit bir düz dizi gösterimine elverişli olmasıdır. Bu gösterimde yaprak düğümler çift numaralı düğümlerdir ve n'inci yaprak 2*n konumunda yer alır. Ara düğümler ise tek numaralı düğümlerde tutulur. Örneğin, 8 yapraklı ağaç aşağıdaki yapıya sahiptir:
X
|
.---------+---------.
/ \
X X
| |
.---+---. .---+---.
/ \ / \
X X X X
/ \ / \ / \ / \
/ \ / \ / \ / \
X X X X X X X X
Düğüm: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Yaprak: 0 1 2 3 4 5 6 7
Şekil 32: Dizi Olarak Gösterilen Sekiz Üyeli Bir Ağaç
Bu sayede, ağaç düğümleri arasındaki ilişkileri, bellekte karmaşık yapılar tutmak yerine yalnızca indisler üzerinde işlem yaparak hesaplayabiliriz. Temel kural, ebeveyn ve çocuk düğüm indislerinin yüksek sıralı bitleri arasında aşağıdaki ilişkinin bulunmasıdır (burada x rastgele bir bit dizisidir):
parent=01x => left=00x, right=10x
Düğüm ilişkileri örtük olduğundan, ağacın sağ kenarına düğüm ekleme ve sağ kenardan düğüm kaldırma algoritmaları oldukça basittir. Dizide N düğüm varsa:
Ekle: Dizinin sonuna N + 1 adet boş değer ekle.
Kaldır: Diziyi ilk (N-1) / 2 girişine kadar kısalt.
Aşağıdaki Python kodu, MLS için dizi tabanlı bir ağacı kullanmak adına gerekli ağaç hesaplamalarını göstermektedir.
# x'ten küçük olan en büyük 2 kuvvetinin üssü. Şuna eşdeğerdir:
# int(math.floor(math.log(x, 2)))
def log2(x):
if x == 0:
return 0
k = 0
while (x >> k) > 0:
k += 1
return k-1
# Ağaçtaki bir düğümün seviyesi. Yapraklar seviye 0'dır, ebeveynleri
# seviye 1'dir, vb. Bir düğümün çocukları farklı seviyelerdeyse,
# düğümün seviyesi çocuklarının en yüksek seviyesinin bir fazlasıdır.
def level(x):
if x & 0x01 == 0:
return 0
k = 0
while ((x >> k) & 0x01) == 1:
k += 1
return k
# n yapraklı bir ağacı göstermek için gereken düğüm sayısı.
def node_width(n):
if n == 0:
return 0
else:
return 2*(n - 1) + 1
# n yapraklı bir ağacın kök düğümünün indisi.
def root(n):
w = node_width(n)
return (1 << log2(w)) - 1
# Bir ara düğümün sol çocuğu.
def left(x):
k = level(x)
if k == 0:
raise Exception('yaprak düğümün çocuğu yok')
return x ^ (0x01 << (k - 1))
# Bir ara düğümün sağ çocuğu.
def right(x):
k = level(x)
if k == 0:
raise Exception('yaprak düğümün çocuğu yok')
return x ^ (0x03 << (k - 1))
# Bir düğümün ebeveyni.
def parent(x, n):
if x == root(n):
raise Exception('kök düğümün ebeveyni yok')
k = level(x)
b = (x >> (k + 1)) & 0x01
return (x | (1 << k)) ^ (b << (k + 1))
# Düğümün ebeveyninin diğer çocuğu.
def sibling(x, n):
p = parent(x, n)
if x < p:
return right(p)
else:
return left(p)
# Bir düğümün yapraktan köke sıralı doğrudan yolu.
def direct_path(x, n):
r = root(n)
if x == r:
return []
d = []
while x != r:
x = parent(x, n)
d.append(x)
return d
# Bir düğümün yapraktan köke sıralı eş yolu.
def copath(x, n):
if x == root(n):
return []
d = direct_path(x, n)
d.insert(0, x)
d.pop()
return [sibling(y, n) for y in d]
# İki düğümün ortak atası, her iki yaprağın da doğrudan yolunda yer
# alan en alt düğümdür.
def common_ancestor_semantic(x, y, n):
dx = set([x]) | set(direct_path(x, n))
dy = set([y]) | set(direct_path(y, n))
dxy = dx & dy
if len(dxy) == 0:
raise Exception('ortak ata bulunamadı')
return min(dxy, key=level)
# İki düğümün ortak atası, her iki yaprağın da doğrudan yolunda yer
# alan en alt düğümdür.
def common_ancestor_direct(x, y, _):
# Biri diğerinin atasıysa bu durumları ele al
lx, ly = level(x)+1, level(y)+1
if (lx <= ly) and (x>>ly == y>>ly):
return y
elif (ly <= lx) and (x>>lx == y>>lx):
return x
# Diğer durumları ele al
xn, yn = x, y
k = 0
while xn != yn:
xn, yn = xn >> 1, yn >> 1
k += 1
return (xn << k) + (1 << (k-1)) - 1