前两天V哥跟一个老学员吃饭，聊起面试大厂的事，说为啥大厂面试第一看基本条件，第二就是考数据结构算法，其他高阶的内容会比较少，最近V哥也在跟大厂对接这一块业务，了解得多一些，这是因为考察基本功能力被放到了重要位置，大厂认为硬性条件，比如学历过关，基本功够扎实，那对于实际工作用的上层技能，内部培养就好，也就是相比你掌握了多少多少牛逼的高阶技术，他们更在乎你的基本功，所以，进大厂，基本功必须要搞稳，否则白扯，今天 V 哥把总结好的22个常用的数据结构实现原理，和示例分析分享给大家，希望对你有帮助，觉得内容有收获，请帮忙转发给更多需求的朋友，共同进步。

1.数组（Array）

数组是一种线性数据结构，它由一系列元素组成，这些元素通过索引进行访问。数组可以是一维的（一维数组）也可以是多维的（多维数组），在内存中连续存储。

示例代码实现：

public class Main {
   
    public static void main(String[] args) {
   
        // 声明并初始化一个数组
        int[] array = {
   1, 2, 3, 4, 5};

        // 访问数组元素
        System.out.println("第三个元素是：" + array[2]);

        // 修改数组元素
        array[2] = 10;
        System.out.println("修改后的第三个元素是：" + array[2]);

        // 遍历数组元素
        System.out.println("数组元素为：");
        for (int i = 0; i < array.length; i++) {
   
            System.out.print(array[i] + " ");
        }
        System.out.println();

        // 数组长度
        System.out.println("数组长度为：" + array.length);
    }
}

实现原理解释：

数组由相同类型的元素组成，这些元素按照一定的顺序存储在内存中，每个元素都可以通过索引来访问，索引通常从0开始。
数组的访问时间复杂度为 O(1)，因为可以通过索引直接计算出要访问的元素在内存中的地址，从而实现快速访问。
数组的插入和删除操作可能比较耗时，因为需要移动数组中的元素。在数组的开头或中间插入或删除元素时，需要将插入点之后的所有元素向后或向前移动一位。
数组的大小通常是固定的，因此插入和删除元素时可能需要进行数组的扩容或缩容操作。

2.链表 (Linked List)

链表是由节点组成的线性数据结构，每个节点包含数据和指向下一个节点的引用。

示例代码实现：

class ListNode {
   
    int val;
    ListNode next;

