木の回転

アルちゃん

前回

基本的にはwikipediaにある通り。

二分探索木の格納ルール（左子の値＜親の値＜右子の値）を崩さずにノード間の参照関係を変更する操作。

画像1

回転対象のノードをRootとし、回転後Rootの位置につくノードをPivotとする。右回転の場合

画像2

各ノードが親ノードへの参照を持たないならば、やはりWikipediaにある通り右回転は

Pivot = Root.Left
Root.Left = Pivot.Right
Pivot.Right = Root
Root = Pivot

各ノードが親ノードへの参照を持つ場合、冗長ではあるが以下

//processing
BinaryTreeNode RotRight(BinaryTree tree, BinaryTreeNode root, BinaryTreeNode pivot)
{
 if(root==null){return null;}
 if(pivot==null){return null;}
 
 //rootの左子がpivot
 
 //Treeクラスが存在し、そのクラスがRootへの参照を持つならrootを変更
 if(root.Parent==null)
 {
   tree.Root = pivot;
 }

 BinaryTreeNode root_parent = root.Parent;
 //BinaryTreeNode root_left = root.Left;
 //BinaryTreeNode root_right = root.Right;
 
 boolean is_left_child = IsLeftChild(root);
         
 //BinaryTreeNode pivot_parent = pivot.Parent;
 //BinaryTreeNode pivot_left = pivot.Left;
 BinaryTreeNode pivot_right = pivot.Right;
 
 //pivotの右子をrootの左子に
 root.Left=pivot_right;//B
 if(root.Left!=null){root.Left.Parent=root;}

 pivot.Right=root;
 root.Parent=pivot;
 
 pivot.Parent=root_parent;//pivotはRootに  
 if(is_left_child)
 {
   if(pivot.Parent!=null){pivot.Parent.Left=pivot;}
 }
 else
 {
   if(pivot.Parent!=null){pivot.Parent.Right=pivot;}
 }  
 return pivot;  //回転後のRootを返す
}

//対象ノードは親の左子か
boolean IsLeftChild(BinaryTreeNode current)
{
 if(current==null){return false;}  
 if(current.Parent==null){return false;}//Rootならfalse
 if(current.Parent.Left!=null&&current.Parent.Left==current){return true;}
 return false;
}

左回転

BinaryTreeNode RotLeft(BinaryTree tree, BinaryTreeNode root, BinaryTreeNode pivot)
{
 if(root==null){return null;}
 if(pivot==null){return null;}
 
 //rootの右子がpivot
 
 //Treeクラスが存在し、そのクラスがRootへの参照を持つならrootを変更
 if(root.Parent==null)
 {
   tree.Root = pivot;
 }

 BinaryTreeNode root_parent = root.Parent;
 //BinaryTreeNode root_left = root.Left;
 //BinaryTreeNode root_right = root.Right;
 
 boolean is_left_child = IsLeftChild(root);
         
 //BinaryTreeNode pivot_parent = pivot.Parent;
 BinaryTreeNode pivot_left = pivot.Left;
 //BinaryTreeNode pivot_right = pivot.Right;
 
 //pivotの左子をrootの右子に
 root.Right=pivot_left;
 if(root.Right!=null){root.Right.Parent=root;}

 pivot.Left=root;
 root.Parent=pivot;
 
 pivot.Parent=root_parent;//pivotはRootに  
 if(is_left_child)
 {
   if(pivot.Parent!=null){pivot.Parent.Left=pivot;}
 }
 else
 {
   if(pivot.Parent!=null){pivot.Parent.Right=pivot;}
 }  
 return pivot;  //回転後のRootを返す
}

テスト用のコード（コピペ用）



import controlP5.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Deque;
import java.lang.NumberFormatException;

ControlP5 cp;
Textfield textField_delete;//Delete用
Textfield textField_insert;//insert用
Textfield textField_rotleft;//RotLeft
Textfield textField_rotright;//RotRight

Button button1;
void rot_rand()
{
  while(RotLeft(Tree, (int)(random(100)))==null){};
}

BinaryTree Tree;

