ڊيٽا جي جوڙجڪ: جاوا ۾ بائنري وڻ

هاءِ هاءِ! بنيادي ڄاڻ کان سواء هڪ مضبوط پروگرامر هجڻ ڏکيو آهي. ۽ هتي اسان جو مطلب آهي نه رڳو ڏيهي پروگرامنگ ٻولي جي نحو جي ڄاڻ، پر عام طور تي پروگرامنگ جا بنيادي ۽ تصورات. انهن بنيادن مان هڪ آهي الگورتھم ۽ ڊيٽا جي جوڙجڪ. ضابطي جي طور تي، ڪجهه هن مسئلي تي وڌيڪ ڄاڻ رکندڙ آهن، ڪجهه گهٽ، پر ڪجهه بنيادي معلومات آهي جيڪا هرڪو ڄاڻڻ گهرجي. ڊيٽا جي جوڙجڪ لاء ڊيٽابيس جي وچ ۾، اهو ضرور سمجهڻ جي قابل آهي بائنري ڳولا جي وڻن. دراصل، اڄ اسان ان جي خصوصيتن سان ساخت کي پاڻ ڏسنداسين ۽ معلوم ڪنداسين ته توهان جاوا ۾ هڪ بائنري وڻ ڪيئن لاڳو ڪري سگهو ٿا . پهرين، اچو ته اهو سمجهون ته بائنري وڻ ڇا آهي. هڪ بائنري وڻ هڪ ڊيٽا جي جوڙجڪ آهي جنهن ۾ هر نوڊ (والدين) کي وڌ ۾ وڌ ٻه ٻار آهن (ساڄي ۽ کاٻي وارث). عملي طور تي، ٻن قسمن جي بائنري وڻن کي عام طور تي استعمال ڪيو ويندو آهي - بائنري سرچ وڻ ۽ پرامڊ (هيپ). اڄ اسان هڪ بائنري ڳولا واري وڻ تي نظر ڪنداسين.

بائنري وڻ جا فائدا

بائنري سرچ وڻ جي طور تي ڊيٽا کي محفوظ ڪرڻ جو فائدو ڇا آهي؟ تصور ڪريو ته اسان وٽ ھڪڙو 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 سان نوڊ کي هٽائڻ کان پوءِ وڻ ڪهڙو نظر ايندو:

   ↓

هاڻي اهو وقت آهي عملي کان نظريي ڏانهن منتقل ڪرڻ جو. اچو ته هڪ نظر رکون ته اسان جاوا ۾ هن ڊيٽا جي جوڙجڪ کي ڪيئن نقشي ڪري سگهون ٿا. سنگل نوڊ ڪلاس:

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) تائين آهي . ان جو دارومدار وڻ جي خرابيءَ جي درجي تي آهي.

هڪ degenerate وڻ ڇا آهي؟

هي اهو وڻ آهي جنهن ۾ عناصر گر ٿي ويا جڏهن کاٻي پاسي واري نوڊ جي پوزيشن ۾ شامل ڪيو ويو (ننڍو نمبر) يا سڀ کان وڏو نوڊ (سڀ کان وڏو). اهو ٿي سگهي ٿو، مثال طور، سڄو کاٻي وڻ هر سطح تي خالي آهي، اتي صرف ساڄي وڻ آهن، ان صورت ۾ وڻ هڪ فهرست ۾ تبديل ٿي وڃي (ساڄي طرف وڃي). ها، اهڙيءَ طرح هڪ خراب ٿيل وڻ مؤثر طور تي هڪ واحد ڳنڍيل فهرست بڻجي ويندو آهي، جنهن ۾ هر عنصر صرف ان جي اڳيان هڪ جي باري ۾ ڄاڻندو آهي. ھن حالت ۾، ھن ڍانچي تي سڀني عملن کي O (N) جي وقت جي پيچيدگي سان ملندو آھي .

ڪهڙي صورت ۾ وڻ خراب ٿي سگهي ٿو؟

مثال طور، جيڪڏهن توهان ترتيب ڏنل عناصر جي فهرست شامل ڪريو. جيڪڏهن فهرست کي ترتيب ڏنل ترتيب سان ترتيب ڏنل آهي، ته روٽ پهريون هوندو، ترتيب سان سڀ کان ننڍو. هن کان پوء ايندڙ هڪ صحيح ٻار جي حيثيت وٺي ويندي. ۽ جيڪو بعد ۾ ايندو، اهو ٻئي کان وڏو هوندو ۽ پنهنجي ساڄي جانشين جي حيثيت وٺندو، وغيره وغيره... جيڪڏهن فهرست نزول جي ترتيب ۾ آهي، ته پوءِ ساڳيو ئي ٿيندو، پر کاٻي ڌر جي عنصرن سان. هن کان بچڻ لاء، ڪيترن ئي عناصر حاصل ڪرڻ کان پوء، توهان صرف انهن کي گڏ ڪري سگهو ٿا. پوءِ ڇنڊڇاڻ غائب ٿي ويندي، ۽ انگ گهٽ ۾ گهٽ هڪجهڙائي سان سڄي وڻ ۾ پکڙجي ويندا. اهو سڀ ڪجهه اڄ لاءِ آهي، توهان جي توجه جي مهرباني!