[Python] I am implementing an AVL Tree in Python. I have two modifications I want to make:

I am working on an AVL Tree in Python and I want to make two changes:


1️⃣ Reverse balancing factor

Normally, the AVL Tree balance factor is calculated as:
left subtree height − right subtree height.

• 
  Positive = left-heavy
  
  
• 
  Negative = right-heavy
  

I want to reverse this, so it becomes:
right subtree height − left subtree height.

Questions:

• 
  How can I safely change the balance factor?
  
  
• 
  After changing it, do I need to change rotation rules (LL, LR, RR, RL)?
  
  
• 
  Any problems or side effects I should be careful about?
  

2️⃣ Handle duplicate values

Right now, duplicate values are ignored. I want all duplicate values to go into the right subtree.

Questions:

• 
  Is this safe for an AVL Tree?
  
  
• 
  Will it affect the balance or efficiency of the tree?
  
  
• 
  Is there a better way to handle duplicates?
  

Goal:

I want both changes to work together:

1. 
   Balance factor is right − left.
   
   
2. 
   Duplicates always go to the right.
   

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:
return leftRotate(node)

# Right Left
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

Continue reading...