void keyPressed()
{
 if (key == ENTER) 
 {
   try
   {
     
     if(textField_delete.isFocus())
     {
       int input = Integer.parseInt(textField_delete.getText()); 
       boolean result = Delete(this.Tree, input);  
     }
     if(textField_insert.isFocus())
     {
       int input = Integer.parseInt(textField_insert.getText()); 
       boolean result = Add(this.Tree, input); 
     }
     if(textField_rotleft.isFocus())
     {
       int input = Integer.parseInt(textField_rotleft.getText()); 
       BinaryTreeNode n = RotLeft(this.Tree, input);  
     }
     if(textField_rotright.isFocus())
     {
       int input = Integer.parseInt(textField_rotright.getText());
       BinaryTreeNode n = RotRight(this.Tree, input);  
     }      
     
   }
   catch(NumberFormatException ex)
   {

   }
 }
}

void setup()
{
 size(500,500);
 
 cp = new ControlP5(this);

 int textfield_x = 40;
 int textfield_y = 300;  
 int textfield_width = 100;  
 int textfield_height = 20;
 int label_offset = 20;
 
 button1 = cp.addButton("rot_rand")
    .setPosition(40,30);
 
 textField_delete = cp.addTextfield("delete")
    .setPosition(textfield_x,textfield_y)
    .setSize(textfield_width,textfield_height)
    .setFocus(true)
    .setColor(color(0))//Box内文字の色
    .setColorActive(color(0))//Box枠の色
    .setColorBackground(color(255)) //Box内背景色      
    .setColorCaptionLabel(color(0))//Labelの色
    ;
 textfield_y+=textfield_height+label_offset;
 
 textField_insert = cp.addTextfield("insert")
    .setPosition(textfield_x,textfield_y)
    .setSize(textfield_width,textfield_height)
    .setFocus(true)
    .setColor(color(0))//Box内文字の色
    .setColorActive(color(0))//Box枠の色
    .setColorBackground(color(255)) //Box内背景色      
    .setColorCaptionLabel(color(0))//Labelの色
    ;     
 textfield_y+=textfield_height+label_offset;     
 
 textField_rotleft = cp.addTextfield("rotleft")
    .setPosition(textfield_x,textfield_y)
    .setSize(textfield_width,textfield_height)
    .setFocus(true)
    .setColor(color(0))//Box内文字の色
    .setColorActive(color(0))//Box枠の色
    .setColorBackground(color(255)) //Box内背景色      
    .setColorCaptionLabel(color(0))//Labelの色
    ;     
 textfield_y+=textfield_height+label_offset;        

 textField_rotright = cp.addTextfield("rotright")
    .setPosition(textfield_x,textfield_y)
    .setSize(textfield_width,textfield_height)
    .setFocus(true)
    .setColor(color(0))//Box内文字の色
    .setColorActive(color(0))//Box枠の色
    .setColorBackground(color(255)) //Box内背景色      
    .setColorCaptionLabel(color(0))//Labelの色
    ;     
 textfield_y+=textfield_height+label_offset;        
 
 Tree = new BinaryTree(20);
 RandomAdd(20);
 
 TreeOrigin = new PVector(width/2,20);
}

void RandomAdd(int count)
{
 for(int i = 0; i<count; i++)
 {
   Add(Tree, (int)(random(100)));    
 }
}

void RandomRot(int count)
{
 for(int i = 0; i<count; i++)
 {
   RotLeft(Tree, (int)(random(100)));
   RotRight(Tree, (int)(random(100)));
 }
}

PVector TreeOrigin = new PVector(0,0);
PVector TreeOffsetR = new PVector(20,40);
PVector TreeOffsetL = new PVector(-20,40);

void draw()
{
 background(255);
 
 DrawQueue();
 //Add(Tree, (int)(random(100)));
 RotLeft(Tree, (int)(random(100)));
 RotRight(Tree, (int)(random(100)));
 //delay(10);
 //RandomRot(100);
}

class BinaryTree<T extends Comparable<T>>
{  
 BinaryTreeNode<T> Root;  
 
