Bir uygulama, ratchet ağaçlarını "bağlantı tabanlı" bir gösterimle saklamayı tercih edebilir; bu gösterimde her düğüm, ebeveynlerine veya çocuklarına referanslar saklar. Bu yaklaşım, yukarıda önerilen ve bu ilişkilerin dizi içindeki düğüm indislerinden hesaplandığı dizi tabanlı gösterimin tersidir. Böyle bir uygulamanın, ağacın yeni üyeler eklenerek genişletilmesi veya üyeler kaldırıldığında kısaltılması sırasında dengeli yapıyı korumak için bu bağlantıları güncellemesi gerekir.
Aşağıdaki kod parçası, bu algoritmaların Python'da nasıl uygulanabileceğini göstermektedir.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value # Düğümün değeri
self.left = left # Sol çocuk düğüm
self.right = right # Sağ çocuk düğüm
@staticmethod
def blank_subtree(depth):
if depth == 1:
return Node(None)
L = Node.blank_subtree(depth-1)
R = Node.blank_subtree(depth-1)
return Node(None, left=L, right=R)
def empty(self):
L_empty = (self.left == None) or self.left.empty()
R_empty = (self.right == None) or self.right.empty()
return (self.value == None) and L_empty and R_empty
class Tree:
def __init__(self):
self.depth = 0 # Ağacın derinliği
self.root = None # Kök düğüm; başlangıçta boştur
# Sağa boş bir alt ağaç ekle
def extend(self):
if self.depth == 0:
self.depth = 1
self.root = Node(None)
L = self.root
R = Node.blank_subtree(self.depth)
self.root = Node(None, left=L, right=R)
self.depth += 1
# Sağ alt ağacı kısalt
def truncate(self):
if self.root == None:
return
if not self.root.right.empty():
raise Exception("boş olmayan alt ağaç kısaltılamaz")
self.depth -= 1
self.root = self.root.left