🥇עץ בינארי או איך להכין עץ חיפוש בינארי

פרלוד

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

עץ הוא מבנה נתונים המורכב מצמתים המחוברים בקצוות. אנו יכולים לומר שעץ הוא מקרה מיוחד של גרף. הנה עץ לדוגמה:

זה לא עץ חיפוש בינארי! הכל תחת חתך!

טרמינולוגיה

שורש

שורש עץ הוא הצומת העליון. בדוגמה, זהו צומת A. בעץ, רק נתיב אחד יכול להוביל מהשורש לכל צומת אחר! למעשה, כל צומת יכול להיחשב כשורש תת-העץ המתאים לצומת זה.

הורים/צאצאים

לכל הצמתים מלבד השורש יש קצה אחד בדיוק המוביל לצומת אחר. הצומת שמעל הצומת הנוכחי נקרא הוֹרֶה הצומת הזה. צומת שנמצא מתחת לזה הנוכחי ומחובר אליו נקרא צאֱצא הצומת הזה. בואו ניקח דוגמה. קח את צומת B, ואז האב שלו יהיה צומת A, והילדים שלו יהיו צמתים D, E ו-F.

גיליון

צומת שאין לו ילדים נקרא עלה של העץ. בדוגמה, הצמתים D, E, F, G, I, J, K יהיו עלים.

זהו המינוח הבסיסי. מושגים אחרים יידונו בהמשך. אז, עץ בינארי הוא עץ שבו לכל צומת יהיו לא יותר משני ילדים. כפי שניחשתם, העץ מהדוגמה לא יהיה בינארי, כי לצמתים 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 יהיו 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, אז נאבד מידע על תת-העץ שהשורש שלו הוא הצומת הזה. שיטות הסרת עצים מחולקות לשלושה מקרים.

מקרה ראשון. לצומת שיש להסיר אין ילדים.

אם לצומת שיימחק אין ילדים, זה אומר שזהו עלה. לכן, אתה יכול פשוט להגדיר את השדות leftChild או rightChild של האב שלו ל-null.

מקרה שני. לצומת שיש להסיר יש ילד אחד

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

מקרה שלישי. ל-Node יש שני ילדים

המקרה הכי קשה. בואו נסתכל על דוגמה חדשה.

חפש יורש

נניח שצריך להסיר את הצומת עם מפתח 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))

מעקף סימטרי

חציה היא ביקור בכל צומת של העץ כדי לעשות איתו משהו.

אלגוריתם מעבר סימטרי רקורסיבי:

בצע פעולה על הילד השמאלי
עשה פעולה עם עצמך
בצע פעולה על הילד הנכון

קוד:

    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());
        }
    }
}

נ.ב.

ניוון ל-O(n)

רבים מכם אולי שמו לב: מה אם תגרמו לעץ להיות לא מאוזן? לדוגמה, שים צמתים בעץ עם מפתחות הולכים וגדלים: 1,2,3,4,5,6... ואז העץ יזכיר קצת רשימה מקושרת. וכן, העץ יאבד את מבנה העץ שלו, ומכאן את יעילות הגישה לנתונים. המורכבות של פעולות חיפוש, הכנסה ומחיקה תהפוך להיות זהה לזו של רשימה מקושרת: O(n). זהו אחד החסרונות החשובים ביותר, לדעתי, של עצים בינאריים.

רק משתמשים רשומים יכולים להשתתף בסקר. להתחברבבקשה.

לא הייתי ב-Habré די הרבה זמן, והייתי רוצה לדעת אילו מאמרים באילו נושאים היית רוצה לראות יותר?

מבני מידע
אלגוריתמים (DP, רקורסיה, דחיסת נתונים וכו')
יישום מבני נתונים ואלגוריתמים בחיים האמיתיים
תכנות אפליקציות אנדרואיד ב-Java
תכנות יישומי אינטרנט Java

2 משתמשים הצביעו. 1 משתמשים נמנעו.

מקור: www.habr.com

עץ בינארי או כיצד להכין עץ חיפוש בינארי