بائنری ٹری یا بائنری سرچ ٹری تیار کرنے کا طریقہ

پیشی

یہ مضمون بائنری تلاش کے درختوں کے بارے میں ہے۔ میں نے حال ہی میں ایک مضمون کیا تھا Huffman طریقہ کا استعمال کرتے ہوئے ڈیٹا کمپریشن. وہاں میں نے بائنری درختوں پر زیادہ توجہ نہیں دی، کیونکہ تلاش، اندراج، اور حذف کرنے کے طریقے متعلقہ نہیں تھے۔ اب میں نے درختوں کے بارے میں ایک مضمون لکھنے کا فیصلہ کیا۔ آو شروع کریں.

درخت ایک ڈیٹا ڈھانچہ ہے جو کناروں سے جڑے ہوئے نوڈس پر مشتمل ہوتا ہے۔ ہم کہہ سکتے ہیں کہ درخت گراف کا ایک خاص معاملہ ہے۔ یہاں ایک مثال درخت ہے:

یہ بائنری تلاش کا درخت نہیں ہے! سب کچھ کٹ گیا ہے!

اصطلاحات

روٹ

درخت کی جڑ - یہ اس کا سب سے اوپر والا نوڈ ہے۔ مثال میں، یہ نوڈ اے ہے۔ درخت میں، صرف ایک راستہ جڑ سے کسی دوسرے نوڈ تک لے جا سکتا ہے! درحقیقت، کسی بھی نوڈ کو اس نوڈ سے مماثل ذیلی درخت کی جڑ سمجھا جا سکتا ہے۔

والدین/اولاد

جڑ کے علاوہ تمام نوڈس کا بالکل ایک کنارہ ہوتا ہے جو دوسرے نوڈ تک جاتا ہے۔ موجودہ کے اوپر واقع نوڈ کہا جاتا ہے۔ والدین یہ نوڈ. ایک نوڈ جو موجودہ کے نیچے واقع ہے اور اس سے جڑا ہوا ہے کہلاتا ہے۔ اولاد یہ نوڈ. آئیے ایک مثال استعمال کرتے ہیں۔ آئیے نوڈ B لیتے ہیں، تو اس کے والدین نوڈ A ہوں گے، اور اس کے بچے نوڈ D، E اور F ہوں گے۔

لیف

ایک نوڈ جس کی کوئی اولاد نہ ہو اسے درخت کا پتا کہا جائے گا۔ مثال میں، پتے ڈی، ای، ایف، جی، آئی، جے، کے نوڈس ہوں گے۔

یہ بنیادی اصطلاح ہے۔ دیگر تصورات پر مزید بحث کی جائے گی۔ لہذا، ایک بائنری درخت ایک درخت ہے جس میں ہر نوڈ میں دو سے زیادہ بچے نہیں ہوں گے۔ جیسا کہ آپ نے اندازہ لگایا، مثال سے درخت بائنری نہیں ہوگا، کیونکہ نوڈس B اور H کے دو سے زیادہ بچے ہیں۔ یہاں ایک بائنری درخت کی ایک مثال ہے:

درخت کے نوڈس میں کوئی بھی معلومات ہوسکتی ہیں۔ بائنری سرچ ٹری ایک بائنری ٹری ہے جس میں درج ذیل خصوصیات ہیں:

1. بائیں اور دائیں دونوں ذیلی درخت بائنری سرچ ٹری ہیں۔
2. صوابدیدی نوڈ X کے بائیں ذیلی درخت کے تمام نوڈس میں ڈیٹا کلید کی قدریں خود نوڈ X کی ڈیٹا کلید کی قدر سے کم ہوتی ہیں۔
3. صوابدیدی نوڈ X کے دائیں سب ٹری میں تمام نوڈس میں ڈیٹا کلید کی قدریں خود نوڈ X کی ڈیٹا کلید کی قدر سے زیادہ یا اس کے برابر ہوتی ہیں۔

کلیدی - نوڈ کی کوئی خصوصیت (مثال کے طور پر، ایک نمبر)۔ کلید کی ضرورت ہے تاکہ آپ درخت کا وہ عنصر تلاش کر سکیں جس سے یہ کلید مطابقت رکھتی ہے۔ بائنری سرچ ٹری کی مثال:

درخت کا نظارہ

جیسے جیسے ہم آگے بڑھیں گے، میں آپ کی سمجھ کو بہتر بنانے کے لیے کوڈ کے کچھ (ممکنہ طور پر نامکمل) ٹکڑے فراہم کروں گا۔ مکمل کوڈ مضمون کے آخر میں ہوگا۔

