מבני נתונים: עץ בינארי ב-Java

היי היי! קשה להיות מתכנת חזק בלי ידע בסיסי. וכאן אנו מתכוונים לא רק לידע בתחביר של שפת התכנות המקורית, אלא גם ליסודות ולמושגים של תכנות באופן כללי. אחד מהיסודות הללו הוא אלגוריתמים ומבני נתונים. ככלל, חלקם בקיאים יותר בנושא זה, חלקם פחות, אבל יש מידע בסיסי שכולם צריכים לדעת. בין מסדי הנתונים למבני נתונים, בהחלט כדאי להבין עצי חיפוש בינאריים. למעשה, היום נסתכל על המבנה עצמו עם התכונות שלו ונגלה כיצד ניתן ליישם עץ בינארי בג'אווה . ראשית, בואו נבין מהו עץ בינארי. עץ בינארי הוא מבנה נתונים שבו לכל צומת (הורה) יש לכל היותר שני ילדים (יורש ימני ושמאלי). בפועל, נפוץ שני סוגים של עצים בינאריים - עץ חיפוש בינארי ופירמידה ( ערימה ). היום נתבונן בעץ חיפוש בינארי.

היתרונות של עץ בינארי

מה היתרון באחסון נתונים כעץ חיפוש בינארי? תארו לעצמכם שיש לנו ספר עיון בן 100 עמודים ואנחנו צריכים למצוא עמוד ספציפי שיכיל את הנתונים שאנחנו צריכים. אנחנו גם יודעים מהתוכן איזה עמוד ספציפי אנחנו צריכים. אם נלך בדרך הרגילה, נצטרך להפוך עמוד אחד בכל פעם עד שנגיע לזה שאנחנו צריכים. כלומר, נעבור בין 1 ל-100 עמודים עד שנמצא את עצמנו במקום הנכון. לדוגמה, אם אנחנו צריכים את עמוד 77, אז יהיו לנו 77 חיפושים. אם נדבר על מורכבות זמן, אז זה יהיה O(N) . אבל זה יכול להיעשות בצורה יעילה יותר, נכון? בוא ננסה לעשות את אותו הדבר, אבל באמצעות חיפוש בינארי :

1. אנו מחלקים את הספרייה לשני חלקים, הראשון - מ-1 עד 50, השני - 51-100. אנחנו יודעים בדיוק באיזה מהחלקים האלה נמצא הדף שלנו: אם ניקח שוב את עמוד 77, זה בחלק השני של הספר.
2. לאחר מכן, נשקול את החלק השני ונחלק אותו לשניים - מ-51 עד 75, מ-76 עד 100. במקרה זה, הדף שלנו יהיה שוב במחצית השנייה, בטווח 76-100.
3. לאחר מכן, נחלק את המרווח הזה ב-2 ונקבל 76-88 ו-89-100. הדף מתאים לרווח הראשון, אז אנחנו פוסלים את השני.
4. בהמשך הם המרווחים: 76-81 ו-82-88, קח את הראשון.
5. 76-78 ו-79-81, קח את הראשון.
6. 76 ו-77-78, קח את השני.
7. 77 ו-78, קח את הראשון וקבל את הדף שלנו - 77.

במקום 77 ​​צעדים, היינו צריכים רק 7! מורכבות הזמן של חיפוש זה תהיה O(log(N)) .

כללים לבניית עץ חיפוש בינארי

עץ החיפוש הבינארי בנוי לפי כללים מסוימים:

• לכל צומת יש לכל היותר שני ילדים;
• כל ערך קטן מערכו של הצומת הופך לילד השמאלי או לילד של הילד השמאלי;
• כל ערך הגדול או שווה לערך הצומת הופך לילד הנכון או לילד של הילד הנכון.

לדוגמה, יש לנו סדרה של מספרים מ-1 עד 10. בוא נראה איך ייראה עץ החיפוש הבינארי של סדרה זו: בוא נחשוב אם כל התנאים של עץ בינארי מתקיימים כאן:

• לכל הצמתים אין יותר משני יורשים, התנאי הראשון מתקיים;
• אם נשקול, למשל, צומת עם הערך 7 (או כל אחר), נראה שכל הערכים של האלמנטים בתת-עץ השמאלי יהיו פחות, ובימין - יותר. המשמעות היא שמתקיימים תנאים 2 ו-3.

הבה נבחן כיצד מתרחשות הפעולות הבסיסיות - הכנסה, מחיקה, חיפוש.

חפש אלמנט

כאשר מחפשים אלמנט עם ערך נתון, אנו מתחילים באלמנט השורש:

1. אם הוא שווה לערך המבוקש, יסוד השורש הוא המבוקש; אם לא, נשווה בין ערכי השורש למבוקש.
2. אם האלמנט שאנו מחפשים גדול יותר, נעבור לילד הימני; אם לא, נעבור לילד השמאלי.
3. אם האלמנט לא נמצא, החל את שלבים 1 ו-2, אך על הילד (ימין או שמאל) עד ​​שהאלמנט נמצא.

לדוגמה, בעץ החיפוש הבינארי המוצג למעלה, אנו רוצים למצוא את האלמנט בעל הערך 5:

• אנחנו משווים את זה לאלמנט השורש, אנחנו רואים שאלמנט השורש גדול יותר, אז אנחנו עוברים לילד השמאלי, שיש לו ערך של 3;
• אנחנו משווים את זה שאנחנו מחפשים ואת האלמנט עם ערך 3, אנחנו רואים שהאחד שאנחנו מחפשים הוא גדול יותר, אז אנחנו צריכים את הצאצא הנכון של האלמנט המדובר, כלומר, האלמנט עם ערך 5;
• אנחנו משווים את הצאצא הזה לזה שאנחנו מחפשים ורואים שהערכים שווים - האלמנט נמצא.

הכנסת אלמנט

גם אלגוריתם ההכנסה הוא מאוד מאוד פשוט:

1. אנחנו משווים את החדש לשורש (אם הוא לא קיים, האלמנט החדש הוא השורש).

2. אם אלמנט חדש:

   • הוא פחות, אז אנחנו הולכים ליורש השמאלי; אם אין כזה, האלמנט החדש תופס את מקומו של היורש השמאלי, והאלגוריתם הושלם;
   • גדול או שווה לשורש, אז נעבור ליורש הנכון. ובדומה לכך, אם האלמנט הזה לא קיים, אז אלמנט חדש יתפוס את מקומו של האלמנט הנכון והאלגוריתם הושלם.

3. עבור האלמנט החדש המדובר, שהיה מימין או שמאל מהשלב הקודם, חזור על שלבים 1 ו-2 עד שהאלמנט שהוכנס למקומו.

   כדוגמה, נרצה להכניס לעץ הנחשב לעיל, אלמנט עם הערך 11:

   • אנחנו משווים לאלמנט השורש 7 ורואים שאלמנט השורש קטן יותר, אז אנחנו עוברים ליורש הנכון;
   • לרכיב הבא שנבחן יש ערך של 9, שהוא פחות מה-11 החדש, אז אנחנו עוברים ליורש הנכון;
   • ליורש הנכון יש ערך של 10, וזה שוב פחות, אז אנחנו הולכים ליסוד הראשון, ומכיוון שהוא לא שם, מרכיב חדש עם ערך של 11 ממוקם במקום הזה.
   ↓

הסרת אלמנט

אולי מכל הפעולות עם עצי חיפוש בינאריים, המחיקה היא הקשה ביותר. קודם כל, יש חיפוש אחר האלמנט שיימחק, ולאחר מכן מגיע שלב שיכול להיות בשלוש וריאציות:

1. הצומת שיימחק הוא צומת עלה (אין לו ילדים).

   אולי הכי פשוט. הכל מסתכם בעובדה שאנחנו פשוט חותכים אותו מהעץ, ללא מניפולציות מיותרות. לדוגמה, מהעץ שלנו אנו מסירים את הצומת עם הערך 8:

   ↓

2. לצומת שנמחק יש בן אחד.

   במקרה זה, אנו מוחקים את הצומת שנבחר ונשים את הצאצא שלו במקומו (בעצם, אנו פשוט חותכים את הצומת שנבחר מהשרשרת). כדוגמה, בוא נסיר מהעץ צומת עם ערך 9:

   ↓

3. לצומת שנמחק יש שני ילדים.

   החלק הכי מעניין. אחרי הכל, אם לצומת שנמחק יש שני ילדים בבת אחת, אתה לא יכול פשוט להחליף אותו באחד מהילדים האלה (במיוחד אם לילד יש ילדים משלו).

   דוגמה: בעץ למעלה, איזה צומת צריך להיות הילד השמאלי של צומת 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) .

באיזה מקרה יכול עץ להתנוון?

לדוגמה, אם תוסיף רשימה של אלמנטים ממוינים. אם הרשימה ממוינת בסדר עולה, השורש יהיה הראשון, בהתאמה הקטן ביותר. הבא אחריו יתפוס את עמדת הילד הנכון. וזה שיבוא אחריו יהיה גדול מהשני ויתפוס את עמדת היורש הימני שלו, וכן הלאה... אם הרשימה בסדר יורד, אז יקרה אותו דבר, אבל עם האלמנטים השמאליים ביותר. כדי למנוע זאת, לאחר קבלת מספר אלמנטים, אתה יכול פשוט לערבב אותם. אז ייעלם המיון, והמספרים יתפזרו פחות או יותר באופן שווה על פני העץ. זה הכל להיום, תודה על תשומת הלב!