JavaRush /Java Blog /Random-JA /データ構造: Java のバイナリツリー

レベル 36

28 February 2021
35 views
0 comments

データ構造: Java のバイナリツリー

こんにちは、こんにちは！基本的な知識がなければ、強力なプログラマーになることは困難です。ここでは、ネイティブプログラミング言語の構文の知識だけでなく、プログラミング一般の基礎と概念も意味します。これらの基盤の 1 つはアルゴリズムとデータ構造です。一般に、この問題について詳しい人もいるし、知識が少ない人もいますが、誰もが知っておくべき基本的な情報がいくつかあります。データ構造のデータベースの中でも、二分探索ツリーを理解することは間違いなく価値があります。データ構造: Java のバイナリツリー - 1

実際、今日は構造そのものとその機能を見て、Java でバイナリツリーを実装する方法を見ていきます。まず、二分木とは何かを理解しましょう。バイナリツリーは、各ノード (親) が最大 2 つの子 (右と左の継承者) を持つデータ構造です。データ構造: Java のバイナリツリー - 2

実際には、二分探索ツリーとピラミッド(ヒープ) という 2 種類のバイナリツリーが一般的に使用されます。今日は二分探索木について見ていきます。

バイナリーツリーの利点

データを二分探索木として保存する利点は何ですか? 100 ページの参考書があり、必要なデータが含まれる特定のページを見つける必要があると想像してください。また、コンテンツからどの特定のページが必要なのかもわかります。通常の道をたどると、必要なページに到達するまで一度に 1 ページをめくる必要があります。つまり、適切な場所が見つかるまで 1 ページから 100 ページまで読み進めます。たとえば、77 ページが必要な場合、77 回の検索が必要になります。時間計算量について言えば、O(N)になります。しかし、これはもっと効率的に行うことができますよね? 同じことを二分探索を使用して実行してみましょう。

ディレクトリを 2 つの部分に分割します。最初の部分は 1 から 50、2 番目の部分は 51 ～ 100 です。私たちは、ページがこれらのどの部分にあるかを正確に知っています。もう一度 77 ページを見ると、それは本の第 2 部にあります。
次に、2 番目の部分を検討し、51 から 75、76 から 100 の 2 つに分割します。この場合、ページは再び後半、76 から 100 の範囲になります。
次に、この間隔を 2 で割ると、76 ～ 88 と 89 ～ 100 が得られます。ページは最初のギャップに収まるので、2 番目のギャップは破棄します。
次はインターバルです。76 ～ 81 と 82 ～ 88、最初のものを取ります。
76-78、79-81で先制する。
76、77-78で2本目を奪う。
77 と 78、最初のものを選択し、ページ 77 を取得します。

77 ステップではなく、7 ステップしか必要ありませんでした。この検索の時間計算量はO(log(N))になります。

二分探索木を構築するためのルール

二分探索ツリーは、特定のルールに従って構築されます。

各ノードには最大 2 つの子があります。
ノードの値より小さい値はすべて、左の子または左の子の子になります。
ノードの値以上のすべての値が、右の子または右の子の子になります。

たとえば、1 から 10 までの一連の数値があります。この系列の二分探索木がどのようになるかを見てみましょう: データ構造: Java のバイナリツリー - 3

ここで、二分木のすべての条件が満たされるかどうかを考えてみましょう:

すべてのノードに継承者が 2 人以下である場合、最初の条件が満たされます。
たとえば、値 7 (またはその他) を持つノードを考慮すると、左側のサブツリーの要素のすべての値が小さくなり、右側の要素の値が大きくなることがわかります。これは、条件 2 と 3 が満たされていることを意味します。

基本的な操作 (挿入、削除、検索) がどのように行われるかを見てみましょう。

要素を検索する

指定された値を持つ要素を検索する場合は、ルート要素から開始します。

求めた値と等しい場合はルート要素が求められたものとなり、そうでない場合はルート要素と求められた値を比較します。
探している要素が大きい場合は右側の子に移動し、そうでない場合は左側の子に移動します。
要素が見つからない場合は、要素が見つかるまで子 (右または左) に手順 1 と 2 を適用します。

たとえば、上に示した二分探索ツリーで、値 5 を持つ要素を見つけたいとします。