ایک درخت نوڈس پر مشتمل ہوتا ہے۔ نوڈ کی ساخت:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }
    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }
//...остальные методы узла
}

ہر نوڈ میں دو بچے ہوتے ہیں (یہ بالکل ممکن ہے کہ لیفٹ چائلڈ اور/یا رائٹ چائلڈ بچوں میں null قدر ہو گی)۔ آپ نے شاید محسوس کیا ہے کہ اس معاملے میں نمبر ڈیٹا نوڈ میں محفوظ کردہ ڈیٹا ہے۔ کلید - نوڈ کلید۔

ہم نے گرہ چھانٹ لی ہے، اب بات کرتے ہیں درختوں سے متعلق مسائل کو دبانے کے بارے میں۔ اس کے بعد، لفظ "درخت" سے میرا مطلب بائنری سرچ ٹری کا تصور ہوگا۔ بائنری درخت کی ساخت:

public class BinaryTree<T> {
     private Node<T> root;

    //методы дерева
}

ہمیں صرف ایک کلاس فیلڈ کے طور پر درخت کی جڑ کی ضرورت ہے، کیونکہ جڑ سے، getLeftChild() اور getRightChild() طریقوں کا استعمال کرتے ہوئے، آپ درخت میں کسی بھی نوڈ تک جا سکتے ہیں۔

ایک درخت میں الگورتھم

تلاش

ہم کہتے ہیں کہ آپ کے پاس ایک تعمیر شدہ درخت ہے۔ کلیدی کلید کے ساتھ ایک عنصر کو کیسے تلاش کریں؟ آپ کو ترتیب وار جڑ سے درخت کے نیچے جانے کی ضرورت ہے اور کلید کی قدر کا اگلے نوڈ کی کلید سے موازنہ کرنا ہوگا: اگر کلید اگلے نوڈ کی کلید سے کم ہے، تو نوڈ کے بائیں نسل پر جائیں، اگر یہ ہے زیادہ سے زیادہ، دائیں طرف، اگر چابیاں برابر ہیں، تو مطلوبہ نوڈ مل جائے گا! متعلقہ کوڈ:

public Node<T> find(int key) {
    Node<T> current = root;
    while (current.getKey() != key) {
        if (key < current.getKey())
            current = current.getLeftChild();
        else
            current = current.getRightChild();
        if (current == null)
            return null;
    }
    return current;
}

اگر کرنٹ کالعدم ہو جاتا ہے، تو تلاش درخت کے اختتام تک پہنچ گئی ہے (ایک تصوراتی سطح پر، آپ درخت میں ایک غیر موجود جگہ پر ہیں - ایک پتی کی اولاد)۔

آئیے متوازن درخت (ایک درخت جس میں نوڈس کو کم و بیش یکساں طور پر تقسیم کیا جاتا ہے) پر سرچ الگورتھم کی تاثیر پر غور کریں۔ پھر تلاش کی کارکردگی O(log(n)) ہوگی، اور لاگرتھم بیس 2 ہے۔ دیکھو: اگر متوازن درخت میں n عناصر موجود ہیں، تو اس کا مطلب ہے کہ log(n) کی بنیاد 2 سطحوں پر ہوگی۔ درخت اور تلاش میں، سائیکل کے ایک قدم میں، آپ ایک درجے نیچے چلے جاتے ہیں۔

داخل

اگر آپ تلاش کے جوہر کو سمجھتے ہیں تو آپ کے لیے اندراج کو سمجھنا مشکل نہیں ہوگا۔ آپ کو صرف درخت کے ایک پتے کے نیچے جانے کی ضرورت ہے (تلاش میں بیان کردہ نزول کے قواعد کے مطابق) اور اس کی اولاد بننے کی ضرورت ہے - بائیں یا دائیں، کلید پر منحصر ہے۔ نفاذ:

   public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

اس صورت میں، موجودہ نوڈ کے علاوہ، موجودہ نوڈ کے والدین کے بارے میں معلومات کو ذخیرہ کرنا ضروری ہے۔ جب کرنٹ null کے برابر ہو جاتا ہے تو پیرنٹ متغیر میں وہ شیٹ ہو گی جس کی ہمیں ضرورت ہے۔
اندراج کی کارکردگی ظاہر ہے وہی ہوگی جو تلاش کی ہوگی - O(log(n))۔

حذف کریں۔

