🥇Binary Tree หรือวิธีเตรียมแผนผังการค้นหาแบบไบนารี

โหมโรง

บทความนี้เกี่ยวกับแผนผังการค้นหาแบบไบนารี ฉันเพิ่งทำบทความเกี่ยวกับ การบีบอัดข้อมูลด้วยวิธีฮัฟฟ์แมน ที่นั่นฉันไม่ได้สนใจไบนารีทรีมากนัก เนื่องจากวิธีการค้นหา การแทรก และการลบไม่เกี่ยวข้องกัน ตอนนี้ฉันตัดสินใจเขียนบทความเกี่ยวกับต้นไม้ มาเริ่มกันเลย.

ต้นไม้เป็นโครงสร้างข้อมูลที่ประกอบด้วยโหนดที่เชื่อมต่อกันด้วยขอบ เราสามารถพูดได้ว่าต้นไม้เป็นกรณีพิเศษของกราฟ นี่คือตัวอย่างต้นไม้:

นี่ไม่ใช่แผนผังการค้นหาแบบไบนารี! ตัดทุกอย่าง!

คำศัพท์

ราก

รากต้นไม้ - นี่คือโหนดบนสุด ในตัวอย่าง นี่คือโหนด A ในแผนผัง มีเพียงเส้นทางเดียวเท่านั้นที่สามารถนำจากรากไปยังโหนดอื่นได้! ในความเป็นจริง โหนดใด ๆ ถือได้ว่าเป็นรากของแผนผังย่อยที่สอดคล้องกับโหนดนี้

บิดามารดา/ทายาท

โหนดทั้งหมดยกเว้นรูทมีขอบเดียวที่นำไปสู่อีกโหนดหนึ่ง โหนดที่อยู่เหนือโหนดปัจจุบันเรียกว่า พ่อแม่ โหนดนี้ โหนดที่อยู่ด้านล่างโหนดปัจจุบันและเชื่อมต่อกับโหนดนั้นเรียกว่า ลูกหลาน โหนดนี้ ลองใช้ตัวอย่าง ลองใช้โหนด B จากนั้นพาเรนต์ของมันจะเป็นโหนด A และลูกของมันจะเป็นโหนด D, E และ F

แผ่น

โหนดที่ไม่มีลูกจะเรียกว่าใบไม้ของต้นไม้ ในตัวอย่าง ใบไม้จะเป็นโหนด D, E, F, G, I, J, K

นี่คือคำศัพท์พื้นฐาน แนวคิดอื่นๆ จะมีการหารือเพิ่มเติม ดังนั้น binary tree คือต้นไม้ที่แต่ละโหนดจะมีลูกไม่เกินสองคน ดังที่คุณเดาไว้ ต้นไม้จากตัวอย่างจะไม่ใช่ไบนารี่ เนื่องจากโหนด B และ H มีลูกมากกว่าสองคน นี่คือตัวอย่างของต้นไม้ไบนารี:

โหนดต้นไม้สามารถมีข้อมูลใดๆ ได้ ต้นไม้ค้นหาแบบไบนารีเป็นต้นไม้ไบนารีที่มีคุณสมบัติดังต่อไปนี้:

แผนผังย่อยทั้งซ้ายและขวาเป็นแผนผังการค้นหาแบบไบนารี
โหนดทั้งหมดของทรีย่อยด้านซ้ายของโหนด X โดยพลการมีค่าคีย์ข้อมูลน้อยกว่าค่าของคีย์ข้อมูลของโหนด X เอง
โหนดทั้งหมดในแผนผังย่อยด้านขวาของโหนด 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;
    }
//...остальные методы узла
}

แต่ละโหนดมีลูกสองคน (ค่อนข้างเป็นไปได้ที่ลูก leftChild และ/หรือ rightChild จะมีค่าว่าง) คุณอาจตระหนักว่าในกรณีนี้ข้อมูลตัวเลขคือข้อมูลที่เก็บไว้ในโหนด คีย์ - คีย์โหนด

ไขข้อข้องใจแล้ว ต่อไปมาพูดถึงปัญหาเร่งด่วนเกี่ยวกับต้นไม้กันดีกว่า ต่อไปนี้ คำว่า "ต้นไม้" ผมจะหมายถึงแนวคิดของแผนผังการค้นหาแบบไบนารี โครงสร้างต้นไม้ไบนารี:

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 รายการในแผนผังที่สมดุล นั่นหมายความว่าจะมีบันทึก(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;
                    }
                }
            }
        }
    }

ในกรณีนี้ นอกเหนือจากโหนดปัจจุบัน จำเป็นต้องจัดเก็บข้อมูลเกี่ยวกับพาเรนต์ของโหนดปัจจุบันด้วย เมื่อกระแสกลายเป็นโมฆะ ตัวแปรพาเรนต์จะมีชีตที่เราต้องการ
เห็นได้ชัดว่าประสิทธิภาพของการแทรกจะเหมือนกับการค้นหา - O(log(n))

การถอด

การกำจัดเป็นการดำเนินการที่ยากที่สุดที่จะต้องดำเนินการบนต้นไม้ เป็นที่ชัดเจนว่าก่อนอื่นเราจะต้องค้นหาองค์ประกอบที่เราจะลบ แต่แล้วไงล่ะ? หากเราตั้งค่าการอ้างอิงเป็นโมฆะ เราจะสูญเสียข้อมูลเกี่ยวกับแผนผังย่อยที่โหนดนี้เป็นรูท วิธีการกำจัดต้นไม้แบ่งออกเป็น XNUMX กรณี

กรณีแรก. โหนดที่กำลังลบไม่มีลูก

หากโหนดที่ถูกลบไม่มีลูก แสดงว่าโหนดนั้นอยู่ในสถานะลีฟ ดังนั้น คุณก็สามารถตั้งค่าฟิลด์ leftChild หรือ rightChild ของพาเรนต์เป็นโมฆะได้

กรณีที่สอง โหนดที่จะลบมีลูกหนึ่งคน

กรณีนี้ก็ไม่ได้ซับซ้อนมากนัก กลับไปที่ตัวอย่างของเรา สมมติว่าเราจำเป็นต้องลบองค์ประกอบที่มีคีย์ 14 ยอมรับว่าเนื่องจากมันเป็นลูกหลานที่ถูกต้องของโหนดที่มีคีย์ 10 ดังนั้นลูกหลานใดๆ ของมัน (ในกรณีนี้คือองค์ประกอบที่ถูกต้อง) จะมีคีย์ที่มากกว่า 10 ดังนั้นคุณ สามารถ "ตัด" มันออกจากแผนผังได้อย่างง่ายดาย และเชื่อมต่อพาเรนต์โดยตรงกับลูกของโหนดที่กำลังถูกลบ เช่น เชื่อมต่อโหนดด้วยคีย์ 10 กับโหนด 13 สถานการณ์จะคล้ายกันหากจำเป็นต้องลบโหนดที่เป็นลูกด้านซ้ายของพาเรนต์ ลองคิดดูเอง - การเปรียบเทียบที่แน่นอน

กรณีที่สาม. โหนดมีลูกสองคน

กรณีที่ยากที่สุด ลองดูตัวอย่างใหม่

ค้นหาผู้สืบทอด

สมมติว่าเราจำเป็นต้องลบโหนดด้วยคีย์ 25 เราควรใส่ใครแทน? ผู้ติดตามคนหนึ่งของเขา (ลูกหลานหรือลูกหลานของลูกหลาน) จะต้องเป็น ผู้สืบทอด(ผู้ที่จะเข้ามาแทนที่โหนดที่ถูกถอดออก)

จะเข้าใจได้อย่างไรว่าใครควรเป็นผู้สืบทอด? โดยสังหรณ์ใจ นี่คือโหนดในแผนผังซึ่งมีคีย์ใหญ่เป็นอันดับถัดไปจากโหนดที่กำลังถูกลบ อัลกอริธึมมีดังนี้ คุณต้องไปที่ทายาทที่ถูกต้อง (ไปทางขวาเสมอเนื่องจากมีการกล่าวไปแล้วว่าคีย์ตัวตายตัวแทนนั้นมีค่ามากกว่าคีย์ของโหนดที่ถูกลบ) จากนั้นผ่านสายโซ่ของทายาทด้านซ้ายของทายาทด้านขวานี้ . ในตัวอย่างนี้ เราจะไปที่โหนดที่มีคีย์ 35 จากนั้นลงไปที่ leaf ผ่านสายโซ่ของลูกด้านซ้าย - ในกรณีนี้ สายโซ่นี้ประกอบด้วยเฉพาะโหนดที่มีคีย์ 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))

บายพาสแบบสมมาตร

Traversal กำลังเยี่ยมชมแต่ละโหนดของแผนผังเพื่อดำเนินการบางอย่างกับมัน

อัลกอริธึมการเคลื่อนที่แบบสมมาตรแบบเรียกซ้ำ:

ดำเนินการกับลูกด้านซ้าย
ดำเนินการกับตัวเอง
ดำเนินการกับเด็กที่ถูกต้อง

รหัส:

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

ข้อสรุป

ในที่สุด! หากฉันไม่ได้อธิบายอะไรหรือมีความคิดเห็นใด ๆ โปรดทิ้งไว้ในความคิดเห็น ตามที่สัญญาไว้ ฉันให้รหัสที่สมบูรณ์แล้ว

โหนด.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) นี่เป็นหนึ่งในข้อเสียที่สำคัญที่สุดในความคิดของฉันของต้นไม้ไบนารี

เฉพาะผู้ใช้ที่ลงทะเบียนเท่านั้นที่สามารถเข้าร่วมในการสำรวจได้ เข้าสู่ระบบ, โปรด.

ฉันไม่ได้เข้า Hub มานานมากแล้ว และอยากทราบว่ามีบทความอะไรบ้างในหัวข้อใดบ้างที่คุณอยากดูเพิ่มเติม

โครงสร้างข้อมูล
อัลกอริทึม (DP, การเรียกซ้ำ, การบีบอัดข้อมูล ฯลฯ)
การประยุกต์โครงสร้างข้อมูลและอัลกอริธึมในชีวิตจริง
การเขียนโปรแกรมแอพพลิเคชั่น Android ใน Java
การเขียนโปรแกรมเว็บแอปพลิเคชันใน Java

ผู้ใช้ 2 คนโหวต ผู้ใช้ 1 รายงดออกเสียง

ที่มา: www.habr.com

Binary Tree หรือวิธีการเตรียม Binary Search Tree