 //コンストラクタ
 BinaryTree(BinaryTreeNode<T> root)
 {
   Root = root;
 }  
 BinaryTree(T root_value)
 {
   Root = new BinaryTreeNode(root_value);
 }
}

class BinaryTreeNode<T extends Comparable<T>>
{
 BinaryTreeNode<T> Parent;
  
 //なんらかのValue,ただしComperableを実装
 T Value;
 
 BinaryTreeNode<T> Left;
 BinaryTreeNode<T> Right;
 
 //コンストラクタ
 BinaryTreeNode(T value)
 {
   this.Value = value;
 }
}

//+tree
<T extends Comparable<T>>
BinaryTreeNode RotLeft(BinaryTree tree, T value)
{
 if(tree==null){return null;}
 BinaryTreeNode node = Search(tree.Root, value);
 if(node==null){return null;}
 return RotLeft(tree, node);
}

//+tree
BinaryTreeNode RotLeft(BinaryTree tree, BinaryTreeNode root)
{
 if(root==null){return null;}
 //回転後のRootを返す
 return RotLeft(tree, root, root.Right);
}

//+tree
BinaryTreeNode RotLeft(BinaryTree tree, BinaryTreeNode root, BinaryTreeNode pivot)
{
 if(root==null){return null;}
 if(pivot==null){return null;}
 
 //rootの右子がpivot
 
 //TreeがあるならTreeのrootを変更
 if(root.Parent==null)
 {
   tree.Root = pivot;
 }

 BinaryTreeNode root_parent = root.Parent;
 //BinaryTreeNode root_left = root.Left;
 //BinaryTreeNode root_right = root.Right;
 
 boolean is_left_child = IsLeftChild(root);
         
 //BinaryTreeNode pivot_parent = pivot.Parent;
 BinaryTreeNode pivot_left = pivot.Left;
 //BinaryTreeNode pivot_right = pivot.Right;
 
 //pivotの左子をrootの右子に
 root.Right=pivot_left;
 if(root.Right!=null){root.Right.Parent=root;}

 pivot.Left=root;
 root.Parent=pivot;
 
 pivot.Parent=root_parent;//pivotはRootに  
 if(is_left_child)
 {
   if(pivot.Parent!=null){pivot.Parent.Left=pivot;}
 }
 else
 {
   if(pivot.Parent!=null){pivot.Parent.Right=pivot;}
 }  
 return pivot;  //回転後のRootを返す
}

//+tree
<T extends Comparable<T>>
BinaryTreeNode RotRight(BinaryTree tree, T value)
{
 if(tree==null){return null;}  
 BinaryTreeNode node = Search(tree.Root, value);
 if(node==null){return null;}  
 return RotRight(tree, node);
}

//+tree
BinaryTreeNode RotRight(BinaryTree tree, BinaryTreeNode root)
{
 if(root==null){return null;}
 //回転後のRootを返す
 return RotRight(tree, root, root.Left);
}

//+tree
BinaryTreeNode RotRight(BinaryTree tree, BinaryTreeNode root, BinaryTreeNode pivot)
{
 if(root==null){return null;}
 if(pivot==null){return null;}
 
 //rootの左子がpivot
 
 //Treeクラスが存在し、そのクラスがRootへの参照を持つならrootを変更
 if(root.Parent==null)
 {
   tree.Root = pivot;
 }

 BinaryTreeNode root_parent = root.Parent;
 //BinaryTreeNode root_left = root.Left;
 //BinaryTreeNode root_right = root.Right;
 
 boolean is_left_child = IsLeftChild(root);
         
 //BinaryTreeNode pivot_parent = pivot.Parent;
 //BinaryTreeNode pivot_left = pivot.Left;
 BinaryTreeNode pivot_right = pivot.Right;
 
 //pivotの右子をrootの左子に
 root.Left=pivot_right;//B
 if(root.Left!=null){root.Left.Parent=root;}

 pivot.Right=root;
 root.Parent=pivot;
 
 pivot.Parent=root_parent;//pivotはRootに  
 if(is_left_child)
 {
   if(pivot.Parent!=null){pivot.Parent.Left=pivot;}
 }
 else
 {
   if(pivot.Parent!=null){pivot.Parent.Right=pivot;}
 }  
 return pivot;  //回転後のRootを返す
}

