Вращение узлов дерева AVL не работает

Question

Я пытаюсь написать дерево AVL в python, но вращение не работает, потому что я не могу поменять «сам» узел каким-либо другим. Есть ли способ исправить это? Я думаю, что делать это в Java или C, как это не правильно ...

class Sentinel(object): 
    value = left = right = None 
    height = -1 

sentinel = Sentinel() #singleton of sentinel node 

class Node:  
def __init__(self, data, left=sentinel, right=sentinel, height=0): 
    self.data = data 
    self.left = left 
    self.right = right 
    self.height = height 

def addNode(self, data): 
    if self.data == data: 
     #return when node duplicated 
     return 
    isLeft = self.data > data 
    child = self.left if isLeft else self.right 

    if child is sentinel: 
     if isLeft: 
      self.left = Node(data) 
     else: 
      self.right = Node(data) 
    else: 
     child.addNode(data) 
     if abs(child.right.height - child.left.height) == 2: 
      print("Rebalancing after inserting", data) 
      ''' Then we need to balance a subtree''' 
      if data < child.data: 
       rotation = self.rotateLeft if isLeft else self.rotateRight 
      else: 
       rotation = self.doubleRotateLeft if isLeft else self.doubleRotateRight 
      rotation() 
      self.left.setHeight() if isLeft else self.right.setHeight() 
     self.setHeight() 

def printNodes(self): 
    if self.left is not sentinel: 
     self.left.printNodes() 
    print(self) 
    if self.right is not sentinel: 
     self.right.printNodes() 


def setHeight(self): 
    self.height = max(self.left.height, self.right.height) + 1 

def rotateRight(self): 
    new_root = self.left 
    new_left_sub = new_root.right 
    old_root = self 
    self = new_root 
    old_root.left = new_left_sub 
    new_root.right = old_root 

def rotateLeft(self): 
    new_root = self.right 
    new_left_sub = new_root.left 
    old_root = self 
    self = new_root 
    old_root.right = new_left_sub 
    new_root.left = old_root 

def doubleRotateRight(self): 
    return 

def doubleRotateLeft(self): 
    return 

def __str__(self): 
    return str(self.data) 

class binaryTree: 

def __init__(self): 
    self.root = sentinel 

def add(self, data): 
    print("Before adding", data) 
    self.printAll() 
    if self.root is sentinel: 
     self.root = Node(data) 
    else: 
     self.root.addNode(data) 


def printAll(self): 
    if self.root is sentinel: 
     print("Empty tree") 
    else: 
     self.root.printNodes() 

if __name__ == '__main__': 
b = binaryTree() 
b.add(1) 
b.add(22) 
b.add(4) 
b.add(26) 
b.add(13) 
b.add(3) 
b.add(14) 
b.add(6) 
b.add(13) 
b.add(5) 
b.add(36) 
b.add(43) 
b.add(5) 
for i in range(1, 20): 
    b.add(i) 
b.printAll() 

Answer 1

Я хотел бы предложить, что ваши узлы содержат ссылку на родительский (корень, имеющий в качестве одного из родителей). Тогда его легко:

def rotateLeft(self): 
    new_root = self.right 
    new_left_sub = new_root.left 
    old_root = self 

    self.parent.right = new_root #assuming self is a right child 
    old_root.right = new_left_sub 
    new_root.left = old_root 

Мой код не может быть правильным, я не могу проверить это прямо сейчас, но идея: есть узлы сохранить ссылку на родителя.

Некоторые ссылки: http://interactivepython.org/runestone/static/pythonds/Trees/AVLTreeImplementation.html