ہٹانا سب سے مشکل آپریشن ہے جسے درخت پر انجام دینے کی ضرورت ہوگی۔ یہ واضح ہے کہ پہلے ہمیں اس عنصر کو تلاش کرنے کی ضرورت ہوگی جسے ہم حذف کرنے جا رہے ہیں۔ لیکن پھر کیا؟ اگر ہم صرف اس کا حوالہ null پر سیٹ کرتے ہیں، تو ہم اس ذیلی درخت کے بارے میں معلومات کھو دیں گے جس کا یہ نوڈ جڑ ہے۔ درختوں کو ہٹانے کے طریقوں کو تین صورتوں میں تقسیم کیا گیا ہے۔

پہلا کیس۔ جس نوڈ کو حذف کیا جا رہا ہے اس کی کوئی اولاد نہیں ہے۔

اگر حذف کیے جانے والے نوڈ کے کوئی بچے نہیں ہیں، تو اس کا مطلب ہے کہ یہ ایک پتی ہے۔ لہذا، آپ آسانی سے اس کے والدین کے لیفٹ چائلڈ یا رائٹ چائلڈ فیلڈز کو کالعدم کر سکتے ہیں۔

دوسرا کیس۔ حذف کیے جانے والے نوڈ کا ایک بچہ ہے۔

یہ معاملہ بھی زیادہ پیچیدہ نہیں ہے۔ آئیے اپنی مثال کی طرف لوٹتے ہیں۔ ہم کہتے ہیں کہ ہمیں کلید 14 کے ساتھ ایک عنصر کو حذف کرنے کی ضرورت ہے۔ اس بات سے اتفاق کریں کہ چونکہ یہ کلید 10 والے نوڈ کی صحیح اولاد ہے، تو اس کی اولاد میں سے کسی کے پاس (اس صورت میں دائیں والے) کی 10 سے بڑی کلید ہوگی، لہذا آپ اسے درخت سے آسانی سے "کاٹ" سکتا ہے، اور والدین کو براہ راست حذف کیے جانے والے نوڈ کے بچے سے جوڑ سکتا ہے، یعنی نوڈ کو کلید 10 کے ساتھ نوڈ 13 سے جوڑیں۔ صورت حال ایسی ہی ہوگی اگر کسی نوڈ کو حذف کرنا ضروری ہوتا جو اس کے والدین کا بائیں بچہ ہے۔ اس کے بارے میں خود سوچیں - ایک عین مطابق تشبیہ۔

تیسرا کیس۔ ایک نوڈ کے دو بچے ہوتے ہیں۔

سب سے مشکل کیس۔ آئیے ایک نئی مثال دیکھتے ہیں۔

جانشین کی تلاش کریں۔

ہم کہتے ہیں کہ ہمیں کلید 25 کے ساتھ ایک نوڈ کو حذف کرنے کی ضرورت ہے۔ اس کی جگہ ہمیں کس کو رکھنا چاہئے؟ اس کے پیروکاروں میں سے (اولاد یا اولاد کی اولاد) بننا ضروری ہے۔ جانشین(وہ جو ہٹائے جانے والے نوڈ کی جگہ لے گا)۔

جانشین کون بننا چاہئے یہ کیسے سمجھیں؟ بدیہی طور پر، یہ درخت میں ایک نوڈ ہے جس کی کلید حذف کیے جانے والے نوڈ سے اگلی سب سے بڑی ہے۔ الگورتھم مندرجہ ذیل ہے۔ آپ کو اس کے دائیں نسل پر جانے کی ضرورت ہے (ہمیشہ دائیں طرف، کیونکہ یہ پہلے ہی کہا جا چکا ہے کہ جانشین کی کلید حذف کیے جانے والے نوڈ کی کلید سے بڑی ہے)، اور پھر اس دائیں نسل کے بائیں اولاد کی زنجیر سے گزریں۔ . مثال میں، ہم کلید 35 کے ساتھ نوڈ پر جائیں گے، اور پھر اس کے بائیں بچوں کی زنجیر کے ذریعے پتی تک جائیں گے - اس صورت میں، یہ سلسلہ صرف کلید 30 والے نوڈ پر مشتمل ہے۔ نوڈس کے سیٹ میں سب سے چھوٹے نوڈ کے لیے جس سے ہم نوڈ تلاش کر رہے ہیں۔

جانشین تلاش کے طریقہ کار کوڈ:

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;//родитель преемника
        Node<T> successor = deleteNode;//преемник
        Node<T> current = successor.getRightChild();//просто "пробегающий" узел
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        //на выходе из цикла имеем преемника и родителя преемника
        if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
            parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
            successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
        }
        return successor;
    }