これをルート要素と比較すると、ルート要素の方が大きいことがわかり、値 3 を持つ左側の子に移動します。
探している要素と値 3 の要素を比較すると、探している要素の方が大きいことがわかります。そのため、問題の要素の正しい子孫、つまり値 5 の要素が必要です。
この子孫を探している子孫と比較し、値が等しいこと、つまり要素が見つかったことを確認します。

要素の挿入

挿入アルゴリズムも非常にシンプルです。

新しい要素とルート要素を比較します (存在しない場合は、新しい要素がルート要素になります)。
新しい要素の場合:
- が小さい場合は、左の継承者に進みます。存在しない場合は、新しい要素が左の継承者の代わりになり、アルゴリズムは完了します。
- がルート以上である場合は、右の継承者に進みます。同様に、この要素が存在しない場合は、新しい要素が正しい要素の代わりになり、アルゴリズムは完了します。
前のステップの右側または左側にある問題の新しい要素について、挿入された要素が配置されるまでステップ 1 と 2 を繰り返します。

例として、上で検討したツリーに値 11 の要素を挿入するとします。
- ルート要素 7 と比較すると、ルート要素の方が小さいことがわかり、右の継承者に進みます。
- 考慮中の次の要素の値は 9 で、新しい 11 よりも小さいため、右の継承要素に進みます。
- 右の継承者の値は 10 ですが、これも小さいため、最初の要素に移動します。そこには存在しないため、値 11 の新しい要素がこの場所に配置されます。
↓

要素の削除

おそらく、二分探索木を使ったすべての操作の中で、削除が最も難しいでしょう。まず最初に、削除する要素が検索され、その後に続くステージが特定されます。これには 3 つのバリエーションがあります。

削除するノードはリーフノード (子を持たない) です。

おそらく最も単純です。それはすべて、不必要な操作を行わずに単に木から切り取ったという事実に帰着します。たとえば、ツリーから値 8 のノードを削除します。
↓
削除されるノードには 1 つの子があります。

この場合、選択したノードを削除し、その子孫をその場所に置きます (本質的には、選択したノードをチェーンから単に切断するだけです)。例として、値 9 のノードをツリーから削除してみましょう。
↓
削除されるノードには 2 つの子があります。

最も興味深い部分です。結局のところ、削除されるノードに同時に 2 つの子がある場合、単純にこれらの子の 1 つで置き換えることはできません (特に、その子に独自の子がある場合)。

例:上のツリーでは、どのノードがノード 3 の左側の子になるでしょうか?

少し考えてみれば、これが値 4 のノードであるべきであることは明らかです。しかし、ツリーがそれほど単純ではない場合はどうなるでしょうか。数百の値が保持されている場合、後継者が誰になるかを判断するのはそれほど簡単でしょうか?

ノーであることは明らかです。したがって、独自の小型受信機検索アルゴリズムが必要です。
1. まず、選択したノードの右側の子に移動する必要があります。その値はノードの値より大きくなければなりません。
2. 次に、右の子の左の子 (存在する場合)、次に左の子の左の子というように、左の子のチェーンをたどります。
3. したがって、このパス上で最後に残った子が元のノードの後継ノードになります。
この小さなアルゴリズムを少し一般化してみましょう。ソースノードの右側の子のサブツリーでは、すべてのノードが削除されるノードよりも大きくなります。これは、二分探索木の基本規則から理解できます。このサブツリーでは、最小値を探します。

言い換えれば、元のノードよりも大きいノードのセットの中で最小のノードを探します。大きなノードの中でこの最小のノードが、最も適切な後継ノードになります。

値 3 のノードを削除した後のツリーは次のようになります。
↓

今度は実践から理論に移ります。Java でこのデータ構造をマッピングする方法を見てみましょう。単一ノードクラス:

class Node {
   private int value; // ключ узла
   private Node leftChild; // Левый узел потомок
   private Node rightChild; // Правый узел потомок

   public void printNode() { // Вывод значения узла в консоль
       System.out.println(" Выбранный узел имеет meaning :" + value);
   }

   public int getValue() {
       return this.value;
   }

   public void setValue(final int value) {
       this.value = value;
   }

   public Node getLeftChild() {
       return this.leftChild;
   }