//探索操作
<T extends Comparable<T>> 
BinaryTreeNode Search(BinaryTree tree, T value)
{
 return Search(tree, new BinaryTreeNode(value));
}

<T extends Comparable<T>> 
BinaryTreeNode Search(BinaryTreeNode node, T value)
{
 return Search(node, new BinaryTreeNode(value));
}

BinaryTreeNode Search(BinaryTree tree, BinaryTreeNode node)
{
 return Search(tree.Root, node);
}

BinaryTreeNode Search(BinaryTreeNode start_node, BinaryTreeNode node)
{
 BinaryTreeNode current = start_node;  
 while(true)
 {
   //引数の方が大きいならreturn -1
   //引数の方が小さいならreturn +1
   if(current.Value.compareTo(node.Value)<0)
   {
     current = current.Right;
     if(current == null){return null;}//終了:発見できなかった
   }
   else if(current.Value.compareTo(node.Value)>0)
   {
     current = current.Left;
     if(current == null){return null;}//終了:発見できなかった      
   }
   else//等しい:発見できた
   {
     return current;
     //終了
   }
 }
}

//挿入操作
<T extends Comparable<T>> boolean Add(BinaryTree tree, T value)
{
 return Add(tree, new BinaryTreeNode(value));
}

//挿入操作
boolean Add(BinaryTree tree, BinaryTreeNode node)
{
 return Add(tree.Root, node);
}

//挿入操作
boolean Add(BinaryTreeNode start_node, BinaryTreeNode new_node)
{
 if(start_node==null){return false;}
 if(new_node==null){return false;}
 
 BinaryTreeNode current = start_node;  
 
 while(true)
 {    
   //引数の方が大きいならreturn -1
   //引数の方が小さいならreturn +1
   if(current.Value.compareTo(new_node.Value)<0)
   {
     if(current.Right == null){ break; }//成功,while breakして参照セットアップへ
     else{current = current.Right;}//次のノードへ          
   }
   else if(current.Value.compareTo(new_node.Value)>0)
   {
     if(current.Left == null){break;}//成功,while breakして参照セットアップへ
     else{current = current.Left;}//次のノードへ  
   }
   else//等しい:受け入れ拒否
   {
     return false;
   }
 }//while
 
 boolean result = SetParent(current, new_node);
 if(!result){return false;}
 return true;
}

boolean SetParent(BinaryTreeNode parent, BinaryTreeNode current)
{
 if(parent==null){return false;}
 if(current==null){return false;}
 if(parent==current){return false;}
   
 //子から親へ接続
 current.Parent = parent;
   
 //親から子へ接続
 if(parent.Value.compareTo(current.Value)<0)
 {
   //parent<current;
   parent.Right = current;
   return true;
 }
 else if(parent.Value.compareTo(current.Value)>0)
 {
   //parent>current;
   parent.Left = current;
   return true;
 }
 else
 {
   return false;
 }    
}

<T extends Comparable<T>>
boolean Delete(BinaryTree tree, T value)
{
 return Delete(tree.Root, new BinaryTreeNode(value));
}

boolean Delete(BinaryTree tree, BinaryTreeNode node)
{
 return Delete(tree.Root, node);
}

//ノードがParent持ち
boolean Delete(BinaryTreeNode start_node, BinaryTreeNode node)
{ 
 BinaryTreeNode current = start_node;  
 while(true)
 {   
   //引数の方が大きいならreturn -1
   //引数の方が小さいならreturn +1
   if(current.Value.compareTo(node.Value)<0)
   {
     current = current.Right;
     if(current == null){return false;}//終了:削除対象ノードが発見できなかった
   }
   else if(current.Value.compareTo(node.Value)>0)
   {
     current = current.Left;
     if(current == null){return false;}//終了:削除対象ノードが発見できなかった
   }
   else
   {
     //削除対象ノードが発見できた
     if(current.Parent==null){return false;}//Root          
     if(!HasChild(current)){return DeleteReference(current);}//削除対象が子を持たない
     else if(HasSideChild(current))
     {         
       return PullOutNode(current);
     }
     else
     {
       //currentに左右の系列がある                             
       //現在のノードの左の子より始めて、最大値を有するノードを得る
       BinaryTreeNode max = Max(current.Left);                     
       if(max==current.Left)
       {
         return ReplaceReference(max,current);
       }                  
       PullOutNode(max);       
       return ReplaceReference(max,current);           
     }//子が２つ以上の削除          
   }//探索により、削除対象の発見  
 }//while
}//Delete

int count = 0;
void DrawQueue()
{
 Queue<BinaryTreeNode> queue = new ArrayDeque<BinaryTreeNode>();  
 queue.add(Tree.Root);
 
 count=0;
 
 while(0<queue.size())
 {  
   count++;
   if(count>10000)
   {
     break;
   }
   
   BinaryTreeNode node = queue.poll();    
   PVector coord = GetCoordinate(Tree, node, TreeOrigin, TreeOffsetR);       
   if(coord!=null)
   {
     //current
     circle(coord.x,coord.y,20);
     //current.L,R
     PVector coordL = GetCoordinate(Tree, node.Left, TreeOrigin, TreeOffsetR);
     if(coordL!=null){line(coordL.x,coordL.y,coord.x,coord.y);}      
     PVector coordR = GetCoordinate(Tree, node.Right, TreeOrigin, TreeOffsetR);      
     if(coordR!=null){line(coordR.x,coordR.y,coord.x,coord.y);}            
   }

   fill(255,0,0);
   text(str((int)node.Value),coord.x,coord.y);        
   BinaryTreeNode parent = node.Parent;
   if(parent!=null){text("P:"+str((int)parent.Value),coord.x,coord.y+10);}
   BinaryTreeNode left = node.Left;
   if(left!=null){text("L:"+str((int)left.Value),coord.x,coord.y+20);}
   BinaryTreeNode right = node.Right;
   if(right!=null){text("R:"+str((int)right.Value),coord.x,coord.y+30);}        
   noFill();
   
   //queue.add
   if(node.Left!=null)
   {
     queue.add(node.Left);
   }
   if(node.Right!=null)
   {
     queue.add(node.Right);
   }    
 }//queue while   
}

PVector GetCoordinate(BinaryTree tree, BinaryTreeNode node, PVector origin, PVector offset_r)
{
 if(node==null){return null;}
 
 PVector ret_coord = origin.copy();
 PVector offset_l = new PVector(-offset_r.x, offset_r.y);
 
 BinaryTreeNode root = tree.Root;  
 BinaryTreeNode current = root;  
 while(true)
 {
   if(current==null){return new PVector(0,0);}
   if(node==null){return new PVector(0,0);}
   
   //引数の方が大きいならreturn -1
   //引数の方が小さいならreturn +1
   if(current.Value.compareTo(node.Value)<0)
   {
     current = current.Right;
     if(current == null){return null;}//終了:発見できなかった
     ret_coord.add(offset_r);
     
     int depth = GetDepth(tree, current);
     PVector offsetH = CalcuOffsetH(depth, offset_r);
     ret_coord.add(offsetH);
   }
   else if(current.Value.compareTo(node.Value)>0)
   {
     current = current.Left;
     if(current == null){return null;}//終了:発見できなかった
     ret_coord.add(offset_l);
     
     //補正
     int depth = GetDepth(tree, current);
     PVector offsetH = CalcuOffsetH(depth, offset_l);
     ret_coord.add(offsetH);  
   }
   else//等しい:発見できた
   {
     return ret_coord;
     //終了
   }
 }//while
}

PVector CalcuOffsetH(int depth, PVector offset)
{
   float range = (offset.x*2)*(depth+1);
   int node_count = (int)Math.pow(2,depth);      
   PVector offsetH = new PVector(range/(float)node_count,0);  
   return offsetH;
}

