1. 首页
  2. 博客
  3. java常见算法 树形查找算法

java常见算法 树形查找算法

树形查找算法是一种基于树形结构的查找算法，通常用于在大量数据中快速查找特定元素。在树形结构中，数据按照某种特定的规则进行排序，并以树形结构的形式组织起来。在查找时，可以利用树形结构的特点，通过比较目标元素与树结点的值大小关系，逐层向下查找，从而快速定位目标元素所在的位置。

在 Java 中，常见的树形查找算法包括二叉查找树、平衡二叉树、红黑树、B树、B+树等等。其中，二叉查找树是最简单、最基础的树形查找算法之一，它的实现相对简单，容易理解。下面，我们来介绍一下如何在 Java 中实现二叉查找树算法。

二叉查找树的特点是，左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根结点的值。因此，在查找时，可以按照以下步骤进行：

  1. 比较目标元素与根结点的值大小关系。
  2. 如果目标元素小于根结点的值，则继续在左子树中查找。
  3. 如果目标元素大于根结点的值，则继续在右子树中查找。
  4. 如果目标元素等于根结点的值，则返回该结点。

下面是一个简单的 Java 代码示例，实现了二叉查找树算法：

public class BinarySearchTree {
    private TreeNode root;

    public TreeNode search(int key) {
        TreeNode current = root;
        while (current != null) {
            if (key == current.val) {
                return current;
            } else if (key < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }

    public void insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
        } else {
            TreeNode current = root;
            TreeNode parent;
            while (true) {
                parent = current;
                if (val < current.val) {
                    current = current.left;
                    if (current == null) {
                        parent.left = node;
                        return;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = node;
                        return;
                    }
                }
            }
        }
    }

    public void delete(int key) {
        TreeNode current = root;
        TreeNode parent = root;
        boolean isLeftChild = true;
        while (current.val != key) {
            parent = current;
            if (key < current.val) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            if (current == null) {
                return;

}
    // 如果待删除结点是叶子结点，则直接删除
    if (current.left == null && current.right == null) {
        if (current == root) {
            root = null;
        } else if (isLeftChild) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    }
    // 如果待删除结点只有一个子结点，则将该子结点替换到待删除结点的位置上
    else if (current.right == null) {
        if (current == root) {
            root = current.left;
        } else if (isLeftChild) {
            parent.left = current.left;
        } else {
            parent.right = current.left;
        }
    } else if (current.left == null) {
        if (current == root) {
            root = current.right;
        } else if (isLeftChild) {
            parent.left = current.right;
        } else {
            parent.right = current.right;
        }
    }
    // 如果待删除结点有两个子结点，则将待删除结点的后继结点替换到待删除结点的位置上
    else {
        TreeNode successor = getSuccessor(current);
        if (current == root) {
            root = successor;
        } else if (isLeftChild) {
            parent.left = successor;
        } else {
            parent.right = successor;
        }
        successor.left = current.left;
    }
}

private TreeNode getSuccessor(TreeNode node) {
    TreeNode successorParent = node;
    TreeNode successor = node;
    TreeNode current = node.right;
    while (current != null) {
        successorParent = successor;
        successor = current;
        current = current.left;
    }
    if (successor != node.right) {
        successorParent.left = successor.right;
        successor.right = node.right;
    }
    return successor;
}

private static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
}

上面的代码中，BinarySearchTree 类包含了三个主要的方法：search()、insert() 和 delete()。其中，search() 方法用于查找特定的元素；insert() 方法用于向二叉查找树中插入新的元素；delete() 方法用于从二叉查找树中删除指定的元素。此外，BinarySearchTree 类中还定义了一个内部类 TreeNode，用于表示二叉查找树中的结点。

需要注意的是，上面的代码中只实现了简单的二叉查找树算法，并没有对树进行平衡操作。如果二叉查找树的数据分布不均匀，可能会导致树的高度过高，查找效率降低。为了解决这个问题，可以使用平衡二叉树、红黑树、B树、B+树等算法。这些算法在实现上比较复杂，但可以提高查找效率，适用于大规模数据的查找应用场景。

除了二叉查找树之外，还有其他一些常见的树形查找算法，下面简单介绍几种。

AVL 树

AVL 树是一种自平衡二叉查找树，它的每个结点都具有一个平衡因子，即左子树高度与右子树高度的差值。AVL 树中任意结点的平衡因子的绝对值不超过 1，如果超过 1 则需要进行相应的旋转操作来调整树的平衡。AVL 树的平均查找和插入时间复杂度都为 O(log n)，但是由于平衡操作的代价较大，所以 AVL 树的实现比较复杂。

红黑树

红黑树也是一种自平衡二叉查找树，它在 AVL 树的基础上进行了优化，使得其插入、删除等操作比 AVL 树更加高效。红黑树的特点是每个结点上都有一个颜色标记，通常为红色或黑色，同时满足以下规则：

  1. 根结点为黑色；
  2. 每个叶子结点都是黑色的空结点；
  3. 如果一个结点是红色的，则其子结点必须是黑色的；
  4. 从任意一个结点到其每个叶子结点的所有路径都包含相同数目的黑色结点。

根据上述规则，可以证明红黑树的最长路径不超过最短路径的两倍，因此红黑树的查找和插入等操作的时间复杂度为 O(log n)。

B 树

B 树是一种多路搜索树，通常用于在磁盘等外部存储器中组织和管理数据。B 树的每个结点可以包含多个关键字和指向子结点的指针，其特点是：

  1. 根结点至少包含两个子结点；
  2. 每个中间结点包含的关键字个数为 m-1，其中 m 为 B 树的阶数，每个结点至少包含 m/2 个关键字；
  3. 所有叶子结点都位于同一层；
  4. 所有结点的关键字按照升序排列。

B 树的查找和插入等操作的时间复杂度为 O(log n)。B 树比较适合于大规模数据的外部存储应用场景，如数据库索引、文件系统等。

B+ 树

B+ 树是在 B 树的基础上进行的改进，其叶子结点之间相互连接形成一个链表，可以加快范围查找等操作的效率。B+ 树的特点是：

  1. 所有叶子结点都包含了全部关键字的信息以及指向它们所对应数据记录的指针，而所有非叶子结点仅仅包含了关键字的信息；
  2. 所有叶子结点之间形成了一个双向链表；
  3. 所有非叶子结点包含的关键字个数为 m-1，其中 m 为 B+ 树的阶数，每个结点至少包含 m/2 个关键字；
  4. 所有结点的关键字按照升序排列。

B+ 树相对于 B 树的优势在于减少了非叶子结点的关键字数目，从而减少了非叶子结点的大小和访问的磁盘块数目，同时由于叶子结点之间相互连接形成链表，因此范围查找等操作的效率更高。

Trie 树

Trie 树，也称为字典树或前缀树，是一种树形数据结构，用于高效地存储和查找字符串集合。Trie 树的根结点不包含任何信息，每个非根结点都包含一个字符和指向子结点的指针，从根结点到叶子结点的路径表示一个字符串。Trie 树的优势在于支持高效的字符串匹配操作，时间复杂度为 O(m)，其中 m 为匹配的字符串长度。

除了上述几种树形查找算法之外，还有一些其他的树形数据结构，如哈希树、kd 树、区间树等，它们都在特定的场景下具有一定的优势，可以根据具体情况选择合适的算法。

原文链接：codingdict.net

热门标签