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): 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): 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) def minValueNode(node): current = node while current.left is not None: current = current.left return current def minValueNode(node): current = node while current.left is not None: current = current.left return current def delete(node, data): if not node: return node if data < node.data: node.left = delete(node.left, data) elif data > node.data: node.right = delete(node.right, data) else: if node.left is None: temp = node.right node = None return temp elif node.right is None: temp = node.left node = None return temp temp = minValueNode(node.right) node.data = temp.data node.right = delete(node.right, temp.data) if node is None: return node # 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 # Inserting the letters root = None letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'] for letter in letters: root = insert(root, letter) inOrderTraversal(root) print('\nDeleting A') root = delete(root,'A') inOrderTraversal(root) #Python
#include
#include
typedef struct TreeNode { char data; struct TreeNode* left; struct TreeNode* right; int height; } TreeNode; int getHeight(TreeNode* node) { if (!node) return 0; return node->height; } int getBalance(TreeNode* node) { if (!node) return 0; return getHeight(node->left) - getHeight(node->right); } 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) { TreeNode* x = y->left; TreeNode* T2 = x->right; x->right = y; y->left = T2; y->height = 1 + (getHeight(y->left) > getHeight(y->right) ? getHeight(y->left) : getHeight(y->right)); x->height = 1 + (getHeight(x->left) > getHeight(x->right) ? getHeight(x->left) : getHeight(x->right)); return x; } TreeNode* leftRotate(TreeNode* x) { TreeNode* y = x->right; TreeNode* T2 = y->left; y->left = x; x->right = T2; x->height = 1 + (getHeight(x->left) > getHeight(x->right) ? getHeight(x->left) : getHeight(x->right)); y->height = 1 + (getHeight(y->left) > getHeight(y->right) ? getHeight(y->left) : getHeight(y->right)); return y; } 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; } TreeNode* minValueNode(TreeNode* node) { TreeNode* current = node; while (current->left != NULL) current = current->left; return current; } TreeNode* delete(TreeNode* root, char data) { if (!root) return root; if (data < root->data) root->left = delete(root->left, data); else if (data > root->data) root->right = delete(root->right, data); else { if (root->left == NULL) { TreeNode* temp = root->right; free(root); return temp; } else if (root->right == NULL) { TreeNode* temp = root->left; free(root); return temp; } TreeNode* temp = minValueNode(root->right); root->data = temp->data; root->right = delete(root->right, temp->data); } if (root == NULL) return root; 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); printf("\nDeleting A\n"); root = delete(root, 'A'); 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; private int height(TreeNode N) { if (N == null) return 0; return N.height; } private int getBalance(TreeNode N) { if (N == null) return 0; return height(N.left) - height(N.right); } private TreeNode rightRotate(TreeNode y) { 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; } private TreeNode leftRotate(TreeNode x) { 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; } private TreeNode minValueNode(TreeNode node) { TreeNode current = node; while (current.left != null) { current = current.left; } return current; } TreeNode delete(TreeNode root, char data) { if (root == null) { return root; } if (data < root.data) { root.left = delete(root.left, data); } else if (data > root.data) { root.right = delete(root.right, data); } else { if ((root.left == null) || (root.right == null)) { TreeNode temp = root.left != null ? root.left : root.right; if (temp == null) { root = null; } else { root = temp; } } else { TreeNode temp = minValueNode(root.right); root.data = temp.data; root.right = delete(root.right, temp.data); } } if (root == null) { return root; } root.height = Math.max(height(root.left), height(root.right)) + 1; 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); System.out.println("\nDeleting A"); tree.root = tree.delete(tree.root, 'A'); tree.inOrderTraversal(tree.root); } } } // Java
Python result:
C result:
Java result:
A, B, C, D, E, F, G, H,
Deleting A
B, C, D, E, F, G, H,
A B C D E F G H
Deleting A
B C D E F G H
A, B, C, D, E, F, G, H,
Deleting A
B, C, D, E, F, G, H,