//nodeは一人っ子を所持
boolean HasSideChild(BinaryTreeNode node)
{
 if(!HasChild(node)){return false;}//子がゼロ
 else if(node.Left!=null&&node.Right==null){return true;}//左にのみ子がある
 else if(node.Left==null&&node.Right!=null){return true;}//右にのみ子がある
 return false;
}

boolean HasChild(BinaryTreeNode node)
{  
 if(node.Left==null&&node.Right==null){return false;}//子がゼロ
 return true;//子がゼロでない
}

//対象ノードは親の左子か
boolean IsLeftChild(BinaryTreeNode current)
{
 if(current==null){return false;}  
 if(current.Parent==null){return false;}//Rootならfalse
 if(current.Parent.Left!=null&&current.Parent.Left==current){return true;}
 return false;
}

//対象ノードは親の右子か
boolean IsRightChild(BinaryTreeNode current)
{
 if(current==null){return false;}  
 if(current.Parent==null){return false;}//Rootならfalse  
 if(current.Parent.Right!=null&&current.Parent.Right==current){return true;}
 return false;
}

//親から子への参照を解除
boolean QuiteParent(BinaryTreeNode current)
{
 return QuiteParent(current.Parent, current);
}

//親から子への参照を解除
boolean QuiteParent(BinaryTreeNode parent, BinaryTreeNode current)
{
 if(parent==null){return false;}
 if(current==null){return false;}
 if(current.Parent==null){return false;}
 
 //親から子への接続を解除
 //インスタンス間の==演算子はreference equalになる
 if(IsLeftChild(current))
 {
   parent.Left=null;
   return true;
 }
 else if(IsRightChild(current))
 {
   parent.Right=null;
   return true;
 }
 else{return false;}//謎の状態    
}

boolean DeleteReference(BinaryTreeNode child)
{  
 return DeleteReference(child.Parent, child);
}

boolean DeleteReference(BinaryTreeNode parent, BinaryTreeNode current)
{
 if(parent==null){return false;}
 if(current==null){return false;}
 if(current.Parent==null){return false;}
 
 //■currentへの参照を削除
 //parentからcurrentへの参照を削除
 QuiteParent(parent, current);  
 //Left,Rightからcurrentへの参照を削除
 if(current.Left!=null){QuiteParent(current, current.Left);}  
 if(current.Right!=null){QuiteParent(current, current.Right);}  

 //■currentからの参照を削除
 //currentからparentへの参照を解除
 current.Parent=null;    
 //currentのLeft,Rightへの参照を解除
 current.Left = null;
 current.Right = null;
 
 return true;
}

//ノードを周辺参照から引っこ抜く
//ノードの抜けた穴は修復される
boolean PullOutNode(BinaryTreeNode current)
{
 //両方に子がある=>抜き出すことはできない
 if(current.Left!=null&&current.Right!=null){return false;}
 
 //左にのみ子がある
 if(current.Left!=null&&current.Right==null)
 {
   //左系列の移植
   return PortingLeftChild(current);    
 }
 //右にのみ子がある
 else if(current.Left==null&&current.Right!=null)  
 {
   //右系列の移植
   return PortingRightChild(current);  
 }
 //子がない
 else if(current.Left==null&&current.Right==null)
 {
   //親からの参照だけは抜いておく
   return QuiteParent(current);
 }
 return false;
}

//currentのLeft系列をcurrentの位置に引き上げる
boolean PortingLeftChild(BinaryTreeNode current)
{
 if(current==null){return false;}
 if(current.Parent==null){return false;}
 
 if(IsLeftChild(current))
 {
   if(current.Parent!=current.Left)
   {
     current.Parent.Left=current.Left;
   }
   if(current.Left!=current.Parent)
   {
     current.Left.Parent=current.Parent;
   }
   
   current.Parent=null;
   current.Left=null;
   current.Right=null;
   return true;
 }
 else if(IsRightChild(current))
 {
   if(current.Parent!=current.Left)
   {
     current.Parent.Right=current.Left;
   }
   if(current.Left!=current.Parent)
   {
     current.Left.Parent=current.Parent;
   }
   
   current.Parent=null;
   current.Left=null;
   current.Right=null;
   return true;
 }
 return false;  
}

