Trình chỉnh sửa thử của Example.com.vn

Python

Java

lớp TreeNode: def __init__(self, data): self.data = dữ liệu self.left = Không có self.right = Không có self.height = 1 def getHeight(node): nếu không phải nút: return 0 return node.height def getBalance( nút): nếu không phải nút: 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)) trả về y def Insert(node, data): nếu không phải nút: trả về TreeNode(data) nếu dữ liệu < node.data: node.left = Insert(node.left , data) dữ liệu elif > node.data: node.right = Insert(node.right, data) node.height = 1 + max(getHeight(node.left), getHeight(node.right)) Balance = getBalance(node) # Trái Trái nếu cân bằng > 1 và dữ liệu < node.left.data: return rightRotate(node) # Phải Phải nếu cân bằng < -1 và dữ liệu > node.right.data: return leftRotate(node) # Left Right nếu cân bằng > 1 và dữ liệu > node.left.data: node.left = leftRotate(node.left) return rightRotate(node) # Right Left nếu số dư < -1 và data < node.right.data: node.right = rightRotate(node.right ) return leftRotate(node) return node def inOrderTraversal(node): nếu nút là None: return inOrderTraversal(node.left) print(node.data, end=", ") inOrderTraversal(node.right) def minValueNode(node): current = node trong khi current.left không phải None: current = current.left trả về hiện tại def minValueNode(node): current = node trong khi current.left không None: current = current.left trả về hiện tại def delete(node, data): nếu không phải nút: trả về nút nếu dữ liệu < node.data: node.left = delete(node.left, data) dữ liệu elif > node.data: node.right = delete(node.right, data) else: if node.left là Không có: temp = node.right nút = Không có return temp elif node.right là Không có: temp = node.left node = Không return temp = minValueNode(node.right) node.data = temp.data node.right = delete (node.right, temp.data) nếu nút là Không: trả về nút # Cập nhật hệ số cân bằng và cân bằng cây node.height = 1 + max(getHeight(node.left), getHeight(node.right)) Balance = getBalance (node) # Cân bằng cây # Trái trái nếu số dư > 1 và getBalance(node.left) >= 0: return rightRotate(node) # Left Right nếu số dư > 1 và getBalance(node.left) < 0: node.left = leftRotate(node.left) return rightRotate(node) # Right Right nếu số dư < -1 và getBalance(node.right) <= 0: return leftRotate(node) # Right Left nếu số dư < -1 và getBalance(node.right) ) > 0: node.right = rightRotate(node.right) return leftRotate(node) return node # Chèn các chữ cái root = Không có chữ cái nào = ['C', 'B', 'E', 'A', 'D' , 'H', 'G', 'F'] cho chữ cái trong các chữ cái: root = Insert(root, letter) inOrderTraversal(root) print('\nDeleting A') root = delete(root,'A') inOrderTraversal( gốc) #Python

#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int data; struct TreeNode *trái; struct TreeNode *đúng; chiều cao int; } Nút cây; int max(int a, int b) { return (a > b) ? một: b; } int getHeight(TreeNode *N) { if (N == NULL) return 0; trả về N->chiều cao; } TreeNode* newNode(int data) { TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode)); nút->dữ liệu = dữ liệu; nút->trái = NULL; nút->phải = NULL; nút-> chiều cao = 1; // nút mới ban đầu được thêm vào tại lá return(node); } TreeNode *rightRotate(TreeNode *y) { TreeNode *x = y->left; TreeNode *T2 = x->phải; x->phải = y; y->trái = T2; y->height = max(getHeight(y->left), getHeight(y->right)) + 1; x->height = max(getHeight(x->left), getHeight(x->right)) + 1; trả lại x; } TreeNode *leftRotate(TreeNode *x) { TreeNode *y = x->right; TreeNode *T2 = y->left; y->trái = x; x->phải = T2; x->height = max(getHeight(x->left), getHeight(x->right)) + 1; y->height = max(getHeight(y->left), getHeight(y->right)) + 1; trả lại y; } int getBalance(TreeNode *N) { if (N == NULL) return 0; return getHeight(N->left) - getHeight(N->right); } TreeNode* Insert(TreeNode* node, int data) { if (node == NULL) return(newNode(data)); if (dữ liệu < nút-> dữ liệu) nút-> left = chèn (nút-> trái, dữ liệu); ngược lại nếu (dữ liệu > nút-> dữ liệu) nút-> bên phải = chèn (nút-> bên phải, dữ liệu); else // Dữ liệu bằng nhau không được phép trong nút trả về BST; nút->height = 1 + max(getHeight(nút->left), getHeight(nút->phải)); int Balance = getBalance(nút); // Left Left Case if (balance > 1 && data < node->left->data) return rightRotate(node); // Right Right Case if (cân bằng < -1 && data > node->right->data) return leftRotate(node); // Chữ trái phải if (balance > 1 && data > node->left->data) { node->left = leftRotate(node->left); return rightRotate(nút); } // Trường hợp bên phải bên trái if (cân bằng < -1 && dữ liệu < node->right->data) { node->right = rightRotate(node->right); return leftRotate(node); } nút trả về; } TreeNode * minValueNode(nút TreeNode*) { TreeNode* current = node; while (current->left != NULL) current = current->left; trở lại hiện tại; } void inOrderTraversal(TreeNode *root) { if (root != NULL) { inOrderTraversal(root->left); printf("%c", root->data); inOrderTraversal(root->right); } } TreeNode* deleteNode(TreeNode* root, int data) { if (root == NULL) return root; // Xóa BST tiêu chuẩn if (data < root->data) root->left = deleteNode(root->left, data); ngược lại nếu (dữ liệu > root->data) root->right = deleteNode(root->right, data); else { if ((root->left == NULL) || (root->right == NULL)) { TreeNode *temp = root->left ? root->left : root->right; if (temp == NULL) { temp = root; gốc = NULL; } else *root = *temp; miễn phí (tạm thời); } else { TreeNode* temp = minValueNode(root->right); gốc->dữ liệu = temp->dữ liệu; root->right = deleteNode(root->right, temp->data); } } if (root == NULL) trả về root; root->height = 1 + max(getHeight(root->left), getHeight(root->right)); int Balance = getBalance(root); // Left Left Case if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Chữ trái phải 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); // Chữ trái phải if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } trả về gốc; } int main() { TreeNode *root = NULL; chữ char[] = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'}; int n = sizeof(chữ cái) / sizeof(chữ cái[0]); for (int i = 0; i < n; i++) { root = Insert(root, Letters[i]); } inOrderTraversal(root); printf("\nXóa 'A'\n"); root = deleteNode(root, 'A'); inOrderTraversal(root); trả về 0; } //C