   public void setLeftChild(final Node leftChild) {
       this.leftChild = leftChild;
   }

   public Node getRightChild() {
       return this.rightChild;
   }

   public void setRightChild(final Node rightChild) {
       this.rightChild = rightChild;
   }

   @Override
   public String toString() {
       return "Node{" +
               "value=" + value +
               ", leftChild=" + leftChild +
               ", rightChild=" + rightChild +
               '}';
   }
}

それほど複雑なことはありません。各要素にはその左右の子へのリンクがあります。そしておそらく、最も重要なクラスはツリークラスです。

class Tree {
   private Node rootNode; // корневой узел

   public Tree() { // Пустое дерево
       rootNode = null;
   }

   public Node findNodeByValue(int value) { // поиск узла по значению
       Node currentNode = rootNode; // начинаем поиск с корневого узла
       while (currentNode.getValue() != value) { // поиск покуда не будет найден элемент or не будут перебраны все
           if (value < currentNode.getValue()) { // движение влево?
               currentNode = currentNode.getLeftChild();
           } else { //движение вправо
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null) { // если потомка нет,
               return null; // возвращаем null
           }
       }
       return currentNode; // возвращаем найденный элемент
   }

   public void insertNode(int value) { // метод вставки нового element
       Node newNode = new Node(); // создание нового узла
       newNode.setValue(value); // вставка данных
       if (rootNode == null) { // если корневой узел не существует
           rootNode = newNode;// то новый элемент и есть корневой узел
       }
       else { // корневой узел занят
           Node currentNode = rootNode; // начинаем с корневого узла
           Node parentNode;
           while (true) // мы имеем внутренний выход из цикла
           {
               parentNode = currentNode;
               if(value == currentNode.getValue()) {   // если такой элемент в дереве уже есть, не сохраняем его
                    return;    // просто выходим из метода
                }
                else  if (value < currentNode.getValue()) {   // движение влево?
                   currentNode = currentNode.getLeftChild();
                   if (currentNode == null){ // если был достигнут конец цепочки,
                       parentNode.setLeftChild(newNode); //  то вставить слева и выйти из методы
                       return;
                   }
               }
               else { // Или направо?
                   currentNode = currentNode.getRightChild();
                   if (currentNode == null) { // если был достигнут конец цепочки,
                       parentNode.setRightChild(newNode);  //то вставить справа
                       return; // и выйти
                   }
               }
           }
       }
   }

   public boolean deleteNode(int value) // Удаление узла с заданным ключом
   {
       Node currentNode = rootNode;
       Node parentNode = rootNode;
       boolean isLeftChild = true;
       while (currentNode.getValue() != value) { // начинаем поиск узла
           parentNode = currentNode;
           if (value < currentNode.getValue()) { // Определяем, нужно ли движение влево?
               isLeftChild = true;
               currentNode = currentNode.getLeftChild();
           }
           else { // or движение вправо?
               isLeftChild = false;
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null)
               return false; // yзел не найден
       }

       if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { // узел просто удаляется, если не имеет потомков
           if (currentNode == rootNode) // если узел - корень, то дерево очищается
               rootNode = null;
           else if (isLeftChild)
               parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя
           else
               parentNode.setRightChild(null);
       }
       else if (currentNode.getRightChild() == null) { // узел заменяется левым поддеревом, если правого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getLeftChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getLeftChild());
           else
               parentNode.setRightChild(currentNode.getLeftChild());
       }
       else if (currentNode.getLeftChild() == null) { // узел заменяется правым поддеревом, если левого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getRightChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getRightChild());
           else
               parentNode.setRightChild(currentNode.getRightChild());
       }
       else { // если есть два потомка, узел заменяется преемником
           Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла
           if (currentNode == rootNode)
               rootNode = heir;
           else if (isLeftChild)
               parentNode.setLeftChild(heir);
           else
               parentNode.setRightChild(heir);
       }
       return true; // элемент успешно удалён
   }