    public ListNode(int val) {
   
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {
   
    private ListNode head;

    public LinkedList() {
   
        this.head = null;
    }

    // 在链表末尾添加一个节点
    public void add(int val) {
   
        if (head == null) {
   
            head = new ListNode(val);
        } else {
   
            ListNode current = head;
            while (current.next != null) {
   
                current = current.next;
            }
            current.next = new ListNode(val);
        }
    }
}

实现原理解释：

链表的实现基于节点的概念。每个节点都包含一个数据元素和一个指向下一个节点的引用。在示例中，我们创建了一个ListNode类来表示链表节点。然后，我们通过LinkedList类来管理链表，其中的add方法用于在链表末尾添加新节点。
当链表为空时，我们简单地将新节点设置为头节点。否则，我们从头节点开始遍历链表，直到找到最后一个节点，然后将新节点连接到最后一个节点的next引用上。

3.栈 (Stack)

栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。

示例代码实现：

import java.util.EmptyStackException;

public class Stack {
   
    private ListNode top;

    public Stack() {
   
        this.top = null;
    }

    // 入栈操作
    public void push(int val) {
   
        ListNode newNode = new ListNode(val);
        newNode.next = top;
        top = newNode;
    }

    // 出栈操作
    public int pop() {
   
        if (isEmpty()) {
   
            throw new EmptyStackException();
        }
        int val = top.val;
        top = top.next;
        return val;
    }

    // 获取栈顶元素
    public int peek() {
   
        if (isEmpty()) {
   
            throw new EmptyStackException();
        }
        return top.val;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
   
        return top == null;
    }
}

实现原理解释：

栈的实现通常基于链表或数组。在示例中，我们选择了链表作为底层数据结构来实现栈。
栈的入栈操作（push）将一个新元素添加到栈顶。这通过创建一个新节点，并将其指向原栈顶节点来完成。然后，我们将新节点设置为栈顶。
栈的出栈操作（pop）将栈顶元素移除并返回其值。我们将栈顶节点指向原栈顶节点的下一个节点，并返回原栈顶节点的值。
栈的peek操作用于获取栈顶元素的值，而isEmpty操作用于检查栈是否为空。

4.队列 (Queue)

队列是一种先进先出（FIFO）的数据结构，允许在队尾进行插入操作，在队首进行删除操作。

示例代码实现：

import java.util.LinkedList;

public class Queue {
   
    private LinkedList<Integer> list;

    public Queue() {
   
        this.list = new LinkedList<>();
    }

    // 入队操作
    public void enqueue(int val) {
   
        list.addLast(val);
    }

    // 出队操作
    public int dequeue() {
   
        if (isEmpty()) {
   
            throw new IllegalStateException("Queue is empty");
        }
        return list.removeFirst();
    }

    // 获取队首元素
    public int peek() {
   
        if (isEmpty()) {
   
            throw new IllegalStateException("Queue is empty");
        }
        return list.getFirst();
    }

    // 判断队列是否为空
    public boolean isEmpty() {
   
        return list.isEmpty();
    }
}

实现原理解释：

队列的实现通常基于链表或数组。在示例中，我们使用了Java标准库提供的LinkedList来实现队列。
队列的入队操作（enqueue）将一个新元素添加到队列的末尾。这通过将新元素添加到链表的末尾来完成。
队列的出队操作（dequeue）将队列首部的元素移除并返回其值。我们使用链表的removeFirst方法来实现。
队列的peek操作用于获取队首元素的值，而isEmpty操作用于检查队列是否为空。

通过理解这些数据结构的实现原理和示例代码，你可以更好地应用它们来解决实际问题，并且能够更深入地理解它们的工作原理。

5.双端队列（Deque）

双端队列（Deque），也称为双向队列，是一种特殊的队列，它允许在队列的两端进行插入和删除操作。双端队列可以从头部和尾部同时插入和删除元素，因此具有队列和栈的特性。

示例代码实现：

以下是使用双向链表实现双端队列的简单示例：

import java.util.LinkedList;

public class MyDeque {
   
    private LinkedList<Integer> deque;

    public MyDeque() {
   
        deque = new LinkedList<>();
    }

    // 从头部插入元素
    public void addFirst(int item) {
   
        deque.addFirst(item);
    }

    // 从尾部插入元素
    public void addLast(int item) {
   
        deque.addLast(item);
    }

    // 从头部删除元素
    public int removeFirst() {
   
        return deque.removeFirst();
    }

    // 从尾部删除元素
    public int removeLast() {
   
        return deque.removeLast();
    }

    // 获取头部元素
    public int getFirst() {
   
        return deque.getFirst();
    }

    // 获取尾部元素
    public int getLast() {
   
        return deque.getLast();
    }

    // 判断双端队列是否为空
    public boolean isEmpty() {
   
        return deque.isEmpty();
    }

    // 获取双端队列的大小
    public int size() {
   
        return deque.size();
    }
}

public class Main {
   
    public static void main(String[] args) {
   
        MyDeque deque = new MyDeque();
        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        System.out.println("双端队列的大小：" + deque.size());
        System.out.println("头部元素：" + deque.getFirst());
        System.out.println("尾部元素：" + deque.getLast());

        while (!deque.isEmpty()) {
   
            System.out.print(deque.removeFirst() + " ");
        }
    }
}

以上代码演示了如何使用双向链表实现双端队列，并对双端队列进行了一些基本操作，如插入、删除、获取元素等。双端队列是一种非常实用的数据结构，在很多场景下都可以发挥作用，例如在树的层序遍历、滑动窗口等算法中。

实现原理解释：

双端队列允许在队列的两端进行插入和删除操作，因此可以在头部和尾部同时执行入队和出队操作。
双端队列的底层实现可以使用链表或者数组。使用链表实现时，可以很方便地在头部和尾部执行插入和删除操作，但是查询操作的时间复杂度为 O(n)；使用数组实现时，插入和删除操作的时间复杂度为 O(1)，但是需要考虑扩容和缩容的问题。
双端队列可以用来实现很多其他数据结构，例如栈、队列、优先队列等。因为它同时具有队列和栈的特性，可以很方便地进行元素的入栈、出栈、入队、出队操作。

6.哈希表 (Hash Table)

哈希表是一种通过哈希函数将关键字映射到表中的位置来实现快速查找的数据结构。

示例代码实现：

import java.util.LinkedList;

public class HashTable {
   
    private static final int SIZE = 10; // 哈希表大小
    private LinkedList<Entry>[] table; // 使用链表数组实现哈希表

    public HashTable() {
   
        table = new LinkedList[SIZE];
        for (int i = 0; i < SIZE; i++) {
   
            table[i] = new LinkedList<>();
        }
    }

    // 哈希函数：将关键字映射到哈希表的索引位置
    private int hashFunction(int key) {
   
        return key % SIZE;
    }

    // 插入键值对到哈希表中
    public void put(int key, int value) {
   
        int index = hashFunction(key);
        LinkedList<Entry> list = table[index];
        for (Entry entry : list) {
   
            if (entry.key == key) {
   
                entry.value = value; // 如果关键字已经存在，则更新值
                return;
            }
        }
        list.add(new Entry(key, value)); // 否则添加新的键值对
    }

    // 获取键对应的值
    public int get(int key) {
   
        int index = hashFunction(key);
        LinkedList<Entry> list = table[index];
        for (Entry entry : list) {
   
            if (entry.key == key) {
   
                return entry.value; // 返回对应的值
            }
        }
        throw new IllegalArgumentException("Key not found"); // 如果键不存在则抛出异常
    }

    // 删除指定键的键值对
    public void remove(int key) {
   
        int index = hashFunction(key);
        LinkedList<Entry> list = table[index];
        for (Entry entry : list) {
   
            if (entry.key == key) {
   
                list.remove(entry); // 删除对应的键值对
                return;
            }
        }
        throw new IllegalArgumentException("Key not found"); // 如果键不存在则抛出异常
    }

    // 内部类表示哈希表中的键值对
    private static class Entry {
   
        int key;
        int value;

        public Entry(int key, int value) {
   
            this.key = key;
            this.value = value;
        }
    }
}

实现原理解释：

哈希表通过哈希函数将关键字映射到表中的位置，这个位置通常称为哈希桶。在示例中，我们使用简单的取模运算作为哈希函数。
为了处理哈希冲突，即多个不同的关键字映射到同一个哈希桶的情况，我们使用链表来存储具有相同哈希值的键值对。
插入键值对时，首先计算关键字的哈希值并找到对应的哈希桶，然后遍历该哈希桶内的链表，如果发现已存在相同的关键字，则更新对应的值；否则，在链表末尾添加新的键值对。
获取键值对时，同样计算出哈希桶的索引，并在对应的链表中查找对应的键值对，如果找到则返回其值，否则抛出异常表示键不存在。
删除键值对时，同样需要先找到对应的哈希桶和链表，然后遍历链表，找到对应的键值对并将其删除。

哈希表是一种高效的数据结构，能够在平均情况下实现快速的插入、查找和删除操作，但在最坏情况下可能会有较高的时间复杂度。

7.树 (Tree)

树是一种层级结构，由节点组成，每个节点可以有零个或多个子节点。

示例代码实现：

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

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

public class BinaryTree {
   
    private TreeNode root;

    public BinaryTree() {
   
        this.root = null;
    }

    // 插入节点
    public void insert(int val) {
   
        root = insertRecursive(root, val);
    }

    // 递归插入节点
    private TreeNode insertRecursive(TreeNode root, int val) {
   
        if (root == null) {
   
            return new TreeNode(val);
        }

        if (val < root.val) {
   
            root.left = insertRecursive(root.left, val);
        } else if (val > root.val) {
   
            root.right = insertRecursive(root.right, val);
        }

        return root;
    }
}

实现原理解释：

树的节点由一个数据元素和指向子节点的引用组成。在示例中，我们使用TreeNode类来表示树的节点。
树的根节点是树的入口点，可以通过它遍历整棵树。在示例中，我们通过BinaryTree类来管理树，其中的insert方法用于插入新节点。
插入节点时，首先比较要插入的节点值和当前节点的值，如果小于当前节点的值，则插入到左子树中；如果大于当前节点的值，则插入到右子树中。递归地在子树中执行相同的操作，直到找到合适的插入位置。

树是一种重要的数据结构，有着丰富的应用场景，包括二叉搜索树、平衡二叉树、红黑树等。对树的深入理解能够帮助我们更好地解决各种问题。

8.平衡二叉树 (Balanced Binary Tree)

平衡二叉树是一种二叉树，它的每个节点的左右子树的高度差不超过1。

示例代码实现：

class AVLNode {
   
    int val;
    int height;
    AVLNode left;
    AVLNode right;

    public AVLNode(int val) {
   
        this.val = val;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
}

public class AVLTree {
   
    private AVLNode root;

    public AVLTree() {
   
        this.root = null;
    }

    // 获取节点的高度
    private int height(AVLNode node) {
   
        if (node == null) {
   
            return 0;
        }
        return node.height;
    }

    // 获取节点的平衡因子
    private int balanceFactor(AVLNode node) {
   
        if (node == null) {
   
            return 0;
        }
        return height(node.left) - height(node.right);
    }

    // 右旋转
    private AVLNode rightRotate(AVLNode y) {
   
        AVLNode x = y.left;
        AVLNode T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

    // 左旋转
    private AVLNode leftRotate(AVLNode x) {
   
        AVLNode y = x.right;
        AVLNode T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

    // 插入节点
    public void insert(int val) {
   
        root = insertRecursive(root, val);
    }

    // 递归插入节点
    private AVLNode insertRecursive(AVLNode root, int val) {
   
        if (root == null) {
   
            return new AVLNode(val);
        }

        if (val < root.val) {
   
            root.left = insertRecursive(root.left, val);
        } else if (val > root.val) {
   
            root.right = insertRecursive(root.right, val);
        } else {
   
            return root; // 重复值不允许插入
        }

        root.height = 1 + Math.max(height(root.left), height(root.right));

        int balance = balanceFactor(root);

        // 左左情况
        if (balance > 1 && val < root.left.val) {
   
            return rightRotate(root);
        }

        // 右右情况
        if (balance < -1 && val > root.right.val) {
   
            return leftRotate(root);
        }

        // 左右情况
        if (balance > 1 && val > root.left.val) {
   
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        // 右左情况
        if (balance < -1 && val < root.right.val) {
   
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }
}

实现原理解释：

平衡二叉树是一种自平衡的二叉搜索树，保持了每个节点的左右子树的高度差不超过1的特性。
在插入新节点时，我们首先按照二叉搜索树的规则找到合适的插入位置。然后，我们递归地更新从插入位置到根节点的路径上所有节点的高度，并检查它们的平衡因子是否满足平衡条件。
如果出现不平衡情况，我们通过旋转操作来恢复平衡。左旋转和右旋转是平衡二叉树中最基本的旋转操作，通过它们可以将不平衡的子树调整为平衡的状态。
在插入新节点后，我们递归地检查每个祖先节点的平衡因子，如果发现不平衡，则执行相应的旋转操作。

9.红黑树 (Red-Black Tree)

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色，并且满足以下性质：

每个节点要么是红色，要么是黑色。
根节点是黑色的。
每个叶子节点（NIL节点，空节点）是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的。
对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

红黑树通过这些性质保持了一种平衡，保证了插入、删除等操作的时间复杂度为O(log n)。

示例代码实现：

class RedBlackTreeNode {
   
    int val;
    boolean isRed;
    RedBlackTreeNode left;
    RedBlackTreeNode right;
    RedBlackTreeNode parent;

    public RedBlackTreeNode(int val) {
   
        this.val = val;
        this.isRed = true;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class RedBlackTree {
   
    private RedBlackTreeNode root;

    public RedBlackTree() {
   
        this.root = null;
    }

    // 插入节点
    public void insert(int val) {
   
        RedBlackTreeNode newNode = new RedBlackTreeNode(val);
        root = insertNode(root, newNode);
        fixViolations(newNode);
    }

    // 插入节点的辅助方法
    private RedBlackTreeNode insertNode(RedBlackTreeNode root, RedBlackTreeNode newNode) {
   
        if (root == null) {
   
            return newNode;
        }

        if (newNode.val < root.val) {
   
            root.left = insertNode(root.left, newNode);
            root.left.parent = root;
        } else if (newNode.val > root.val) {
   
            root.right = insertNode(root.right, newNode);
            root.right.parent = root;
        }

        return root;
    }

    // 修复违反红黑树性质的情况
    private void fixViolations(RedBlackTreeNode node) {
   
        while (node != null && node != root && node.parent.isRed) {
   
            if (node.parent == node.parent.parent.left) {
   
                RedBlackTreeNode uncle = node.parent.parent.right;
                if (uncle != null && uncle.isRed) {
   
                    node.parent.isRed = false;
                    uncle.isRed = false;
                    node.parent.parent.isRed = true;
                    node = node.parent.parent;
                } else {
   
                    if (node == node.parent.right) {
   
                        node = node.parent;
                        leftRotate(node);
                    }
                    node.parent.isRed = false;
                    node.parent.parent.isRed = true;
                    rightRotate(node.parent.parent);
                }
            } else {
   
                RedBlackTreeNode uncle = node.parent.parent.left;
                if (uncle != null && uncle.isRed) {
   
                    node.parent.isRed = false;
                    uncle.isRed = false;
                    node.parent.parent.isRed = true;
                    node = node.parent.parent;
                } else {
   
                    if (node == node.parent.left) {
   
                        node = node.parent;
                        rightRotate(node);
                    }
                    node.parent.isRed = false;
                    node.parent.parent.isRed = true;
                    leftRotate(node.parent.parent);
                }
            }
        }
        root.isRed = false;
    }

    // 左旋转操作
    private void leftRotate(RedBlackTreeNode node) {
   
        RedBlackTreeNode rightChild = node.right;
        node.right = rightChild.left;
        if (rightChild.left != null) {
   
            rightChild.left.parent = node;
        }
        rightChild.parent = node.parent;
        if (node.parent == null) {
   
            root = rightChild;
        } else if (node == node.parent.left) {
   
            node.parent.left = rightChild;
        } else {
   
            node.parent.right = rightChild;
        }
        rightChild.left = node;
        node.parent = rightChild;
    }

    // 右旋转操作
    private void rightRotate(RedBlackTreeNode node) {
   
        RedBlackTreeNode leftChild = node.left;
        node.left = leftChild.right;
        if (leftChild.right != null) {
   
            leftChild.right.parent = node;
        }
        leftChild.parent = node.parent;
        if (node.parent == null) {
   
            root = leftChild;
        } else if (node == node.parent.right) {
   
            node.parent.right = leftChild;
        } else {
   
            node.parent.left = leftChild;
        }
        leftChild.right = node;
        node.parent = leftChild;
    }
}

实现原理解释：

红黑树通过左旋转和右旋转等操作来保持树的平衡。左旋转将一个节点上升到其右子节点的位置，而右旋转将一个节点上升到其左子节点的位置。
当插入一个新节点后，可能会破坏红黑树的性质，例如父节点和叔节点都为红色，此时需要通过颜色调整和旋转来恢复平衡。
插入新节点后，我们沿着插入路径向上检查，如果当前节点的父节点和叔节点都为红色，则需要进行颜色调整；否则，如果当前节点的父节点为红色而叔节点为黑色，则需要进行旋转操作。
通过适当的旋转和颜色调整，我们可以保持红黑树的平衡性质，从而确保其高效的插入、删除和搜索操作的时间复杂度为O(log n)。

10.堆 (Heap)

堆是一种特殊的树形数据结构，其中每个节点的值都必须大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。

示例代码实现：

以下是最小堆的示例代码实现：

public class MinHeap {
   
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
   
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    // 获取父节点索引
    private int parent(int i) {
   
        return (i - 1) / 2;
    }

    // 获取左子节点索引
    private int leftChild(int i) {
   
        return 2 * i + 1;
    }

    // 获取右子节点索引
    private int rightChild(int i) {
   
        return 2 * i + 2;
    }

    // 插入元素
    public void insert(int value) {
   
        if (size == capacity) {
   
            throw new IllegalStateException("Heap is full");
        }
        size++;
        int i = size - 1;
        heap[i] = value;
        // 保持堆的性质
        while (i != 0 && heap[parent(i)] > heap[i]) {
   
            swap(i, parent(i));
            i = parent(i);
        }
    }

    // 交换堆中两个元素
    private void swap(int i, int j) {
   
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 从堆中删除最小元素
    public int extractMin() {
   
        if (size <= 0) {
   
            throw new IllegalStateException("Heap is empty");
        }
        if (size == 1) {
   
            size--;
            return heap[0];
        }
        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;
        minHeapify(0);
        return root;
    }

    // 保持最小堆性质
    private void minHeapify(int i) {
   
        int left = leftChild(i);
        int right = rightChild(i);
        int smallest = i;
        if (left < size && heap[left] < heap[i]) {
   
            smallest = left;
        }
        if (right < size && heap[right] < heap[smallest]) {
   
            smallest = right;
        }
        if (smallest != i) {
   
            swap(i, smallest);
            minHeapify(smallest);
        }
    }

    // 获取堆中最小元素
    public int getMin() {
   
        if (size == 0) {
   
            throw new IllegalStateException("Heap is empty");
        }
        return heap[0];
    }
}

实现原理解释：

堆通常用数组来实现，数组的每个元素对应堆的一个节点。
在最小堆中，父节点的值始终小于或等于其子节点的值。
插入操作保持堆的性质：将新元素插入到堆的末尾，然后通过上移操作（向上比较交换）来确保新元素满足堆的性质。
删除最小元素操作（通常是堆顶元素）：将堆顶元素移动到末尾，然后通过下移操作（向下比较交换）来确保堆的性质。
获取最小元素操作：返回堆顶元素即可。
在最大堆中，父节点的值始终大于或等于其子节点的值，操作类似于最小堆，只是比较的方式相反。

堆是一种非常重要的数据结构，常用于实现优先队列等应用场景，能够快速地获取最大或最小元素。

11.图 (Graph)

图是由节点（顶点）和连接这些节点的边组成的一种数据结构。图可以用于表示各种实际问题中的关系和网络。

示例代码实现：

以下是使用邻接表实现的无向图的示例代码：

import java.util.*;

public class Graph {
   
    private int V; // 图中顶点的数量
    private LinkedList<Integer>[] adj; // 邻接表表示图的结构

    public Graph(int V) {
   
        this.V = V;
        adj = new LinkedList[V];
        for (int i = 0; i < V; ++i)
            adj[i] = new LinkedList<>();
    }

    // 添加边，无向图的边是双向的
    public void addEdge(int v, int w) {
   
        adj[v].add(w);
        adj[w].add(v);
    }

    // 深度优先搜索遍历图
    public void DFS(int v) {
   
        boolean[] visited = new boolean[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, boolean[] visited) {
   
        visited[v] = true;
        System.out.print(v + " ");

        for (int n : adj[v]) {
   
            if (!visited[n]) {
   
                DFSUtil(n, visited);
            }
        }
    }

    // 广度优先搜索遍历图
    public void BFS(int v) {
   
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        visited[v] = true;
        queue.add(v);

        while (!queue.isEmpty()) {
   
            int current = queue.poll();
            System.out.print(current + " ");

            for (int n : adj[current]) {
   
                if (!visited[n]) {
   
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

实现原理解释：

图的表示方式有多种，其中一种常见的方式是邻接表。在示例代码中，我们使用了邻接表来表示无向图的结构。
在邻接表中，对于每个顶点，我们都维护一个与之相邻的顶点列表。在示例中，我们使用LinkedList数组来表示每个顶点的邻接列表。
添加边的操作是双向的，因为无向图中的边是双向的，所以在添加边时，需要同时更新两个顶点的邻接列表。
深度优先搜索（DFS）和广度优先搜索（BFS）是图的常见遍历算法。DFS通过递归或栈来实现，它会沿着图的深度尽可能远地搜索。而BFS通过队列来实现，它会逐层遍历图。在示例代码中，我们实现了DFS和BFS的遍历算法。

图是一种十分灵活的数据结构，能够很好地表示各种实际问题中的关系和网络。深入理解图的遍历算法和性质对于解决各种问题至关重要。

12.字典树 (Trie)

字典树，也称为前缀树或单词查找树，是一种用于存储关联数组的树形数据结构。它是一种哈希树的变种，通常用于高效地检索大量的字符串数据集中的键值。

示例代码实现：

以下是字典树的示例代码实现：

class TrieNode {
   
    TrieNode[] children;
    boolean isEnd;

    public TrieNode() {
   
        children = new TrieNode[26]; // 假设只包含小写字母
        isEnd = false;
    }
}

public class Trie {
   
    private TrieNode root;

    public Trie() {
   
        root = new TrieNode();
    }

    // 向字典树中插入单词
    public void insert(String word) {
   
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
   
            int index = ch - 'a';
            if (node.children[index] == null) {
   
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true; // 标记单词结束
    }

    // 在字典树中搜索单词
    public boolean search(String word) {
   
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
   
            int index = ch - 'a';
            if (node.children[index] == null) {
   
                return false;
            }
            node = node.children[index];
        }
        return node != null && node.isEnd; // 检查单词是否结束
    }

    // 判断是否存在以指定前缀开头的单词
    public boolean startsWith(String prefix) {
   
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
   
            int index = ch - 'a';
            if (node.children[index] == null) {
   
                return false;
            }
            node = node.children[index];
        }
        return node != null; // 只需判断是否存在前缀，不需要检查是否为完整单词
    }
}

实现原理解释：

字典树的节点由一个存储当前字符的数组和一个标记是否是单词结束的布尔变量组成。在示例中，我们使用TrieNode类来表示字典树的节点。
插入操作：将单词中的每个字符按顺序插入到字典树中。对于每个字符，如果该字符对应的子节点不存在，则创建新的子节点；否则，移动到下一个子节点。在单词的最后一个字符处，将isEnd标记为true，表示这是一个完整的单词。
搜索操作：从根节点开始，按照单词中的字符顺序遍历字典树。如果在遍历过程中遇到了空子节点，则说明字典树中不包含该单词。如果遍历完所有字符后，当前节点的isEnd标记为true，则说明该单词存在于字典树中。
前缀搜索操作：与搜索操作类似，只是在搜索过程中不需要检查isEnd标记，因为只需要判断是否存在以指定前缀开头的单词，不需要完整的单词。

字典树是一种高效的数据结构，常用于搜索引擎、拼写检查、自动完成等应用场景中。

13.哈希集合 (HashSet)

哈希集合是一种集合数据结构，它基于哈希表实现，能够提供快速的插入、删除和查找操作。

示例代码实现：

以下是使用哈希表实现的简单哈希集合的示例代码：

import java.util.*;

public class MyHashSet {
   
    private static final int BASE = 769;
    private List<Integer>[] buckets;

    public MyHashSet() {
   
        buckets = new LinkedList[BASE];
        for (int i = 0; i < BASE; i++) {
   
            buckets[i] = new LinkedList<>();
        }
    }

    // 哈希函数
    private int hash(int key) {
   
        return key % BASE;
    }

    // 向集合中插入元素
    public void add(int key) {
   
        int hashKey = hash(key);
        if (!contains(key)) {
   
            buckets[hashKey].add(key);
        }
    }

    // 从集合中删除元素
    public void remove(int key) {
   
        int hashKey = hash(key);
        buckets[hashKey].remove(Integer.valueOf(key));
    }

    // 检查集合中是否包含元素
    public boolean contains(int key) {
   
        int hashKey = hash(key);
        return buckets[hashKey].contains(key);
    }
}

实现原理解释：

哈希集合基于哈希表实现，其中哈希函数将键映射到哈希表中的索引位置。
在示例中，我们使用一个数组来表示哈希表，每个数组元素是一个链表，用于解决哈希冲突。
插入操作：首先计算键的哈希值，然后将键添加到对应索引处的链表中。在添加之前，通常需要检查该键是否已经存在于集合中。
删除操作：同样需要计算键的哈希值，然后在对应索引处的链表中查找并删除该键。
查找操作：通过计算键的哈希值找到对应索引处的链表，然后在链表中查找该键是否存在。

哈希集合是一种高效的数据结构，能够在平均情况下提供快速的插入、删除和查找操作。

14.队列 (Queue)

队列是一种先进先出（FIFO）的数据结构，类似于排队。在队列中，新元素在队尾添加，而从队列中移除元素则发生在队列头部。

示例代码实现：

以下是使用链表实现的队列的示例代码：

import java.util.*;

public class QueueExample {
   
    private LinkedList<Integer> queue;

    public QueueExample() {
   
        queue = new LinkedList<>();
    }

    // 入队操作
    public void enqueue(int item) {
   
        queue.addLast(item);
    }

    // 出队操作
    public int dequeue() {
   
        if (isEmpty()) {
   
            throw new NoSuchElementException("Queue is empty");
        }
        return queue.removeFirst();
    }

    // 获取队头元素
    public int peek() {
   
        if (isEmpty()) {
   
            throw new NoSuchElementException("Queue is empty");
        }
        return queue.getFirst();
    }

    // 检查队列是否为空
    public boolean isEmpty() {
   
        return queue.isEmpty();
    }

    // 获取队列中元素个数
    public int size() {
   
        return queue.size();
    }
}

实现原理解释：

队列通常使用链表或数组来实现。在示例中，我们使用Java中的LinkedList来实现队列。
入队操作：将新元素添加到链表的末尾，因为队列是先进先出的，所以新元素会排在队列的尾部。
出队操作：从链表的头部移除元素，因为队列中的第一个元素最先进入，所以需要从队列的头部移除元素。
获取队头元素：返回链表的头部元素，但不移除它。
检查队列是否为空：判断链表是否为空。
获取队列中元素个数：返回链表的大小，即队列中元素的个数。

队列是一种常见的数据结构，在许多应用场景中都有广泛的应用，例如任务调度、消息队列、广度优先搜索等算法。

15.栈 (Stack)

栈是一种后进先出（LIFO）的数据结构，类似于一叠盘子。在栈中，新元素在顶部添加，而移除元素也发生在顶部。

示例代码实现：

以下是使用链表实现的栈的示例代码：

import java.util.*;

public class StackExample {
   
    private LinkedList<Integer> stack;

    public StackExample() {
   
        stack = new LinkedList<>();
    }

    // 入栈操作
    public void push(int item) {
   
        stack.addLast(item);
    }

    // 出栈操作
    public int pop() {
   
        if (isEmpty()) {
   
            throw new EmptyStackException();
        }
        return stack.removeLast();
    }

    // 获取栈顶元素
    public int peek() {
   
        if (isEmpty()) {
   
            throw new EmptyStackException();
        }
        return stack.getLast();
    }

    // 检查栈是否为空
    public boolean isEmpty() {
   
        return stack.isEmpty();
    }

    // 获取栈中元素个数
    public int size() {
   
        return stack.size();
    }
}

实现原理解释：

栈通常使用链表或数组来实现。在示例中，我们使用Java中的LinkedList来实现栈。
入栈操作：将新元素添加到链表的末尾，因为栈是后进先出的，所以新元素会被添加到栈的顶部。
出栈操作：从链表的末尾移除元素，因为栈中的最后一个元素最后进入，所以需要从栈的顶部移除元素。
获取栈顶元素：返回链表的末尾元素，但不移除它。
检查栈是否为空：判断链表是否为空。
获取栈中元素个数：返回链表的大小，即栈中元素的个数。

栈是一种常见的数据结构，在计算机科学中有着广泛的应用，例如函数调用、表达式求值、深度优先搜索等算法。

16.哈希表 (HashMap)

哈希表是一种常见的数据结构，用于存储键值对。它通过哈希函数将键映射到哈希表中的索引位置，从而实现快速的插入、删除和查找操作。

示例代码实现：

以下是使用拉链法解决冲突的哈希表的示例代码：

import java.util.*;

class Entry<K, V> {
   
    K key;
    V value;
    Entry<K, V> next;

    public Entry(K key, V value) {
   
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

public class MyHashMap<K, V> {
   
    private static final int DEFAULT_CAPACITY = 16;
    private static final double LOAD_FACTOR_THRESHOLD = 0.75;

    private Entry<K, V>[] buckets;
    private int size;

    public MyHashMap() {
   
        buckets = new Entry[DEFAULT_CAPACITY];
        size = 0;
    }

    // 哈希函数
    private int hash(K key) {
   
        return Objects.hashCode(key) % buckets.length;
    }

    // 插入键值对
    public void put(K key, V value) {
   
        int index = hash(key);
        if (buckets[index] == null) {
   
            buckets[index] = new Entry<>(key, value);
        } else {
   
            Entry<K, V> current = buckets[index];
            while (current != null) {
   
                if (Objects.equals(current.key, key)) {
   
                    current.value = value;
                    return;
                }
                if (current.next == null) {
   
                    current.next = new Entry<>(key, value);
                    break;
                }
                current = current.next;
            }
        }
        size++;
        if ((double)size / buckets.length >= LOAD_FACTOR_THRESHOLD) {
   
            resize();
        }
    }

    // 获取键对应的值
    public V get(K key) {
   
        int index = hash(key);
        Entry<K, V> current = buckets[index];
        while (current != null) {
   
            if (Objects.equals(current.key, key)) {
   
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

    // 删除键值对
    public void remove(K key) {
   
        int index = hash(key);
        Entry<K, V> prev = null;
        Entry<K, V> current = buckets[index];
        while (current != null) {
   
            if (Objects.equals(current.key, key)) {
   
                if (prev == null) {
   
                    buckets[index] = current.next;
                } else {
   
                    prev.next = current.next;
                }
                size--;
                return;
            }
            prev = current;
            current = current.next;
        }
    }

    // 哈希表是否为空
    public boolean isEmpty() {
   
        return size == 0;
    }

    // 哈希表的大小
    public int size() {
   
        return size;
    }

    // 哈希表扩容
    private void resize() {
   
        Entry<K, V>[] oldBuckets = buckets;
        buckets = new Entry[buckets.length * 2];
        size = 0;
        for (Entry<K, V> entry : oldBuckets) {
   
            while (entry != null) {
   
                put(entry.key, entry.value);
                entry = entry.next;
            }
        }
    }
}

实现原理解释：

哈希表通过哈希函数将键映射到哈希表中的索引位置。在示例中，我们使用对象的hashCode()方法来生成哈希值。
解决冲突：当两个不同的键映射到同一个索引位置时，会发生冲突。在示例中，我们使用拉链法（Chaining）来解决冲突，即将具有相同哈希值的键值对存储在同一个索引位置的链表中。
插入操作：首先计算键的哈希值，然后将键值对插入到对应索引处的链表中。如果已存在相同的键，则更新对应的值。
获取操作：通过哈希函数找到键对应的索引位置，然后在对应索引处的链表中查找键对应的值。
删除操作：类似于获取操作，找到键对应的索引位置，然后在对应索引处的链表中删除键值对。
扩容操作：当哈希表的负载因子（键值对数量与数组长度的比值）超过阈值时，会触发扩容操作。扩容后，哈希表的大小会变为原来的两倍，并重新计算每个键值对的哈希值，然后重新插入到扩容后的哈希表中。

哈希表是一种非常常用且高效的数据结构，可以在平均情况下提供O(1)的插入、删除和查找操作。在实际应用中，哈希表被广泛用于实现各种数据结构，如哈希集合、哈希映射等。

17.优先队列 (Priority Queue)

优先队列是一种特殊的队列，它允许在插入元素时赋予每个元素一个优先级，并且每次出队操作都会返回具有最高优先级的元素。

示例代码实现：

以下是使用堆实现的优先队列的示例代码：

import java.util.*;

public class PriorityQueueExample<T extends Comparable<T>> {
   
    private List<T> heap;

    public PriorityQueueExample() {
   
        heap = new ArrayList<>();
    }

    // 入队操作
    public void enqueue(T item) {
   
        heap.add(item);
        siftUp(heap.size() - 1);
    }

    // 出队操作
    public T dequeue() {
   
        if (isEmpty()) {
   
            throw new NoSuchElementException("Priority queue is empty");
        }
        T max = heap.get(0);
        int last = heap.size() - 1;
        heap.set(0, heap.get(last));
        heap.remove(last);
        siftDown(0);
        return max;
    }

    // 获取队列中优先级最高的元素
    public T peek() {
   
        if (isEmpty()) {
   
            throw new NoSuchElementException("Priority queue is empty");
        }
        return heap.get(0);
    }

    // 检查队列是否为空
    public boolean isEmpty() {
   
        return heap.isEmpty();
    }

    // 获取队列中元素个数
    public int size() {
   
        return heap.size();
    }

    // 上移操作，保持堆的性质
    private void siftUp(int i) {
   
        while (i > 0) {
   
            int parent = (i - 1) / 2;
            if (heap.get(i).compareTo(heap.get(parent)) <= 0) {
   
                break;
            }
            swap(i, parent);
            i = parent;
        }
    }

    // 下移操作，保持堆的性质
    private void siftDown(int i) {
   
        int size = heap.size();
        while (i < size) {
   
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int max = i;
            if (left < size && heap.get(left).compareTo(heap.get(max)) > 0) {
   
                max = left;
            }
            if (right < size && heap.get(right).compareTo(heap.get(max)) > 0) {
   
                max = right;
            }
            if (max == i) {
   
                break;
            }
            swap(i, max);
            i = max;
        }
    }

    // 交换元素位置
    private void swap(int i, int j) {
   
        T temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
}

实现原理解释：

优先队列通常使用堆来实现，堆是一种特殊的树形数据结构，满足堆的性质（例如最大堆或最小堆）。
入队操作：将新元素插入到堆的末尾，然后通过上移操作（向上比较交换）来确保新元素满足堆的性质。
出队操作：删除堆顶元素，然后将堆的末尾元素移动到堆顶，并通过下移操作（向下比较交换）来确保堆的性质。
获取优先级最高的元素操作：返回堆顶元素。
优先队列可以用于实现诸如任务调度、事件驱动等应用场景，其中需要根据某种优先级来决定下一步的操作。

18.AVL 树

AVL 树是一种自平衡二叉搜索树，它保持了二叉搜索树的特性，并且在插入或删除节点时通过旋转操作来保持树的平衡，使得树的高度始终保持在较小的范围内，从而提高了搜索、插入和删除操作的效率。

示例代码实现：

以下是 AVL 树的简单实现示例：

class TreeNode {
   
    int val;
    TreeNode left;
    TreeNode right;
    int height;

    public TreeNode(int val) {
   
        this.val = val;
        this.height = 1;
    }
}

public class AVLTree {
   
    private TreeNode root;

    // 获取树的高度
    private int height(TreeNode node) {
   
        if (node == null) {
   
            return 0;
        }
        return node.height;
    }

    // 获取节点的平衡因子
    private int balanceFactor(TreeNode node) {
   
        if (node == null) {
   
            return 0;
        }
        return height(node.left) - height(node.right);
    }

    // 更新节点的高度
    private void updateHeight(TreeNode node) {
   
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }

    // 右旋操作
    private TreeNode rightRotate(TreeNode y) {
   
        TreeNode x = y.left;
        TreeNode T = x.right;

        x.right = y;
        y.left = T;

        updateHeight(y);
        updateHeight(x);

        return x;
    }

    // 左旋操作
    private TreeNode leftRotate(TreeNode x) {
   
        TreeNode y = x.right;
        TreeNode T = y.left;

        y.left = x;
        x.right = T;

        updateHeight(x);
        updateHeight(y);

        return y;
    }

    // 插入节点
    public TreeNode insert(TreeNode node, int val) {
   
        if (node == null) {
   
            return new TreeNode(val);
        }

        if (val < node.val) {
   
            node.left = insert(node.left, val);
        } else if (val > node.val) {
   
            node.right = insert(node.right, val);
        } else {
   
            // 重复值，不处理
            return node;
        }

        updateHeight(node);
        int balance = balanceFactor(node);

        // 左子树不平衡
        if (balance > 1 && val < node.left.val) {
   
            return rightRotate(node);
        }
        // 右子树不平衡
        if (balance < -1 && val > node.right.val) {
   
            return leftRotate(node);
        }
        // 左右情况，先左旋再右旋
        if (balance > 1 && val > node.left.val) {
   
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // 右左情况，先右旋再左旋
        if (balance < -1 && val < node.right.val) {
   
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }
}

实现原理解释：

AVL 树通过维护每个节点的平衡因子来保持树的平衡，平衡因子定义为节点的左子树高度和右子树高度的差。
当插入或删除节点导致树失去平衡时，需要通过旋转操作来恢复平衡。根据失衡的情况，可以进行四种旋转操作：左旋、右旋、左右旋、右左旋。
在 AVL 树中，每个节点的平衡因子必须为 -1、0 或 1。如果某个节点的平衡因子不在这个范围内，则需要进行相应的旋转操作来调整树的结构，以恢复平衡。
插入节点时，需要递归地将节点插入到正确的位置，并在递归回溯过程中更新节点的高度和检查平衡因子。如果插入后导致树失去平衡，则进行相应的旋转操作来恢复平衡。

AVL 树是一种高效的自平衡二叉搜索树，能够保持较低的平均搜索时间。在需要高效地进行搜索、插入和删除操作的场景中，AVL 树是一种非常有用的数据结构。

19.红黑树 (Red-Black Tree)

红黑树是一种自平衡的二叉搜索树，它保持了二叉搜索树的特性，并且通过对节点着色和旋转操作来保持树的平衡，从而确保了树的高度始终保持在对数范围内，提高了搜索、插入和删除操作的效率。

示例代码实现：

以下是红黑树的简单实现示例：

enum Color {
   
    RED, BLACK
}

class TreeNode {
   
    int val;
    TreeNode left;
    TreeNode right;
    Color color;

    public TreeNode(int val) {
   
        this.val = val;
        this.color = Color.RED; // 默认新插入节点为红色
    }
}

public class RedBlackTree {
   
    private TreeNode root;

    // 左旋操作
    private TreeNode leftRotate(TreeNode node) {
   
        TreeNode rightChild = node.right;
        node.right = rightChild.left;
        rightChild.left = node;
        rightChild.color = node.color;
        node.color = Color.RED;
        return rightChild;
    }

    // 右旋操作
    private TreeNode rightRotate(TreeNode node) {
   
        TreeNode leftChild = node.left;
        node.left = leftChild.right;
        leftChild.right = node;
        leftChild.color = node.color;
        node.color = Color.RED;
        return leftChild;
    }

    // 颜色翻转
    private void flipColors(TreeNode node) {
   
        node.color = Color.RED;
        node.left.color = Color.BLACK;
        node.right.color = Color.BLACK;
    }

    // 检查节点是否为红色
    private boolean isRed(TreeNode node) {
   
        return node != null && node.color == Color.RED;
    }

    // 插入节点
    public void insert(int val) {
   
        root = insert(root, val);
        root.color = Color.BLACK; // 根节点始终为黑色
    }

    private TreeNode insert(TreeNode node, int val) {
   
        if (node == null) {
   
            return new TreeNode(val);
        }

        if (val < node.val) {
   
            node.left = insert(node.left, val);
        } else if (val > node.val) {
   
            node.right = insert(node.right, val);
        }

        // 调整树结构，保持红黑树的特性
        if (isRed(node.right) && !isRed(node.left)) {
   
            node = leftRotate(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
   
            node = rightRotate(node);
        }
        if (isRed(node.left) && isRed(node.right)) {
   
            flipColors(node);
        }

        return node;
    }
}

实现原理解释：

红黑树通过对节点着色（红色或黑色）和旋转操作来保持树的平衡。
红黑树的每个节点具有颜色属性，可以是红色或黑色。根据红黑树的性质，根节点和叶子节点（NIL 节点）必须为黑色，红色节点的子节点必须为黑色。
插入操作时，首先将新插入的节点着为红色，然后根据不同的情况进行旋转和颜色调整操作，以保持红黑树的特性。
插入节点后，通过旋转和颜色调整操作，保持了树的平衡性，并且树的高度始终保持在对数范围内，从而提高了搜索、插入和删除操作的效率。

红黑树是一种高效的自平衡二叉搜索树，常用于实现各种高级数据结构和算法，如Java中的TreeMap和TreeSet。

20. B树 (B-Tree)

B 树是一种多路搜索树，它具有以下特点：每个节点可以包含多个子节点，每个节点中的键值按顺序排列，并且对应的子树范围也按顺序排列。B 树通常用于数据库和文件系统等需要大量数据存储和高效检索的场景。

示例代码实现：

B 树的实现相对复杂，以下是简化版本的示例代码：

class BTreeNode {
   
    int[] keys;
    int numKeys;
    BTreeNode[] children;
    boolean leaf;

    public BTreeNode(int t, boolean leaf) {
   
        this.keys = new int[2 * t - 1];
        this.children = new BTreeNode[2 * t];
        this.numKeys = 0;
        this.leaf = leaf;
    }
}

public class BTree {
   
    private BTreeNode root;
    private int t; // B 树的度

    public BTree(int t) {
   
        this.root = null;
        this.t = t;
    }

    // 在 B 树中搜索给定的键
    public boolean search(int key) {
   
        return search(root, key);
    }

    private boolean search(BTreeNode node, int key) {
   
        int i = 0;
        while (i < node.numKeys && key > node.keys[i]) {
   
            i++;
        }
        if (i < node.numKeys && key == node.keys[i]) {
   
            return true;
        }
        if (node.leaf) {
   
            return false;
        }
        return search(node.children[i], key);
    }

    // 在 B 树中插入键
    public void insert(int key) {
   
        if (root == null) {
   
            root = new BTreeNode(t, true);
            root.keys[0] = key;
            root.numKeys = 1;
        } else {
   
            if (root.numKeys == 2 * t - 1) {
   
                BTreeNode newRoot = new BTreeNode(t, false);
                newRoot.children[0] = root;
                splitChild(newRoot, 0);
                root = newRoot;
            }
            insertNonFull(root, key);
        }
    }

    private void insertNonFull(BTreeNode node, int key) {
   
        int i = node.numKeys - 1;
        if (node.leaf) {
   
            while (i >= 0 && key < node.keys[i]) {
   
                node.keys[i + 1] = node.keys[i];
                i--;
            }
            node.keys[i + 1] = key;
            node.numKeys++;
        } else {
   
            while (i >= 0 && key < node.keys[i]) {
   
                i--;
            }
            i++;
            if (node.children[i].numKeys == 2 * t - 1) {
   
                splitChild(node, i);
                if (key > node.keys[i]) {
   
                    i++;
                }
            }
            insertNonFull(node.children[i], key);
        }
    }

    private void splitChild(BTreeNode parentNode, int childIndex) {
   
        BTreeNode childNode = parentNode.children[childIndex];
        BTreeNode newChildNode = new BTreeNode(t, childNode.leaf);
        newChildNode.numKeys = t - 1;

        for (int j = 0; j < t - 1; j++) {
   
            newChildNode.keys[j] = childNode.keys[j + t];
        }

        if (!childNode.leaf) {
   
            for (int j = 0; j < t; j++) {
   
                newChildNode.children[j] = childNode.children[j + t];
            }
        }

        childNode.numKeys = t - 1;

        for (int j = parentNode.numKeys; j >= childIndex + 1; j--) {
   
            parentNode.children[j + 1] = parentNode.children[j];
        }
        parentNode.children[childIndex + 1] = newChildNode;

        for (int j = parentNode.numKeys - 1; j >= childIndex; j--) {
   
            parentNode.keys[j + 1] = parentNode.keys[j];
        }
        parentNode.keys[childIndex] = childNode.keys[t - 1];
        parentNode.numKeys++;
    }
}

实现原理解释：

B 树是一种平衡的多路搜索树，每个节点可以包含多个子节点。节点中的键值按顺序排列，并且对应的子树范围也按顺序排列。
B 树的度（degree）定义为每个节点中子节点的最小数量，通常用 t 来表示。根据度的大小，B 树可以是 2-3 树、2-3-4 树等。
插入操作时，首先搜索到合适的叶子节点，并在叶子节点中插入新的键值。如果插入后导致节点的键值数量超过了阈值，则进行节点分裂操作。
节点分裂操作将节点一分为二，并将中间的键值提升到父节点。如果父节点的键值数量超过了阈值，则递归进行分裂操作。
B 树具有平衡性，可以保持较低的高度，并且可以实现高效的搜索、插入和删除操作。在需要大量数据存储和高效检索的场景中，B 树是一种非常有用的数据结构。

21.Trie 树

Trie 树（字典树）是一种树形数据结构，用于高效地存储和检索字符串集合。它的特点是每个节点都代表一个字符串的前缀，从根节点到每个节点的路径构成一个字符串。

示例代码实现：

以下是 Trie 树的简单实现示例：

class TrieNode {
   
    TrieNode[] children;
    boolean isEnd;

    public TrieNode() {
   
        children = new TrieNode[26]; // 假设只包含小写字母
        isEnd = false;
    }
}

public class Trie {
   
    private TrieNode root;

    public Trie() {
   
        root = new TrieNode();
    }

    // 插入单词
    public void insert(String word) {
   
        TrieNode node = root;
        for (char c : word.toCharArray()) {
   
            int index = c - 'a';
            if (node.children[index] == null) {
   
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    // 搜索单词
    public boolean search(String word) {
   
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    // 搜索前缀
    public boolean startsWith(String prefix) {
   
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String prefix) {
   
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
   
            int index = c - 'a';
            if (node.children[index] == null) {
   
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

实现原理解释：

Trie 树是一种树形数据结构，每个节点代表一个字符串的前缀。根节点代表空字符串，每个节点的子节点代表该节点对应的字符串后面添加一个字符后得到的新前缀。
Trie 树的每个节点包含一个数组，数组的大小通常为字符集大小（例如ASCII码中的26个小写字母），数组中的每个元素对应一个可能的字符，表示该字符在当前节点的子节点中是否存在。
插入操作时，从根节点开始，逐个遍历待插入字符串的字符，根据字符找到对应的子节点，并创建新节点（如果子节点不存在）。在插入完成后，标记最后一个节点为单词结束节点。
搜索操作时，从根节点开始，逐个遍历待搜索字符串的字符，根据字符找到对应的子节点，如果子节点不存在，则表示字符串不存在于 Trie 树中。
Trie 树的时间复杂度取决于字符串的长度，对于每个操作（插入、搜索、删除），时间复杂度均为 O(m)，其中 m 表示字符串的长度。Trie 树可以实现高效的字符串存储和检索。

22.Bloom Filter

Bloom Filter（布隆过滤器）是一种高效的数据结构，用于判断一个元素是否属于一个集合。它可以快速地告诉你一个元素不在集合中，或者可能在集合中。

示例代码实现：

以下是 Bloom Filter 的简单实现示例：

import java.util.BitSet;

public class BloomFilter {
   
    private BitSet bitSet;
    private int size;
    private int[] hashFunctions;

    public BloomFilter(int size, int numHashFunctions) {
   
        this.bitSet = new BitSet(size);
        this.size = size;
        this.hashFunctions = new int[numHashFunctions];
    }

    // 添加元素
    public void add(String element) {
   
        for (int i = 0; i < hashFunctions.length; i++) {
   
            int hash = hash(element, i);
            bitSet.set(hash);
        }
    }

    // 查询元素是否可能存在
    public boolean contains(String element) {
   
        for (int i = 0; i < hashFunctions.length; i++) {
   
            int hash = hash(element, i);
            if (!bitSet.get(hash)) {
   
                return false;
            }
        }
        return true;
    }

    // 哈希函数
    private int hash(String element, int index) {
   
        // 实际应用中通常采用多种哈希函数，这里简化为使用字符串的哈希码
        return (element.hashCode() + index) % size;
    }
}

实现原理解释：

Bloom Filter 的实现原理比较简单，基本思想是使用多个哈希函数来表示一个元素在集合中的存在情况。Bloom Filter 主要有两个基本操作：插入元素和查询元素。

插入元素：将要插入的元素经过多个哈希函数计算得到多个哈希值，并将对应的位数组中的位置设为1。
查询元素：对于查询元素，同样经过多个哈希函数计算得到多个哈希值，并检查对应的位数组中的位置是否都为1。如果有任何一位为0，则可以确定该元素一定不在集合中；如果所有位都为1，则该元素可能在集合中，但也有可能是误判。

由于 Bloom Filter 只是用来判断一个元素可能存在于一个集合中，因此在查询结果为存在时，还需要进一步验证。Bloom Filter 是一种空间效率和时间效率都较高的数据结构，适用于需要快速判断元素是否可能存在于集合中的场景，但不适用于需要100%准确性的场景。

在实际应用中，可以使用更复杂的哈希函数，并根据实际情况选择合适的位数组大小和哈希函数数量，以平衡空间占用和查询性能。Bloom Filter 主要用于缓存、数据库查询优化等场景，能够显著降低查询时间和存储空间的开销。

最后

好了，以上是 V 哥整理的22个数据结构的案列实现和原理解释，V 哥建议，数据结构一定要理解原理和实现逻辑，代码实现不一定是一样的，只要满足原理即可，最近遇到有参加 OD 面试的，机考是必须开着摄像头共享屏幕现写代码，考的就是数据结构这类题，然后技术面试依然是数据结构算法题，即问即答，想要通过面试，收藏起来慢慢学习吧。关注威哥爱编程，一起成长。

22个常用数据结构实现与原理分析

1.数组（Array）

2.链表 (Linked List)

3.栈 (Stack)

4.队列 (Queue)

5.双端队列（Deque）

6.哈希表 (Hash Table)

7.树 (Tree)

8.平衡二叉树 (Balanced Binary Tree)

9.红黑树 (Red-Black Tree)

10.堆 (Heap)

11.图 (Graph)

12.字典树 (Trie)

13.哈希集合 (HashSet)

14.队列 (Queue)

15.栈 (Stack)

16.哈希表 (HashMap)

17.优先队列 (Priority Queue)

18.AVL 树

19.红黑树 (Red-Black Tree)

20. B树 (B-Tree)

21.Trie 树

22.Bloom Filter

最后

热门文章

最新文章

相关课程

相关电子书