🥇二叉树或如何准备二叉搜索树

序幕

本文介绍的是二叉搜索树。我最近写了一篇关于采用霍夫曼方法进行数据压缩。在那里我并没有真正关注二叉树，因为搜索、插入、删除的方法不相关。现在我决定写一篇关于树的文章。也许我们会开始。

树是一种由通过边连接的节点组成的数据结构。我们可以说树是图的特例。这是一个示例树：

这不是二叉搜索树！一切都在削减之中！

术语

根

树根是最顶层的节点。在示例中，这是节点 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());
        }
    }
}

PS

退化到 O(n)

你们中的许多人可能已经注意到：如果让树变得不平衡怎么办？例如，将节点放入树中，键值递增：1,2,3,4,5,6...，那么树会有点让人想起链表。是的，树将失去其树结构，从而失去数据访问的效率。搜索、插入和删除操作的复杂度将变得与链表相同：O(n)。在我看来，这是二叉树最重要的缺点之一。

只有注册用户才能参与调查。登录拜托

我已经很久没有上哈布雷了，我想知道您还想看更多关于哪些主题的文章？

数据结构
算法（DP、递归、数据压缩等）
数据结构和算法在现实生活中的应用
使用 Java 编写 Android 应用程序
Java Web 应用程序编程

2 位用户投票。 1 位用户弃权。

资料来源：www.habr.com

二叉树或如何准备二叉搜索树

序幕

术语

根

父母/子女

片

树视图

树算法

搜索

插入

切除

第一个案例。 要删除的节点没有子节点。

第二个案例。 要移除的节点有一个子节点

第三种情况。 节点有两个孩子