حذف کرنے کے طریقہ کار کے لیے مکمل کوڈ:

public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;//В зависимости от того, является ли  удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {//второй случай
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {//третий случай
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

پیچیدگی O(log(n)) کے قریب لگائی جا سکتی ہے۔

درخت میں زیادہ سے زیادہ/کم سے کم تلاش کرنا

یہ واضح ہے کہ درخت میں کم از کم/زیادہ سے زیادہ قدر کیسے تلاش کی جائے - آپ کو ترتیب وار درخت کے بائیں/دائیں عناصر کی زنجیر کے ساتھ آگے بڑھنے کی ضرورت ہے۔ جب آپ شیٹ پر پہنچیں گے، تو یہ کم از کم/زیادہ سے زیادہ عنصر ہوگا۔

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

پیچیدگی - O(log(n))

سڈول بائی پاس

ٹراورسل درخت کے ہر نوڈ کا دورہ کر رہا ہے تاکہ اس کے ساتھ کچھ کارروائی کی جا سکے۔

بار بار چلنے والا ہم آہنگ ٹراورسل الگورتھم:

1. بائیں بچے پر عمل کریں۔
2. اپنے ساتھ ایک عمل کریں۔
3. صحیح بچے پر عمل کریں۔

کوڈ:

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
            inOrder(current.getRightChild());
        }
    }

حاصل يہ ہوا

آخرکار! اگر میں نے کچھ وضاحت نہیں کی ہے یا کوئی تبصرہ نہیں کیا ہے، تو براہ کرم انہیں تبصروں میں چھوڑ دیں۔ جیسا کہ وعدہ کیا گیا ہے، میں مکمل کوڈ فراہم کرتا ہوں۔

Node.java:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }

    public void setLeftChild(Node<T> newNode) {
        leftChild = newNode;
    }

    public void setRightChild(Node<T> newNode) {
        rightChild = newNode;
    }

    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }

    public T getData() {
        return data;
    }

    public int getKey() {
        return key;
    }
}

BinaryTree.java:

public class BinaryTree<T> {
    private Node<T> root;

    public Node<T> find(int key) {
        Node<T> current = root;
        while (current.getKey() != key) {
            if (key < current.getKey())
                current = current.getLeftChild();
            else
                current = current.getRightChild();
            if (current == null)
                return null;
        }
        return current;
    }

    public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;
        Node<T> successor = deleteNode;
        Node<T> current = successor.getRightChild();
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }

        if (successor != deleteNode.getRightChild()) {
            parentSuccessor.setLeftChild(successor.getRightChild());
            successor.setRightChild(deleteNode.getRightChild());
        }
        return successor;
    }

    public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");
            inOrder(current.getRightChild());
        }
    }
}

PS

O(n) میں تنزلی

آپ میں سے بہت سے لوگوں نے دیکھا ہوگا: اگر آپ درخت کو غیر متوازن کر دیں تو کیا ہوگا؟ مثال کے طور پر، ایک درخت میں بڑھتی ہوئی چابیاں کے ساتھ نوڈس ڈالیں: 1,2,3,4,5,6... پھر درخت کسی حد تک منسلک فہرست سے مشابہ ہوگا۔ اور ہاں، درخت اپنی درخت کی ساخت، اور اس وجہ سے ڈیٹا تک رسائی کی کارکردگی کھو دے گا۔ تلاش، اندراج، اور حذف کرنے کی کارروائیوں کی پیچیدگی ایک منسلک فہرست کی طرح ہو جائے گی: O(n)۔ یہ سب سے اہم میں سے ایک ہے، میری رائے میں، بائنری درختوں کے نقصانات۔

سروے میں صرف رجسٹرڈ صارفین ہی حصہ لے سکتے ہیں۔ سائن ان، برائے مہربانی.

میں بہت لمبے عرصے سے مرکز پر نہیں ہوں، اور میں جاننا چاہوں گا کہ آپ کن عنوانات پر مزید کون سے مضامین دیکھنا چاہیں گے؟

• ڈیٹا ڈھانچے

• الگورتھم (ڈی پی، تکرار، ڈیٹا کمپریشن، وغیرہ)

• حقیقی زندگی میں ڈیٹا ڈھانچے اور الگورتھم کا اطلاق

• جاوا میں پروگرامنگ اینڈرائیڈ ایپلی کیشنز

• جاوا میں پروگرامنگ ویب ایپلیکیشنز

2 صارفین نے ووٹ دیا۔ 1 صارف نے پرہیز کیا۔

ماخذ: www.habr.com