Java は、二分探索ツリーの検索、挿入、削除、および走査のグラフィック詳細を実装します。-＆＃＆チュートリアル-php.cn

この記事ではJavaで実装された二分探索木の検索、挿入、削除、走査などを主に紹介します。とても良い参考値なので、エディタで見てみましょう

最近、JDK1.8でのHashMapの具体的な実装について読みたいと思ったのですが、HashMapの実装は赤黒ツリーを使っているので、が必要ですまずは赤黒木に関する知識を復習してからこの作文メモを書きました間違いがあればご指摘ください〜

赤黒木を学ぶには二分探索木から始める必要があると思います。ということで、このエッセイは主に二分探索木の検索、挿入、削除、走査などを実装するJavaを紹介します。

二分探索木は次の 4 つの条件を満たす必要があります:

いずれかのノードの左サブツリーが空でない場合、左サブツリー上のすべてのノードの値はそのルートノードの値より小さい。

いずれかのノードの右側のサブツリーが空でない場合、右側のサブツリー上のすべてのノードの値がそのルートノードの値より大きい場合

任意のノードの左側と右側のサブツリーも二分探索ツリーです。それぞれ;

等しいキー値を持つノードはありません。

二分探索木の例:

図1

以下では、図1に基づいて二分探索木の関連する操作を紹介します。

まず、Node という名前の、ノードオブジェクトに関連するクラスが存在する必要があります。

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}

ログイン後にコピー

Node クラスには、ツリー内のノードの対応する位置を決定するために使用されるキー値が含まれています。この値は、保存されるコンテンツを表し、左右への 2 つの参照も含まれています。子ノード。

次に、検索ツリーの対応するクラスを見てみましょう:

class Tree {
 Node root;//保存树的根
 public Node find(int key) {//查找指定节点
 }
 public void insert(int key, int value) {//插入节点
 }
 public boolean delete(int key) {//删除指定节点
 }
 private Node getDirectPostNode(Node delNode) {//得到待删除节点的直接后继节点
 }
 public void preOrder(Node rootNode) {//先序遍历树
 }
 public void inOrder(Node rootNode) {//中序遍历树
 }
 public void postOrder(Node rootNode) {//后序遍历树
 }
}

ログイン後にコピー

ツリーのフレームワークは、検索、挿入、走査、削除メソッドを含むクラスで表現されます。その中には削除メソッドも含まれます。ノードは最も複雑な操作であるため、次に 1 つずつ紹介します。

1. ノードを検索します

二分探索木の定義の特殊性により、入力されたキー値がルートのキー値より小さい場合にのみルートから比較する必要があります。、ルートの左側のサブツリーと比較され、ルートより大きいキー値がルートの右側のサブツリーと比較されます。見つかった場合は、対応するノードが返され、それ以外の場合は null が返されます。

public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
}

ログイン後にコピー

2. ノード

の挿入は、二分探索木の特殊性により、挿入されるノードもルートノードから比較する必要があります。ルートノードより小さい場合は、ルートノードの左側のサブツリーと比較され、それ以外の場合は、左側のサブツリーまたは右側のサブツリーが空になるまで、右側のサブツリーと比較され、対応する空のノードに挿入されます。比較処理中は、親ノードの情報と挿入する情報の保存に注意してください。位置が親ノードの左側のサブツリーまたは右側のサブツリーの場合にのみ、正しい位置に挿入されます。

public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
}

ログイン後にコピー

3. 二分探索木を走査する

走査操作は通常の二分木を走査するのとまったく同じであるため、詳細は説明しません。

public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }

ログイン後にコピー

4. 指定したノードを削除します。

二分探索木におけるノードの削除操作は複雑であり、以下の3つの状況に分けられます。

1. 削除するノードはリーフノードなので直接削除できます。

public boolean delete(int key) {
 Node currentNode = root;//用来保存待删除节点
 Node parentNode = root;//用来保存待删除节点的父亲节点
 boolean isLeftChild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {//要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } 
 ......
 }

ログイン後にコピー

2. 削除するノードには子ノードが 1 つだけあります

たとえば、図 1 のキー値 11 のノードを削除するには、ノードの左側の子ノードをポイントするだけです。キー値 13 からキー値 12 のノードは、キー値 11 のノードを削除する目的を達成できます。

上記の分析から得られたコードは次のとおりです (その後に上記の delete メソッドの省略記号が続きます):

else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } 
 ......

ログイン後にコピー

3. 削除されるノードには左の子と右の子の両方があります。

たとえば、図1のキー値10のノードを削除する場合、キー値10のノードを、キー値10のノードの順序後継ノード(ノード11)に置き換える必要があります。、キー値 10 のノードを削除します。ノード 10 の順序後続ノードは、順序トラバーサルの関連ルールから知ることができます。キー値 10 のノードの直接の順序後続ノードは、次でなければなりません。したがって、この順序後続ノードは、子を含むノードまたは右の子を 1 つだけ含むノードであってはなりません。順序後続ノードを削除すると、上記の 1 および 2 で説明した状況に陥ります。図 1 では、キー値 10 を持つノードの直接の順序後続ノードは 11 で、ノード 11 には右側の子 12 が含まれています。

したがって、図 1 のキー値 10 のノードの削除は次の手順に分かれます:

a. キー値 10 のノードの直接の順序後続ノード (つまり、最小値を持つノード) を見つけます。その右側のサブツリー 11 の値を削除し、この直接の順序後続ノードを削除します。

private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
}

ログイン後にコピー

b. 後継ノードのキーと値を、削除するノードのキーと値に割り当てます。 (ケース2の省略記号コード以降)

else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
}

ログイン後にコピー

これで指定したノードの削除操作は終了です。

最後に、完全なコードと簡単なテストコードとテスト結果を示します:

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}
class Tree {
 Node root;
 public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
 }
 public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
 }
 public boolean delete(int key) {
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {
 //要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
 }
 return true;
 }
 private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
 }
 public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
 public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
 public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }
}
public class BinarySearchTreeApp {
 public static void main(String[] args) {
 Tree tree = new Tree();
 tree.insert(6, 6);//插入操作,构造图一所示的二叉树
 tree.insert(3, 3);
 tree.insert(14, 14);
 tree.insert(16, 16);
 tree.insert(10, 10);
 tree.insert(9, 9);
 tree.insert(13, 13);
 tree.insert(11, 11);
 tree.insert(12, 12);
 System.out.println("删除前遍历结果");
 tree.inOrder(tree.root);//中序遍历操作
 System.out.println("删除节点10之后遍历结果");
 tree.delete(10);//删除操作
 tree.inOrder(tree.root);
 }
}

ログイン後にコピー

テスト結果: