Run ❯
Get your
own
website
×
Change Orientation
Change Theme, Dark/Light
Go to Spaces
Python
C
Java
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
#include
#include
typedef struct TreeNode { char data; struct TreeNode *left, *right; int height; } TreeNode; int max(int a, int b) { return (a > b) ? a : b; } int getHeight(TreeNode* node) { if (!node) return 0; return node->height; } TreeNode* createNode(char data) { TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode)); node->data = data; node->left = NULL; node->right = NULL; node->height = 1; return(node); } TreeNode *rightRotate(TreeNode *y) { printf("Rotate right on node %c\n", y->data); TreeNode *x = y->left; TreeNode *T2 = x->right; x->right = y; y->left = T2; y->height = max(getHeight(y->left), getHeight(y->right)) + 1; x->height = max(getHeight(x->left), getHeight(x->right)) + 1; return x; } TreeNode *leftRotate(TreeNode *x) { printf("Rotate left on node %c\n", x->data); TreeNode *y = x->right; TreeNode *T2 = y->left; y->left = x; x->right = T2; x->height = max(getHeight(x->left), getHeight(x->right)) + 1; y->height = max(getHeight(y->left), getHeight(y->right)) + 1; return y; } int getBalance(TreeNode *N) { if (N == NULL) return 0; return getHeight(N->left) - getHeight(N->right); } TreeNode* insert(TreeNode* root, char data) { if (!root) return createNode(data); if (data < root->data) root->left = insert(root->left, data); else if (data > root->data) root->right = insert(root->right, data); root->height = 1 + (getHeight(root->left) > getHeight(root->right) ? getHeight(root->left) : getHeight(root->right)); int balance = getBalance(root); if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); if (balance > 1 && getBalance(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); } if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root); if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } void inOrderTraversal(TreeNode *root) { if (root != NULL) { inOrderTraversal(root->left); printf("%c ", root->data); inOrderTraversal(root->right); } } int main() { TreeNode *root = NULL; char letters[] = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'}; int n = sizeof(letters) / sizeof(letters[0]); for (int i = 0; i < n; i++) { root = insert(root, letters[i]); } inOrderTraversal(root); return 0; } //C
public class Main { static class AVLTree { class TreeNode { char data; TreeNode left, right; int height; TreeNode(char d) { data = d; height = 1; } } TreeNode root; int height(TreeNode N) { if (N == null) return 0; return N.height; } int getBalance(TreeNode N) { if (N == null) return 0; return height(N.left) - height(N.right); } TreeNode rightRotate(TreeNode y) { System.out.println("Rotate right on node " + y.data); TreeNode x = y.left; TreeNode T2 = x.right; x.right = y; y.left = T2; y.height = Math.max(height(y.left), height(y.right)) + 1; x.height = Math.max(height(x.left), height(x.right)) + 1; return x; } TreeNode leftRotate(TreeNode x) { System.out.println("Rotate left on node " + x.data); TreeNode y = x.right; TreeNode T2 = y.left; y.left = x; x.right = T2; x.height = Math.max(height(x.left), height(x.right)) + 1; y.height = Math.max(height(y.left), height(y.right)) + 1; return y; } TreeNode insert(TreeNode root, char data) { if (root == null) return new TreeNode(data); if (data < root.data) { root.left = insert(root.left, data); } else if (data > root.data) { root.right = insert(root.right, data); } else { return root; // Duplicate data is not allowed } root.height = 1 + Math.max(height(root.left), height(root.right)); int balance = getBalance(root); // Left Left Case if (balance > 1 && getBalance(root.left) >= 0) { return rightRotate(root); } // Left Right Case if (balance > 1 && getBalance(root.left) < 0) { root.left = leftRotate(root.left); return rightRotate(root); } // Right Right Case if (balance < -1 && getBalance(root.right) <= 0) { return leftRotate(root); } // Right Left Case if (balance < -1 && getBalance(root.right) > 0) { root.right = rightRotate(root.right); return leftRotate(root); } return root; } void inOrderTraversal(TreeNode node) { if (node != null) { inOrderTraversal(node.left); System.out.print(node.data + ", "); inOrderTraversal(node.right); } } } public static void main(String[] args) { AVLTree tree = new AVLTree(); char[] letters = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'}; for (char letter : letters) { tree.root = tree.insert(tree.root, letter); } tree.inOrderTraversal(tree.root); } } //Java
Python result:
C result:
Java result:
Rotate right on node H
A, B, C, D, E, F, G, H,
Rotate right on node H
A B C D E F G H
Rotate right on node H
A, B, C, D, E, F, G, H,