🥇二叉樹或如何準備二叉搜索樹

序幕

本文介紹的是二叉搜索樹。我最近寫了一篇關於採用霍夫曼方法進行數據壓縮。在那裡我並沒有真正關註二叉樹，因為搜索、插入、刪除的方法不相關。現在我決定寫一篇關於樹的文章。也許我們會開始。

樹是一種由通過邊連接的節點組成的數據結構。我們可以說樹是圖的特例。這是一個示例樹：

這不是二叉搜索樹！一切都在削減之中！

術語

根

樹根是最頂層的節點。在示例中，這是節點 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 子節點很可能為空）。您可能明白，在這種情況下，數字數據是存儲在節點中的數據； key - 節點鍵。

我們解決了這個結，現在我們來談談樹木的緊迫問題。在下文中，詞語“樹”將表示二叉搜索樹的概念。二叉樹結構：

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

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

作為類字段，我們只需要樹的根，因為從根開始，使用 getLeftChild() 和 getRightChild() 方法，您可以獲取樹的任何節點。

樹算法

搜索

假設您有一棵已建成的樹。如何用key鍵查找元素？需要依次從根部向下移動樹，並將 key 的值與下一個節點的 key 進行比較：如果 key 小於下一個節點的 key，則轉到該節點的左後代，如果大於 -向右，如果鍵相等- 找到所需的節點！相關代碼：

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

如果 current 變為 null，則迭代已到達樹的末尾（在概念層面上，您處於樹中不存在的位置 - 葉子的子級）。

考慮平衡樹（節點或多或少均勻分佈的樹）上的搜索算法的效率。那麼搜索效率將是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;
                    }
                }
            }
        }
    }

這種情況下，除了當前節點之外，還需要存儲當前節點的父節點的信息。當 current 變為 null 時，父變量將包含我們需要的工作表。
插入效率顯然與搜索相同 - O(log(n))。

切除

刪除是需要對樹執行的最複雜的操作。顯然，首先需要找到我們要刪除的元素。但然後呢？如果我們簡單地將其引用設置為 null，那麼我們將丟失有關以該節點為根的子樹的信息。樹木去除方法分為三種情況。

第一個案例。要刪除的節點沒有子節點。

如果要刪除的節點沒有子節點，則意味著它是葉子。因此，您只需將其父級的 leftChild 或 rightChild 字段設置為 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))

對稱旁路

遍歷是訪問樹的每個節點以便對其執行某些操作。

遞歸對稱遍曆算法：

對左邊的孩子做一個動作
與自己一起行動
對正確的孩子採取行動

代碼：

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

二叉樹.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)。在我看來，這是二叉樹最重要的缺點之一。

只有註冊用戶才能參與調查。登入，請。

我已經很久沒有上哈布雷了，我想知道您還想看更多關於哪些主題的文章？

數據結構
算法（DP、遞歸、數據壓縮等）
數據結構和算法在現實生活中的應用
使用 Java 編寫 Android 應用程序
Java Web 應用程序編程

2 位用戶投票。 1 位用戶棄權。

資料來源：www.habr.com

二叉樹或如何準備二叉搜索樹

序幕

術語

根

父母/子女

片

樹視圖

樹算法

搜索

插入

切除

第一個案例。 要刪除的節點沒有子節點。

第二個案例。 要移除的節點有一個子節點

第三種情況。 節點有兩個孩子