   // метод возвращает узел со следующим meaningм после передаваемого аргументом.
   // для этого он сначала переходим к правому потомку, а затем
   // отслеживаем цепочку левых потомков этого узла.
   private Node receiveHeir(Node node) {
       Node parentNode = node;
       Node heirNode = node;
       Node currentNode = node.getRightChild(); // Переход к правому потомку
       while (currentNode != null) // Пока остаются левые потомки
       {
           parentNode = heirNode;// потомка задаём How текущий узел
           heirNode = currentNode;
           currentNode = currentNode.getLeftChild(); // переход к левому потомку
       }
       // Если преемник не является
       if (heirNode != node.getRightChild()) // правым потомком,
       { // создать связи между узлами
           parentNode.setLeftChild(heirNode.getRightChild());
           heirNode.setRightChild(node.getRightChild());
       }
       return heirNode;// возвращаем приемника
   }

   public void printTree() { // метод для вывода дерева в консоль
       Stack globalStack = new Stack(); // общий стек для значений дерева
       globalStack.push(rootNode);
       int gaps = 32; // начальное meaning расстояния между elementми
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack localStack = new Stack(); // локальный стек для задания потомков element
           isRowEmpty = true;

           for (int j = 0; j < gaps; j++)
               System.out.print(' ');
           while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
               Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека
               if (temp != null) {
                   System.out.print(temp.getValue()); // выводим его meaning в консоли
                   localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего element
                   localStack.push(temp.getRightChild());
                   if (temp.getLeftChild() != null ||
                           temp.getRightChild() != null)
                       isRowEmpty = false;
               }
               else {
                   System.out.print("__");// - если элемент пустой
                   localStack.push(null);
                   localStack.push(null);
               }
               for (int j = 0; j < gaps * 2 - 2; j++)
                   System.out.print(' ');
           }
           System.out.println();
           gaps /= 2;// при переходе на следующий уровень расстояние между elementми каждый раз уменьшается
           while (localStack.isEmpty() == false)
               globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
       }
       System.out.println(separator);// подводим черту
   }
}

繰り返しますが、それほど複雑なことはありません。前述した二分探索ツリー操作に加えて、コンソールにツリーを表示するメソッドが存在します。さて、実際にツリーが動作している様子を見てみましょう。

public class Application {
   public static void main(String[] args) {
       Tree tree = new Tree();
       // вставляем узлы в дерево:
       tree.insertNode(6);
       tree.insertNode(8);
       tree.insertNode(5);
       tree.insertNode(8);
       tree.insertNode(2);
       tree.insertNode(9);
       tree.insertNode(7);
       tree.insertNode(4);
       tree.insertNode(10);
       tree.insertNode(3);
       tree.insertNode(1);
       // отображение дерева:
       tree.printTree();

       // удаляем один узел и выводим оставшееся дерево в консоли
       tree.deleteNode(5);
       tree.printTree();

       // находим узел по значению и выводим его в консоли
       Node foundNode = tree.findNodeByValue(7);
       foundNode.printNode();
   }
}

二分探索ツリーでの検索/挿入/削除操作の時間計算量はO(log(N))です。しかし、それは最良のシナリオです。一般に、操作の時間計算量はO(log(N))からO(N)の範囲になります。それは木の退化の程度によって異なります。

退化木とは何ですか?

これは、要素が左端のノード (最小番号) または最大ノード (最大) の位置に追加されたときに含まれるツリーです。これは、たとえば、左側のツリー全体が各レベルで空で、右側のツリーのみが存在する場合に発生する可能性があります。この場合、ツリーはリストに縮退します (右に進みます)。はい、これが、縮退ツリーが事実上、各要素がその隣の要素についてのみ認識する単一リンクリストになる方法です。この場合、この構造体に対するすべての操作はO(N)の時間計算量に近づきます。

どのような場合に木が退化する可能性がありますか?

たとえば、並べ替えられた要素のリストを追加するとします。リストが昇順でソートされている場合、ルートが最初になり、それぞれが最小になります。彼の次の子が右の子の位置を占めます。そして、その後に来るものは 2 番目のものよりも大きく、その右の後続者の位置を占めます。以下同様です...リストが降順の場合、同じことが起こりますが、最も左の要素が使用されます。これを回避するには、多数の要素を受け取った後、それらを単に混合するだけです。その後、並べ替えはなくなり、数値はツリー全体にほぼ均等に分散されます。データ構造: Java のバイナリツリー - 13

今日はここまでです、ご清聴ありがとうございました！

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION

データ構造: Java のバイナリ ツリー