AVL 트리 기본 작업
34502 단어 데이터 구조와 알고리즘
public class AVLTree {
public static class Node {
public int data;
public int height;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
this.height = 1;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", height=" + height +
'}';
}
}
public int heightOf(Node node) {
return node == null ? 0 : node.height;
}
public int balanceOf(Node node) {
return node == null ? 0 : heightOf(node.left) - heightOf(node.right);
}
public Node rotateLeft(Node node) {
Node rightNode = node.right;
node.right = rightNode.left;
rightNode.left = node;
node.height = Math.max(heightOf(node.left), heightOf(node.right)) + 1;
rightNode.height = Math.max(heightOf(rightNode.left), heightOf(rightNode.right)) + 1;
return rightNode;
}
public Node rotateRight(Node node) {
Node leftNode = node.left;
node.left = leftNode.right;
leftNode.right = node;
node.height = Math.max(heightOf(node.left), heightOf(node.right)) + 1;
leftNode.height = Math.max(heightOf(leftNode.left), heightOf(leftNode.right)) + 1;
return leftNode;
}
public Node insert(Node root, int data) {
if (root == null) {
return new Node(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;
}
root.height = Math.max(heightOf(root.left), heightOf(root.right)) + 1;
int balance = balanceOf(root);
//check balance
//LL
if (balance > 1 && data < root.left.data) {
return rotateRight(root);
}
//RR
if (balance < -1 && data > root.right.data) {
return rotateLeft(root);
}
//LR
if (balance > 1 && data > root.left.data) {
root.left = rotateLeft(root.left);
return rotateRight(root);
}
//RL
if (balance < -1 && data < root.right.data) {
root.right = rotateRight(root.right);
return rotateLeft(root);
}
return root;
}
public Node delete(Node root, int 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) {
Node temp = null;
if (root.left != null) {
temp = root.left;
} else if (root.right != null) {
temp = root.right;
}
root = temp;
} else {
Node minNode = minValueNode(root.right);
root.data = minNode.data;
root.right = delete(root.right, minNode.data);
}
}
if (root == null) {
return root;
}
root.height = Math.max(heightOf(root.left), heightOf(root.right)) + 1;
int rootBalance = balanceOf(root);
int leftBalance = balanceOf(root.left);
int rightBalance = balanceOf(root.right);
//check balance of root
if (rootBalance > 1 && leftBalance >= 0) {
root = rotateRight(root);
}
if (rootBalance > 1 && leftBalance < 0) {
root.left = rotateLeft(root.left);
root = rotateRight(root);
}
if (rootBalance < -1 && rightBalance <= 0) {
root = rotateLeft(root);
}
if (rootBalance < -1 && rightBalance > 0) {
root.right = rotateRight(root.right);
root = rotateLeft(root);
}
return root;
}
public Node minValueNode(Node root) {
while (root.left != null) {
root = root.left;
}
return root;
}
public void printTreeInOrder(Node root) {
if (root != null) {
printTreeInOrder(root.left);
System.out.println(root.data);
printTreeInOrder(root.right);
}
}
public Node search(Node root, int data) {
if (root == null) {
return null;
}
if (data < root.data) {
return search(root.left, data);
} else if (data > root.data) {
return search(root.right, data);
} else {
return root;
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
Node root = null;
//create
for (int i = 1; i <= 100; i++) {
root = tree.insert(root, i);
}
//search
Node targetNode = tree.search(root, 50);
System.out.println("search result:" + targetNode);
//delete
tree.delete(root, 50);
tree.delete(root, 5);
tree.printTreeInOrder(root);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.