//currentのRight系列をcurrentの位置に引き上げる
boolean PortingRightChild(BinaryTreeNode current)
{
 if(current==null){return false;}
 if(current.Parent==null){return false;}
 
 if(IsLeftChild(current))
 {
   //current親から子へ
   if(current.Parent!=current.Right)
   {
     current.Parent.Left=current.Right;
   }
   //current子から親へ
   if(current.Right!=current.Parent)
   {
     current.Right.Parent=current.Parent;
   }   
   
   current.Parent=null;
   current.Right=null;
   current.Left=null;
   return true;
 }
 else if(IsRightChild(current))
 {
   //current親から子へ
   if(current.Parent!=current.Right)
   {
     current.Parent.Right=current.Right;
   }
   //current子から親へ
   if(current.Right!=current.Parent)
   {
     current.Right.Parent=current.Parent;
   }
   
   current.Parent=null;
   current.Right=null;
   current.Left=null;
   return true;
 }
 return false;  
}

//targetノードの居た場所にsurceノードを叩き込む
boolean ReplaceReference(BinaryTreeNode source, BinaryTreeNode target)
{
 if(source==null){return false;}
 if(target==null){return false;}
 if(target.Parent==null){return false;}  
 
 BinaryTreeNode tempParent = target.Parent;
 BinaryTreeNode tempLeft = target.Left;
 BinaryTreeNode tempRight = target.Right;
   
 //sourceからの参照3本
 if(tempParent!=source)
 {
   source.Parent = tempParent;
 }
 if(tempLeft!=source)
 {
   source.Left = tempLeft;    
 }
 if(tempRight!=source)
 {
   source.Right = tempRight;    
 }
 
 //targetの親から子への参照
 if(IsLeftChild(target))
 {
   if(tempParent!=source){tempParent.Left=source;}
 }  
 else if(IsRightChild(target))
 {
   if(tempParent!=source){tempParent.Right=source;}
 }
 else
 {
   return false;
 }  
 
 //targetの子から親への参照
 if(tempLeft!=null&&tempLeft!=source)
 {
   tempLeft.Parent=source;
 }
 if(tempRight!=null&&tempRight!=source)
 {
   tempRight.Parent=source;
 }
 
 target.Parent = null;
 target.Left = null;
 target.Right = null;
 return true;
}

//最大ノード(右端）を得る
//Root始動
BinaryTreeNode Max(BinaryTree tree)
{
 return Max(tree.Root);
}

//指定のノード始動
BinaryTreeNode Max(BinaryTreeNode node)
{
 if(node==null){return null;}  
 BinaryTreeNode current = node;  
 while(current.Right!=null)
 {
   current = current.Right;
 }   
 return current;
}

BinaryTreeNode Min(BinaryTree tree)
{
 return Min(tree.Root);
}

BinaryTreeNode Min(BinaryTreeNode node)
{
 if(node==null){return null;}  
 BinaryTreeNode current = node;  
 while(current.Left!=null)
 {
   current = current.Left;
 }   
 return current;
}

int GetDepth(BinaryTree tree, BinaryTreeNode node)
{
 return GetDepth(tree.Root, node);
}

int GetDepth(BinaryTreeNode root, BinaryTreeNode node)
{
 int depth = 0;
 
 BinaryTreeNode current = root;  
 while(true)
 {
   //引数の方が大きいならreturn -1
   //引数の方が小さいならreturn +1
   if(current.Value.compareTo(node.Value)<0)
   {
     current = current.Right;
     depth++;
     if(current == null){return depth;}//終了:発見できなかった
   }
   else if(current.Value.compareTo(node.Value)>0)
   {
     current = current.Left;
     depth++;
     if(current == null){return depth;}//終了:発見できなかった      
   }
   else//等しい:発見できた
   {      
     return depth;
     //終了
   }
 }  
}

この記事が気に入ったらサポートをしてみませんか？