データ構造学習のバランスツリーとAVL編(Java)
49508 ワード
バランスツリー:任意のノードに対して、左サブツリーと右サブツリーの高さ差は1バランス因子を超えてはならない:任意のノードの左サブツリーと右サブツリーの高さ差.AVLツリーはバランスツリーの一種で、AVLツリー自体はまず1本のツリーである.二分探索ツリーは、挿入されたデータが規則的である場合、二分探索ツリーが最も悪い場合にチェーンテーブルに劣化する可能性があるからである.このようなデータ構造を用いてデータを処理する意味が失われる.そこでAVLという自己平衡二叉ルックアップツリーが最初に発明された.AVLツリーは高さバランスツリーとも呼ばれ、追加と削除は1回または複数回ツリーを回転させることでこのツリーを再バランスさせる必要がある場合があります.Javaを使用してAVLTreeを実装するには:
import java.util.ArrayList;
/**
* @author ymn
* @version 1.0
* @date 2020\6\2 0002
*/
public class AVLTree<K extends Comparable<K>,V> {
private class Node{
public K key;
public V value;
public Node left,right;
public int height;
public Node(K key,V value){
this.key = key;
this.value = value;
left = null;
right = null;
height = 1;
}
}
private Node root;
private int size;
public AVLTree(){
root = null;
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
//
public boolean isBST(){
//
ArrayList<K> keys = new ArrayList<>();
inOrder(root,keys);
for (int i = 1;i < keys.size(); i++){
if (keys.get(i - 1).compareTo(keys.get(i)) > 0){
return false;
}
}
return true;
}
//
private void inOrder(Node node,ArrayList<K> keys){
if (node == null)
return;
inOrder(node.left,keys);
keys.add(node.key);
inOrder(node.right,keys);
}
//
public boolean isBalanced(){
return isBalanced(root);
}
// node ，
private boolean isBalanced(Node node){
if (node == null){
return true;
}
int balanceFactor = getBalanceFactor(node);
//Math.abs
if (Math.abs(balanceFactor) > 1){
return false;
}
return isBalanced(node.left) && isBalanced(node.right);
}
// y ， x
private Node rightRotate(Node y){
Node x = y.left;
Node xRight = x.right;
//
x.right = y;
y.left = xRight;
// height
y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
return x;
}
// y ， x
private Node leftRotate(Node y){
Node x = y.right;
Node xLeft = x.left;
//
x.left = y;
y.left = xLeft;
// height
y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
return x;
}
//
private int getHeight(Node node){
if (node == null){
return 0;
}
return node.height;
}
//
private int getBalanceFactor(Node node){
if (node == null){
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
public void add(K key,V value){
root = add(root,key,value);
}
// node (key,value),
//
private Node add(Node node,K key,V value){
if(node == null){
size ++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0){
node.left = add(node.left,key, value);
}else if(key.compareTo(node.key) > 0){ //
node.right = add(node.right,key, value);
}else {
node.value = value;
}
// height
node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
//
int balanceFactor = getBalanceFactor(node);
// if (Math.abs(balanceFactor) > 1){
// System.out.println("unbalanced" + balanceFactor);
// }
//
//LL
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
return rightRotate(node);
//RR
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
return leftRotate(node);
//LR
if(balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
//
node.left = leftRotate(node.left);
//
return rightRotate(node);
}
//RL
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0){
//
node.right = rightRotate(node.right);
//
return leftRotate(node);
}
return node;
}
// node ，key
private Node getNode(Node node,K key){
if (node == null){
return null;
}
if (key.compareTo(node.key) == 0){
return node;
}else if (key.compareTo(node.key) < 0){
return getNode(node.left,key);
}else { //key.compareTo(node.key) > 0
return getNode(node.right,key);
}
}
public boolean contains(K key){
return getNode(root,key) != null;
}
public V get(K key){
Node node = getNode(root,key);
return node == null ? null : node.value;
}
public void set(K key, V value) {
Node node = getNode(root,key);
if (node == null){
throw new IllegalArgumentException(key + "dose't exist!");
}
node.value = value;
}
// node ,
private Node minimum(Node node){
if (node.left == null){
return node;
}
return minimum(node.left);
}
public V remove(K key){
Node node = getNode(root,key);
if (node != null){
root = remove(root,key);
return node.value;
}
return null;
}
// node e ，
//
private Node remove(Node node,K key){
if (node == null){
return null;
}
Node returnNode;
if (key.compareTo(node.key) < 0){
node.left = remove(node.left,key);
returnNode = node;
}else if (key.compareTo(node.key) > 0){
node.right = remove(node.right,key);
returnNode = node;
}
else { //key == node.key
//
if (node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
returnNode = rightNode;
}
//
else if (node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
returnNode = leftNode;
}
else {
//
// , ( )。
// ， ( ）
//
Node successor = minimum(node.right);
successor.right = remove(node.right, successor.key);
successor.left = node.left;
node.left = null;
node.right = null;
returnNode = successor;
}
}
// returnNode ，
if (returnNode == null){
return null;
}
// height
returnNode.height = 1 + Math.max(getHeight(returnNode.left),getHeight(returnNode.right));
//
int balanceFactor = getBalanceFactor(returnNode);
//
//LL
if (balanceFactor > 1 && getBalanceFactor(returnNode.left) >= 0)
return rightRotate(returnNode);
//RR
if (balanceFactor < -1 && getBalanceFactor(returnNode.right) <= 0)
return leftRotate(returnNode);
//LR
if(balanceFactor > 1 && getBalanceFactor(returnNode.left) < 0) {
//
returnNode.left = leftRotate(returnNode.left);
//
return rightRotate(returnNode);
}
//RL
if (balanceFactor < -1 && getBalanceFactor(returnNode.right) > 0){
//
returnNode.right = rightRotate(returnNode.right);
//
return leftRotate(returnNode);
}
return returnNode;
}
}