lớp công khai Chính { lớp tĩnh AVLtree { lớp TreeNode { dữ liệu char; TreeNode trái, phải; chiều cao int; TreeNode(char d) { data = d; chiều cao = 1; } } Gốc TreeNode; chiều cao int riêng tư (TreeNode N) { if (N == null) trả về 0; trả về N.height; } riêng tư int getBalance(TreeNode N) { if (N == null) return 0; chiều cao trả về(N.left) - chiều cao(N.right); } riêng 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; trả lại x; } riêng tư 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; trả lại y; } Chèn TreeNode (nút TreeNode, dữ liệu char) { if (nút == null) trả về TreeNode mới (dữ liệu); if (dữ liệu < node.data) node.left = Insert(node.left, data); ngược lại nếu (dữ liệu > node.data) node.right = Insert(node.right, data); nút trả về khác; node.height = 1 + Math.max(height(node.left), Height(node.right)); int Balance = getBalance(nút); // Left Left Case if (balance > 1 && data < node.left.data) return rightRotate(node); // Phải Trường hợp bên phải if (cân bằng < -1 && data > node.right.data) return leftRotate(node); // Chữ trái phải if (balance > 1 && data > node.left.data) { node.left = leftRotate(node.left); return rightRotate(nút); } // Trường hợp bên phải bên trái if (cân bằng < -1 && dữ liệu < node.right.data) { node.right = rightRotate(node.right); return leftRotate(node); } nút trả về; } Private TreeNode minValueNode(TreeNode node) { TreeNode current = node; while (current.left != null) { current = current.left; } trả về dòng điện; } TreeNode delete(TreeNode root, char data) { if (root == null) return root; if (dữ liệu < root.data) root.left = delete(root.left, data); ngược lại nếu (dữ liệu > root.data) root.right = delete(root.right, data); else { if ((root.left == null) || (root.right == null)) { TreeNode temp = null; if (temp == root.left) temp = root.right; khác temp = root.left; if (temp == null) { temp = root; gốc = null; } khác root = temp; } else { TreeNode temp = minValueNode(root.right); root.data = temp.data; root.right = xóa(root.right, temp.data); } } if (root == null) trả về 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); // Chữ trái phải if (balance > 1 && getBalance(root.left) < 0) { root.left = leftRotate(root.left); return rightRotate(root); } // Phải Phải Trường hợp if (balance < -1 && getBalance(root.right) <= 0) return leftRotate(root); // Chữ trái phải if (balance < -1 && getBalance(root.right) > 0) { root.right = rightRotate(root.right); return leftRotate(root); } trả về gốc; } void inOrderTraversal(nút TreeNode) { 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[] chữ cái = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'}; for (chữ char : chữ cái) { tree.root = tree.insert(tree.root, letter); } tree.inOrderTraversal(tree.root); System.out.println("\nXóa A"); tree.root = tree.delete(tree.root, 'A'); tree.inOrderTraversal(tree.root); } } } // Java