Javaベース-バランス二叉検索ツリー(AVLツリー)
三日間をかけて、ノートの木を描きました.やっとできたはずです.
まず一点の木の4種類の回転、シングルスピン、シングルスピン、双方向左回り、両方の右回りは大丈夫です.また、バランスツリーの追加機能は可能です.機能を削除しました.
まず一点の木の4種類の回転、シングルスピン、シングルスピン、双方向左回り、両方の右回りは大丈夫です.また、バランスツリーの追加機能は可能です.機能を削除しました.
package com.yc.tree;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
* @author wb
* @param
*
*
* （height balanced binary search tree） 1962 Adelson-Velskii
* Landis ， AVL 。AVL ： ； T ，TL TR
* ， ， T ：（1）TL TR ；（2）
* |hL - hR| <= 1， hL hR TL TR 。
*
* p， （TL） （TR） hL hR， BF(p) p
* （balance factory）。 hL - hR。 AVL ， -1 0 1，
* |hL - hR| < 2。
*
* （AVL ）。 30 2.
* 50 BF=1
* ││
* BF=-2 30────────┘└─────────70 BF=1
* │ │
* └──40 BF=1 BF=0 60──┘
* │
* BF=0 35───┘
* xx.xx
*
*
* ：
* AVL ， ，
* 。 1.5 log n
* ， AVL ， O(log n) 。
* Balanced BST e ： BBST ，
* e BBST ， 1； e BBST ，
* ； e BBST ， BBST e ，
* e BBST ， （+1） ， ：
* BBST -1（ ， 0，BBST ；
* BBST 0（ 、 ）： 1，BBST 1；
* BBST 1（ ）： BBST 1：
* ， ， 0， ；
* e BBST ， BBST e ， e BBST
* ， （+1） ， 。
*
* ：
* AVL ， 。
* log n ， AVL ， O(log n) 。
*
* （ ： ( privot )
* （ ）。
* pivot.BF >= 0
* （privot.left.BF >= 0 LL ）
* （privot.left.BF < 0 LR ）
*
* pivot.BF < 0
* （privot.right.BF >= 0 RL ）
* （privot.right.BF < 0 RR ）
* ） 。 ， 。
*
*
* ：
* AVL BST ， O(log n) ， AVL 。
* ， 。（ ， 。）
*/
public class HeightBalanBinSearchTree >{
private static final int LEFT_HEAVY = -1;
private static final int BALANCED = 0;
private static final int RIGHT_HEAVY = 1;
private static final int RIGHT_RIGHT_HEAVY = 2;
private static final int LEFT_LEFT_HEAVY = -2;
public class AVLNode {
//
int balanceFactory;
T data;
AVLNode left;
AVLNode right;
//
AVLNode parent;
public AVLNode(int balanceFactory, T data, AVLNode left, AVLNode right, AVLNode parent){
this.balanceFactory = balanceFactory;
this.data = data;
this.left = left;
this.right = right;
this.parent = parent;
}
public String toString(){
return "[BF=" + balanceFactory + ",data=" + data + "]";
}
}
//avl
private AVLNode root;
public HeightBalanBinSearchTree(){
}
public HeightBalanBinSearchTree(T data){
root = new AVLNode(BALANCED, data, null, null, null);
}
/**
* AVL data
* @param data
*/
public void add(T data){
if(root == null){
root = new AVLNode(BALANCED, data, null, null, null);
}else{
AVLNode current = root;
AVLNode parent = null;
int imp = 0;
do{
parent = current;
imp = data.compareTo(current.data);
if(imp > 0){
current = current.right;
}else{
current = current.left;
}
}while(current != null);
AVLNode newNode = new AVLNode(BALANCED, data, null, null, parent);
if(imp > 0){
parent.right = newNode;
}else{
parent.left = newNode;
}
//
reBalacedForAdd(newNode);
}
}
/**
*
* @param data
*/
public void remove(T data){
AVLNode delNode = getAVLNode(data);
reBalacedForRemove(delNode);
}
//
private void reBalacedForRemove(AVLNode target){
if(target == null){//
return;
}
if(target.left == null && target.right == null){// 、 ( )
if(target == root){
root = null;
}else{
reBalacedForRemoveHelp(target);
if(target == target.parent.left){
target.parent.left = null;
}else{
target.parent.right = null;
}
//
target.parent = null;
}
}else if(target.left != null && target.right == null){ // ( ， )
//
if(root == target){
root = target.left;
target.left.parent = null; //
}
else{
//
if(target == target.parent.left){
target.parent.left = target.left;
}else{
target.parent.right = target.left;
}
target.left.parent = target.parent; // （ ， ， ）
reBalacedForRemoveHelp(target.left);
target.parent = target.left = target.right = null;
}
}else if(target.right != null && target.left == null){ //
if(root == target){
root = target.right;
target.right.parent = null; //
}
else{
if(target == target.parent.left){
target.parent.left = target.right;
}else{
target.parent.right = target.right;
}
target.right.parent = target.parent;
reBalacedForRemoveHelp(target.right);
target.parent = target.left = target.right = null;
}
}else if(target.left != null && target.right != null){ // ，
if(root == target){
AVLNode leftMaxNode = target.left;
while(leftMaxNode.right != null){
leftMaxNode = leftMaxNode.right;
}
root = leftMaxNode;
if(target.left.data.equals(leftMaxNode.data)){
leftMaxNode.right = target.right;
target.right.parent = leftMaxNode;//jia
leftMaxNode.parent = null;
target.right = target.parent = target.left = null;
leftMaxNode.balanceFactory = target.balanceFactory - 1;
reBalacedForRemoveHelpAndHelp(leftMaxNode);
}else{
AVLNode tmpNode = new AVLNode(0,null,leftMaxNode.left,null,leftMaxNode.parent);
leftMaxNode.parent.right = tmpNode;
leftMaxNode.left = target.left;
leftMaxNode.right = target.right;
//leftMaxNode.balanceFactory = target.balanceFactory;
target.left.parent = leftMaxNode;
target.right.parent = leftMaxNode;
target.right = target.parent = target.left = null;
leftMaxNode.parent = null;
reBalacedForRemoveHelp(tmpNode);
tmpNode.parent.right = tmpNode.left;
if(tmpNode.left != null){
tmpNode.left.parent = leftMaxNode.parent;
}
tmpNode = null;
}
}else{
AVLNode leftMaxNode = target.left;
while(leftMaxNode.right != null){
leftMaxNode = leftMaxNode.right;
}
if(target.left.data.equals(leftMaxNode.data)){
leftMaxNode.right = target.right;
leftMaxNode.parent = target.parent;
if(target == target.parent.left){
target.parent.left = leftMaxNode;
}else{
target.parent.right = leftMaxNode;
}
target.right = target.parent = target.left = null;
leftMaxNode.balanceFactory = target.balanceFactory - 1;
reBalacedForRemoveHelpAndHelp(leftMaxNode);
}else{
AVLNode tmpNode = new AVLNode(0,null,leftMaxNode.left,null,leftMaxNode.parent);
leftMaxNode.parent.right = tmpNode;
if(target == target.parent.left){
target.parent.left = leftMaxNode;
}else{
target.parent.right = leftMaxNode;
}
leftMaxNode.parent = target.parent;
leftMaxNode.left = target.left;
leftMaxNode.right = target.right;
target.left.parent = leftMaxNode;
target.right.parent = leftMaxNode;
target.right = target.parent = target.left = null;
reBalacedForRemoveHelp(tmpNode);
tmpNode.parent.right = tmpNode.left;
if(tmpNode.left != null){
tmpNode.left.parent = leftMaxNode.parent;
}
tmpNode = null;
}
}
}
}
// （ ）
private void reBalacedForRemoveHelp(AVLNode node){
if(node.parent != null){
if(node.parent.left != null && node.parent.right != null && node.left == null && node.right == null){
if(node == node.parent.left){
node.parent.balanceFactory -= 1;
reBalacedForRemoveHelpAndHelp(node.parent);
}else if(node == node.parent.right){
node.parent.balanceFactory += 1;
reBalacedForRemoveHelpAndHelp(node.parent);
}
}else{
if(node == node.parent.left){
node.parent.balanceFactory -= 1;
}else if(node == node.parent.right){
node.parent.balanceFactory += 1;
}
AVLNode current = node.parent;
while(current.parent != null){
if(current.balanceFactory == BALANCED){
if(current == current.parent.left){
current.parent.balanceFactory -= 1;
if(current.parent.balanceFactory == LEFT_LEFT_HEAVY){// -2，
if(typeOfRemove(current.parent, LEFT_LEFT_HEAVY).equals("RR")){
type_rR(current.parent);
break;
}else if(typeOfRemove(current.parent, LEFT_LEFT_HEAVY).equals("RL")){
type_rL(current.parent, true);
break;
}else{
//what are U nongshalie.
}
}
}else if(current == current.parent.right){
current.parent.balanceFactory += 1;
if(current.parent.balanceFactory == RIGHT_RIGHT_HEAVY){// 2，
if(typeOfRemove(current.parent, RIGHT_RIGHT_HEAVY).equals("LL")){
type_lL(current.parent);
break;
}else if(typeOfRemove(current.parent, RIGHT_RIGHT_HEAVY).equals("LR")){
type_lR(current.parent, true);
break;
}else{
//what are U nongshalie.
}
}
}
}else{
break;
}
current = current.parent;
}
}
}
}
private void reBalacedForRemoveHelpAndHelp(AVLNode current){
if(current.balanceFactory == RIGHT_RIGHT_HEAVY){// 2，
if(typeOfRemove(current, RIGHT_RIGHT_HEAVY).equals("LL")){
type_lL(current);
reBalacedForRemoveHelp(current.parent);
}else if(typeOfRemove(current, RIGHT_RIGHT_HEAVY).equals("LR")){
type_lR(current, true);
reBalacedForRemoveHelp(current.parent);
}else{
//what are U nongshalie.
}
}else if(current.balanceFactory == LEFT_LEFT_HEAVY){
if(typeOfRemove(current, LEFT_LEFT_HEAVY).equals("RR")){
type_rR(current);
reBalacedForRemoveHelp(current.parent);
}else if(typeOfRemove(current, LEFT_LEFT_HEAVY).equals("RL")){
type_rL(current, true);
reBalacedForRemoveHelp(current.parent);
}else{
//what are U nongshalie.
}
}
}
//
private void reBalacedForAdd(AVLNode node){
if(node.parent.left != null && node.parent.right != null){
if(node == node.parent.left){
node.parent.balanceFactory += 1;
return;
}else if(node == node.parent.right){
node.parent.balanceFactory -= 1;
return;
}
}else{
if(node == node.parent.left){
node.parent.balanceFactory += 1;
}else if(node == node.parent.right){
node.parent.balanceFactory -= 1;
}
AVLNode current = node.parent;
while(current.parent != null){
if(current.balanceFactory != BALANCED){
if(current == current.parent.left){
current.parent.balanceFactory += 1;
if(current.parent.balanceFactory == RIGHT_RIGHT_HEAVY){// 2，
if(typeOfAdd(node, current.parent).equals("LL")){
type_lL(current.parent);
break;
}else if(typeOfAdd(node, current.parent).equals("LR")){
type_lR(current.parent, false);
break;
}
}
}else if(current == current.parent.right){
current.parent.balanceFactory -= 1;
if(current.parent.balanceFactory == LEFT_LEFT_HEAVY){// -2，
if(typeOfAdd(node, current.parent).equals("RL")){
type_rL(current.parent, false);
break;
}else if(typeOfAdd(node, current.parent).equals("RR")){
type_rR(current.parent);
break;
}
}
}
current = current.parent;
}else{
break;
}
}
}
}
// LL RR LR RL
private String typeOfAdd(AVLNode node, AVLNode bFIs2Node){
AVLNode current = node;
while(true){//
if(bFIs2Node.left != null){
if(current == bFIs2Node.left.left){
return "LL";
}
if(current == bFIs2Node.left.right){
return "LR";
}
}else if(bFIs2Node.right != null){
if(current == bFIs2Node.right.right){
return "RR";
}
if(current == bFIs2Node.right.left){
return "RL";
}
}
current = current.parent;
}
}
private String typeOfRemove(AVLNode bFIs2Node, int bf){
if(bFIs2Node != null){
if(bf == RIGHT_RIGHT_HEAVY){ //
if(bFIs2Node.left != null){
if(bFIs2Node.left.balanceFactory >= BALANCED){
return bFIs2Node.left.left != null ? "LL" : "";
}else{
return bFIs2Node.left.right != null ? "LR" : "";
}
}
}else if(bf == LEFT_LEFT_HEAVY){ //
if(bFIs2Node.right != null){
if(bFIs2Node.right.balanceFactory >= BALANCED){
return bFIs2Node.right.left != null ? "RL" : "";
}else{
return bFIs2Node.right.right != null ? "RR" : "";
}
}
}
}
return "";
}
/***
* LL （ ）
* p l
* │ ││
* l───┘ -> ll───┘└───p
* │
* ll───┘
*
*/
private void type_lL(AVLNode p){
if(p != null){
AVLNode l = p.left;
//AVLNode ll = l.left;
if(p.parent == null){ //p
root = l;
l.parent = null;
p.left = l.right;
l.right = p;
p.parent = l;
if(l.balanceFactory == RIGHT_HEAVY){ //1
//l.balanceFactory = BALANCED;
//p.balanceFactory = BALANCED;
l.balanceFactory -= RIGHT_HEAVY;
p.balanceFactory -= RIGHT_RIGHT_HEAVY;
}else if(l.balanceFactory == BALANCED){//0
//l.balanceFactory = LEFT_HEAVY;
//p.balanceFactory = BALANCED;
l.balanceFactory -= RIGHT_HEAVY;
p.balanceFactory -= RIGHT_HEAVY;
}else{
/*l.balanceFactory -= RIGHT_HEAVY;
p.balanceFactory -= RIGHT_HEAVY;*/
}
}else{
if(p == p.parent.left){
p.parent.left = l;
}else if(p == p.parent.right){
p.parent.right = l;
}
l.parent = p.parent;
p.left = l.right;
l.right = p;
p.parent = l;
if(l.balanceFactory == RIGHT_HEAVY){ //1
//l.balanceFactory = BALANCED;
//p.balanceFactory = BALANCED;
l.balanceFactory -= RIGHT_HEAVY;
p.balanceFactory -= RIGHT_RIGHT_HEAVY;
}else if(l.balanceFactory == BALANCED){//0
//l.balanceFactory = LEFT_HEAVY;
//p.balanceFactory = BALANCED;
l.balanceFactory -= RIGHT_HEAVY;
p.balanceFactory -= RIGHT_HEAVY;
}else {
/*l.balanceFactory -= RIGHT_HEAVY;
p.balanceFactory -= RIGHT_HEAVY;*/
}
}
}
}
/**
* RR （ ）
* p r
* │ -> ││
* └───r p───┘└───rr
* │
* └──rr
*/
private void type_rR(AVLNode p){
AVLNode r = p.right;
//AVLNode rr = r.right;
if(p.parent == null){ //p
root = r;
r.parent = null;
p.right = r.left;
r.left = p;
p.parent = r;
if(r.balanceFactory == LEFT_HEAVY){ //-1
//r.balanceFactory = BALANCED;
r.balanceFactory += RIGHT_HEAVY;
p.balanceFactory += RIGHT_RIGHT_HEAVY;
}else if(r.balanceFactory == BALANCED){//0
//r.balanceFactory = RIGHT_HEAVY;
//p.balanceFactory = BALANCED;
r.balanceFactory += RIGHT_HEAVY;
p.balanceFactory += RIGHT_HEAVY;
}else {
/*r.balanceFactory += RIGHT_HEAVY;
p.balanceFactory += RIGHT_HEAVY;*/
}
}else{
if(p == p.parent.left){
p.parent.left = r;
}else if(p == p.parent.right){
p.parent.right = r;
}
r.parent = p.parent;
p.right = r.left;
r.left = p;
p.parent = r;
if(r.balanceFactory == LEFT_HEAVY){ //-1
//r.balanceFactory = BALANCED;
r.balanceFactory += RIGHT_HEAVY;
p.balanceFactory += RIGHT_RIGHT_HEAVY;
}else if(r.balanceFactory == BALANCED){//0
//r.balanceFactory = RIGHT_HEAVY;
//p.balanceFactory = BALANCED;
r.balanceFactory += RIGHT_HEAVY;
p.balanceFactory += RIGHT_HEAVY;
}else {
/*r.balanceFactory += RIGHT_HEAVY;
p.balanceFactory += RIGHT_HEAVY;*/
}
}
}
/**
* LR （ （ ））
* p
* │ lr
* l───┘ -》 ││
* │ l──┘└───p
* └───lr
*
* @param p
*/
private void type_lR(AVLNode p, boolean isRemove){
/*AVLNode l = p.left;
AVLNode lr = l.right;
type_rR(l);
type_lL(p);
if(isRemove){
lr.balanceFactory += RIGHT_HEAVY;
}*/
AVLNode l = p.left;
AVLNode lr = l.right;
if(p.parent == null){ //
root = lr;
l.right = lr.left;
if(lr.left != null){
lr.left.parent = l;
}
p.left = lr.right;
if(lr.right != null){
lr.right.parent = p;
}
lr.left = l;
lr.right = p;
l.parent = lr;
p.parent = lr;
lr.parent = null;
if(lr.balanceFactory == RIGHT_HEAVY){ //1
p.balanceFactory -= 3;
l.balanceFactory += 1;
lr.balanceFactory -= 1;
}else if(lr.balanceFactory == BALANCED){//0
p.balanceFactory -= 2;
l.balanceFactory += 1;
}else if(lr.balanceFactory == LEFT_HEAVY){//-1
p.balanceFactory -= 2;
l.balanceFactory += 2;
lr.balanceFactory += 1;
}
}else{
l.right = lr.left;
if(lr.left != null){
lr.left.parent = l;
}
p.left = lr.right;
if(lr.right != null){
lr.right.parent = p;
}
lr.left = l;
lr.right = p;
lr.parent = p.parent;
if(p == p.parent.left){
p.parent.left = lr;
}
if(p == p.parent.right){
p.parent.left = lr;
}
l.parent = lr;
p.parent = lr;
if(lr.balanceFactory == RIGHT_HEAVY){ //1
p.balanceFactory -= 3;
l.balanceFactory += 1;
lr.balanceFactory -= 1;
}else if(lr.balanceFactory == BALANCED){ //0
p.balanceFactory -= 2;
l.balanceFactory += 1;
}else if(lr.balanceFactory == LEFT_HEAVY){ //-1
p.balanceFactory -= 2;
l.balanceFactory += 2;
lr.balanceFactory += 1;
}
}
}
/**
* RL （ （ ））
* p
* │ rl
* └──r -》 ││
* │ p──┘└───r
* rl───┘
*
* @param p
*/
private void type_rL(AVLNode p, boolean isRemove){
/*AVLNode r = p.right;
AVLNode rl = r.left;
type_lL(r);
type_rR(p);
if(isRemove){
rl.balanceFactory -= RIGHT_HEAVY;
}*/
AVLNode r = p.right;
AVLNode rl = r.left;
if(p.parent == null){ //
root = rl;
r.left = rl.right;
if(rl.right != null){
rl.right.parent = r;
}
p.right = rl.left;
if(rl.left != null){
rl.left.parent = p;
}
rl.left = p;
rl.right = r;
rl.parent = p.parent;
p.parent = rl;
r.parent = rl;
if(rl.balanceFactory == RIGHT_HEAVY){ //1
p.balanceFactory += 2;
r.balanceFactory -= 2;
rl.balanceFactory -= 1;
}else if(rl.balanceFactory == BALANCED){
p.balanceFactory += 2;
r.balanceFactory -= 1;
}else if(rl.balanceFactory == LEFT_HEAVY){
p.balanceFactory += 3;
r.balanceFactory -= 1;
rl.balanceFactory += 1;
}
}else{
r.left = rl.right;
if(rl.right != null){
rl.right.parent = r;
}
p.right = rl.left;
if(rl.left != null){
rl.left.parent = p;
}
rl.left = p;
rl.right = r;
rl.parent = p.parent;
if(p == p.parent.left){
p.parent.left = rl;
}
if(p == p.parent.right){
p.parent.left = rl;
}
p.parent = rl;
r.parent = rl;
if(rl.balanceFactory == RIGHT_HEAVY){ //1
p.balanceFactory += 2;
r.balanceFactory -= 2;
rl.balanceFactory -= 1;
}else if(rl.balanceFactory == BALANCED){
p.balanceFactory += 2;
r.balanceFactory -= 1;
}else if(rl.balanceFactory == LEFT_HEAVY){
p.balanceFactory += 3;
r.balanceFactory -= 1;
rl.balanceFactory += 1;
}
}
}
//
private AVLNode getAVLNode(T data){
if(root == null){
return null;
}
AVLNode node = root;
int compInt = 0;
while(node != null){
compInt = data.compareTo(node.data);
if(compInt > 0){
node = node.right;
}else if(compInt < 0){
node = node.left;
}else{
return node;
}
}
return null;
}
//
public List breadthFirstSearch(){
return cBreadthFirstSearch(root);
}
private List cBreadthFirstSearch(AVLNode node) {
List nodes = new ArrayList();
Deque deque = new ArrayDeque();
if(node != null){
deque.offer(node);
}
while(!deque.isEmpty()){
AVLNode tmp = deque.poll();
nodes.add(tmp);
if(tmp.left != null){
deque.offer(tmp.left);
}
if(tmp.right != null){
deque.offer(tmp.right);
}
}
return nodes;
}
public static void main(String[] args) {
HeightBalanBinSearchTree tree = new HeightBalanBinSearchTree();
tree.add(20);
tree.add(23);
tree.add(17);
tree.add(19);
tree.add(21);
tree.add(26);
tree.add(14);
tree.add(18);
tree.add(11);
tree.add(16);
tree.add(22);
tree.add(24);
tree.add(27);
//tree.add(15);
System.out.println( tree.breadthFirstSearch());
tree.remove(17);
System.out.println( tree.breadthFirstSearch());
}
}
[[BF=1,data=20], [BF=1,data=17], [BF=0,data=23], [BF=-1,data=14], [BF=1,data=19], [BF=-1,data=21], [BF=0,data=26], [BF=0,data=11], [BF=1,data=16], [BF=0,data=18], [BF=0,data=22], [BF=0,data=24], [BF=0,data=27], [BF=0,data=15]]
[[BF=0,data=20], [BF=0,data=16], [BF=0,data=23], [BF=0,data=14], [BF=1,data=19], [BF=-1,data=21], [BF=0,data=26], [BF=0,data=11], [BF=0,data=15], [BF=0,data=18], [BF=0,data=22], [BF=0,data=24], [BF=0,data=27]]