Document

二分探索木における要素削除
データ構造とプログラミング（１０）
大岩元
慶応大学環境情報学部
[email protected]
節（ノード）の削除
削除するノードに子がない
削除するノードを見つけ、その親からの参照を
null にする
削除するノードに子が１つある
親の参照をそのノードの子への参照に変える
削除するノードに子が２つある
そのノードの右の子の子孫の最小値を持つノード
と入れ換え、必要な付け替えを行なう
削除するプログラム(最初の部分）
public boolean delete( int key){
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while ( current.iData != key ) {
parent = current;
if ( key < durrent.iData ) {
ifLeftChild = true;
current = current.leftChild;
}
else {
ieLeftChild = false;
current = current.rightChild;
}
if ( current = null) return false;
}
子の無いノードを削除する
if ( current.leftChild == null && current.rightChild == null ) {
if ( current == root) root = null;
else if ( isLeftChild ) parent.leftChild = null;
else parent.rightChild = null;
}
削除するノードに子が１つある
else if ( current.rightChild == null )
if ( current == root ) root = current.leftChild;
else if ( isLeftChild ) parent.leftChild = current.leftChild;
else parent.rightChild = current.leftChild;
else if ( current.leftChild == null )
if (current == root) root = current.rightChild;
else if (isLeftChild ) parent.leftChild = current.rightChild;
else parent.rightChild = current.rightChild;
子が２つあるノードの削除が難しい例
後継者を決める
private node getSuccessor ( node delNode ) {
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
while ( current != null) {
successorParent = successor;
successor = current;
current = current.leftChild;
}
if ( successor != delNode.rightChild ) {
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
riturn successor;
}
削除のプログラム
else {
Node successor = getSuccessor ( current );
if ( current = root ) root = successor;
else if ( isLeftChild )
parent.leftChhild = successor;
else parent.rightChild = successor;
successor.leftChild = current.LeftChild;
}
return true;
} // end of delete

Download Report