二分探索木における要素削除 データ構造とプログラミング（１０） 大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp
節（ノード）の削除 削除するノードに子がない 削除するノードに子が１つある 削除するノードに子が２つある 削除するノードを見つけ、その親からの参照を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