Я реализую дерево AVL в Python. У меня есть две модификации, которые я хочу сделать: ⇐ Python

[Anonymous]

Я работаю над деревом AVL в Python и хочу внести два изменения:

Коэффициент обратной балансировки
Обычно коэффициент балансировки дерева AVL рассчитывается как:

высота левого поддерева − высота правого поддерева.

• Положительный = left-heavy
• Отрицательное значение = right-heavy

Я хочу перевернуть это, чтобы получилось:

высота правого поддерева − высота левого поддерева.
Вопросы:

• Как можно Я безопасно меняю коэффициент баланса?
• После его изменения нужно ли мне менять правила ротации (LL, LR, RR, RL)?
• Есть ли проблемы или побочные эффекты, с которыми мне следует быть осторожными?

Обработка повторяющихся значений
В настоящее время повторяющиеся значения игнорируются. Я хочу, чтобы все повторяющиеся значения попадали в правое поддерево.
Вопросы:

• Безопасно ли это для дерева AVL?
• Повлияет ли это на баланс или эффективность дерева?
• Есть ли лучший способ обработки дубликатов?

Цель:
Я хочу, чтобы оба изменения работали вместе:

• Коэффициент баланса — вправо–влево.
• Дубликаты всегда идут вправо.

class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1

def getHeight(node):
if not node:
return 0
return node.height

def getBalance(node):
if not node:
return 0
return getHeight(node.left) - getHeight(node.right)

def rightRotate(y):
print('Rotate right on node',y.data)
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(getHeight(y.left), getHeight(y.right))
x.height = 1 + max(getHeight(x.left), getHeight(x.right))
return x

def leftRotate(x):
print('Rotate left on node',x.data)
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = 1 + max(getHeight(x.left), getHeight(x.right))
y.height = 1 + max(getHeight(y.left), getHeight(y.right))
return y

def insert(node, data):
if not node:
return TreeNode(data)

if data < node.data:
node.left = insert(node.left, data)
elif data > node.data:
node.right = insert(node.right, data)

# Update the balance factor and balance the tree
node.height = 1 + max(getHeight(node.left), getHeight(node.right))
balance = getBalance(node)

# Balancing the tree
# Left Left
if balance > 1 and getBalance(node.left) >= 0:
return rightRotate(node)

# Left Right
if balance > 1 and getBalance(node.left) < 0:
node.left = leftRotate(node.left)
return rightRotate(node)

# Right Right
if balance < -1 and getBalance(node.right) 0:
node.right = rightRotate(node.right)
return leftRotate(node)

return node

def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)

# Inserting nodes
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
root = insert(root, letter)

inOrderTraversal(root)

#Python


Подробнее здесь: https://stackoverflow.com/questions/798 ... nt-to-make