Aşağıdaki gibi bir ikili ağacı göz önüne alalım. Bu örnek üzerinden giderek köşeleri koordinatlayacağız. Sonra da uzaklık fonksiyonunu tanımlayacağız.
![](http://matkafasi.com/?qa=blob&qa_blobid=4608845398228810476)
Ağacın başlangıç noktası olan A köşesini 0 olarak koodinatlayalım. Diğer noktaları ise, A ya göre ya sağ tarafta ya da sol tarafta kalacak biçimde L (left), R (right) harfleriyle kodlayacağız. Örneğin H noktası için üç kez sola gidildiği için H=0LLL dizesini kullanacağız. E noktası için önce sola sonra sağa gidildiği için E=0LR dizesini kullanacağız. İlk bileşen hep 0 (sıfır) olacak. Benzer şekilde J=0RLL ve N=0RRLL olur.
Tüm koordinatlarının listesi verilmiş bir ikili ağaç belirlenmiş bir ağaçtır. Bu tür bir listenin bize sunulmuş olduğunu varsayalım, artık çizgenin resmine ihtiyacımız kalmayacaktır. (Eğer istersek, koordinatlar listesine bakarak çizgenin resmini de tekrar yapabiliriz.)
Küçük çizgelerde iki nokta arası mesafeyi, ayrıtları kullanarak sayabiliyoruz. Şekilde H ile E arasındaki mesafe 3 tür. Eğer kooddinatlar listesi verilmişse, iki nokta arasındaki mesafeyi Python kodu kullanarak yazabiliriz:
def d(x,y):
n = min(len(x),len(y))
noet = 0
for i in range(0,n):
if x[i]==y[i]:
noet = noet + 1
else:
break
return len(x) + len(y) - 2*noet
H = "0LLR"
N = "0RRLL"
d(H,N)
Bu şekilde tanımladığımız d(x,y) uzaklık fonksiyonunda; len(x), x noktasının A başlangıcına uzaklığının 1 fazlası veya eşdeğer olarak x in dize uzunluğu, m=x ve y dizelerindeki eşit olan ilk k terimin sayısı olmak üzere
M1. d(x,y)=len(x)+len(y)−2⋅m=(len(x)−m)+(len(y)−m)≥0.
M2. d(x,y)=0⟺len(x)−m=len(y)−m=0 olmalıdır. Bu ise x ve y dizelerinin aynı indisli tüm terimlerinin birbiriyle çakışması demektir. Yani x=y.
M3. d fonksiyonunun tanımından dolayı x ile y nin konumlarının değiştirilebilir olduğunu görüyoruz. Dolayısıyla simetri özelliği vardır ve d(x,y)=d(y,x) tir.
M4. d(x,y)=(len(x)−m1)+(len(y)−m1) dir. x ve y nin ilk m1 terimi çakışıyor, x ve z nin ilk m2 terimi çakışıyor, z ve y nin ilk m3 terimi çakışıyor, olsun.
d(x,z)+d(x,z)=(len(x)−m2)+(len(z)−m2)+(len(z)−m3)+(len(y)−m3)
olur.
d(x,z)+d(x,z)≥d(x,y) olduğunu kanıtlamak gerekiyor. Örnekler bunu destekliyor ve eşitsizlik sanki açık gibi görünüyor ama bu kısmın cebirsel ispatını tamamlamadım.
M4. de doğru ise, (doğru olmasını bekliyorum) d(x,y) fonksiyonu bir metrik oluşturur. Son kısmı beraberce biraz daha kurcalayabiliriz...
Ek Çabalar: Ağaç yapısını kullanırsak önceki paragrafta bahsettiğim "açık gibi" olan kısım "açık" hale dönüşüyor. d(x,y) ile x ile y arasındaki yolun uzunluğunu (kenarların sayısını) buluyoruz. Ağaç çizge ile çalıştığımız için bu tür bir yol tek türlü belirlidir. Farklı bir yolla daha ulaşım mümkün olsaydı, döngü oluşurdu. Ağaç çizgede ise döngü yoktur. x i y ye bağlayan yol bir alt ağaçtır ve mümkün olan en kısa yoldur. d(x,z)+d(z,y) ile önce x ten z ye gidiyoruz ve sonra da z den y ye geçiyoruz. Yine x ten y ye bir rota çizildiği için bu bir yürüyüş (walk) olur. Yürüyüş içinde tekrar geçilen noktalar olabilir. Böylece d(x,y)≤d(x,z)+d(z,y) üçgen eşitsizliği de sağlanır. d(x,y), ikili ağaç üzerinde bir metriktir.
Muhtemelen ağaç özellikleri kullanılarak M1, M2, M3 şartları daha kolayca açıklanabilir. Çözümü uzatmış olabilirim.