二分探索木における要素削除 データ構造とプログラミング（１０）

Presentation on theme: "二分探索木における要素削除 データ構造とプログラミング（１０）"— Presentation transcript:

1 二分探索木における要素削除 データ構造とプログラミング（１０）
大岩 元 慶応大学環境情報学部

2 節（ノード）の削除 削除するノードに子がない 削除するノードに子が１つある 削除するノードに子が２つある
削除するノードを見つけ、その親からの参照をnull にする 削除するノードに子が１つある 親の参照をそのノードの子への参照に変える 削除するノードに子が２つある そのノードの右の子の子孫の最小値を持つノードと入れ換え、必要な付け替えを行なう

3 削除するプログラム(最初の部分） 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;

4 子の無いノードを削除する if ( current.leftChild == null && current.rightChild == null ) { if ( current == root) root = null; else if ( isLeftChild ) parent.leftChild = null; else parent.rightChild = null; }

5 削除するノードに子が１つある 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;

6 子が２つあるノードの削除が難しい例

7 後継者を決める 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;

8 削除のプログラム 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