โครงสร้างข้อมูล: Binary Tree ใน Java

สวัสดี สวัสดี! เป็นการยากที่จะเป็นโปรแกรมเมอร์ที่แข็งแกร่งโดยไม่มีความรู้พื้นฐาน และในที่นี้เราไม่ได้หมายถึงเพียงความรู้เกี่ยวกับไวยากรณ์ของภาษาการเขียนโปรแกรมพื้นเมืองเท่านั้น แต่ยังรวมถึงพื้นฐานและแนวคิดของการเขียนโปรแกรมโดยทั่วไปด้วย รากฐานประการหนึ่งคืออัลกอริธึมและโครงสร้างข้อมูล ตามกฎแล้ว บางคนมีความรู้เกี่ยวกับปัญหานี้มากกว่า บางคนมีความรู้น้อยกว่า แต่มีข้อมูลพื้นฐานบางอย่างที่ทุกคนควรรู้ ในบรรดาฐานข้อมูลสำหรับโครงสร้างข้อมูล การทำความเข้าใจแผนผังการค้นหาแบบไบนารีนั้นคุ้มค่าอย่างแน่นอน จริงๆ แล้ว วันนี้เราจะดูโครงสร้างพร้อมฟีเจอร์ต่างๆ ของตัวมันเอง และดูว่าคุณสามารถใช้binary tree ใน 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 +
               '}';
   }
}

ไม่มีอะไรซับซ้อนเกินไป แต่ละองค์ประกอบมีลิงก์ไปยังลูกด้านซ้ายและขวา และตอนนี้บางทีคลาสที่สำคัญที่สุดคือคลาส tree:

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)

ต้นไม้จะเสื่อมสลายได้ในกรณีใด?

ตัวอย่างเช่น หากคุณเพิ่มรายการองค์ประกอบที่เรียงลำดับ หากรายการเรียงลำดับจากน้อยไปมาก รากจะเป็นอันดับแรก และเล็กที่สุดตามลำดับ คนถัดมาจะเข้ารับตำแหน่งลูกที่ถูกต้อง และอันที่ตามมาจะมีขนาดใหญ่กว่าอันที่สองและจะเข้ารับตำแหน่งผู้สืบทอดที่เหมาะสม และอื่น ๆ... หากรายการเรียงลำดับจากมากไปน้อยสิ่งเดียวกันก็จะเกิดขึ้น แต่มีองค์ประกอบซ้ายสุด เพื่อหลีกเลี่ยงปัญหานี้ หลังจากได้รับองค์ประกอบจำนวนหนึ่งแล้ว คุณสามารถผสมองค์ประกอบเหล่านั้นได้ จากนั้นการเรียงลำดับจะหายไป และตัวเลขจะกระจัดกระจายเท่าๆ กันทั่วทั้งต้นไม้ไม่มากก็น้อย นั่นคือทั้งหมดสำหรับวันนี้ ขอบคุณสำหรับความสนใจของคุณ!