技术-数据结构

二叉树

特点

1. 节点结构：
   - 每个节点最多有两个子节点，分别称为左子节点和右子节点。
2. 层次关系：
   - 树的层次从根节点开始，根节点位于第 1 层，子节点位于其父节点的下一层。
   - 每一层的节点数最多为 $$2^{\text{层号}-1}$$（例如，第 1 层最多有 1 个节点，第 2 层最多有 2 个节点）。
3. 树的高度：
   - 树的高度是从根节点到叶子节点的最长路径上的节点数。
4. 子树结构：
   - 二叉树的每个子树本身也是一个二叉树。
5. 特殊操作规则：
   - 在二叉搜索树（BST）中，左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。
   - 在堆中（如最大堆或最小堆），根节点具有特殊的大小关系（最大堆：根节点最大；最小堆：根节点最小）。

在代码示例中，构建的是一个二叉搜索树（BST），其特点包括：

• 插入和搜索时遵循左小右大的规则。
• 中序遍历会按顺序输出节点的键值对（从小到大）。

代码示例

public class BinaryTree {

    // Node class for the binary tree
    static class Node {
        int key;
        String value;
        Node left, right;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }

    private Node root;

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

    // Method to insert a key-value pair into the binary tree
    public void insert(int key, String value) {
        root = insertRec(root, key, value);
    }

    private Node insertRec(Node root, int key, String value) {
        if (root == null) {
            root = new Node(key, value);
            return root;
        }

        if (key < root.key) {
            root.left = insertRec(root.left, key, value);
        } else if (key > root.key) {
            root.right = insertRec(root.right, key, value);
        }

        return root;
    }

    // Method to search for a value by its key
    public String search(int key) {
        Node result = searchRec(root, key);
        return result != null ? result.value : null;
    }

    private Node searchRec(Node root, int key) {
        if (root == null || root.key == key) {
            return root;
        }

        if (key < root.key) {
            return searchRec(root.left, key);
        }

        return searchRec(root.right, key);
    }

    // In-order traversal to display the tree
    public void inOrderTraversal() {
        inOrderRec(root);
    }

    private void inOrderRec(Node root) {
        if (root != null) {
            inOrderRec(root.left);
            System.out.println("Key: " + root.key + ", Value: " + root.value);
            inOrderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        // Insert key-value pairs into the binary tree
        tree.insert(50, "Value50");
        tree.insert(30, "Value30");
        tree.insert(70, "Value70");
        tree.insert(20, "Value20");
        tree.insert(40, "Value40");
        tree.insert(60, "Value60");
        tree.insert(80, "Value80");

        // Display the binary tree in in-order
        System.out.println("In-order traversal of the binary tree:");
        tree.inOrderTraversal();

        // Search for a value by key
        int searchKey = 40;
        String result = tree.search(searchKey);
        System.out.println("\nSearch result for key " + searchKey + ": " + (result != null ? result : "Not found"));
    }
}

AVL树

特点

AVL树的特点

1. 平衡性：

• AVL树是自平衡的二叉搜索树。
• 每个节点的左右子树的高度差（即平衡因子）最多为1。
• 插入和删除节点后，AVL树通过旋转操作（左旋、右旋等）重新保持平衡。

2. 二叉搜索树的特性：

• 对于每个节点，其左子树中的所有节点值小于该节点的值，其右子树中的所有节点值大于该节点的值。
• 中序遍历的结果是按键值排序的序列。

3. 高度最优：

• AVL树的高度与节点数目之间的关系为 O(log⁡n)O(\log n)，插入、删除和查询的时间复杂度都能保持在 O(log⁡n)O(\log n)。

4. 旋转操作：

• 平衡因子超过1时，通过旋转恢复平衡。

  • 左左（LL）旋转：单次右旋。

  

  • 右右（RR）旋转：单次左旋。

  

  • 左右（LR）旋转：先左旋后右旋。
  • 右左（RL）旋转：先右旋后左旋。

  

5. 适用场景：

• 适用于插入和删除操作较频繁，同时要求查询效率较高的场景，例如数据库索引。

代码示例

public class AvlTree {

    // Node class for the AVL tree
    static class Node {
        int key;
        String value;
        int height;
        Node left, right;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
            this.height = 1;
        }
    }

    private Node root;

    // Get the height of a node
    private int height(Node node) {
        return node == null ? 0 : node.height;
    }

    // Get the balance factor of a node
    private int getBalance(Node node) {
        return node == null ? 0 : height(node.left) - height(node.right);
    }

    // Right rotate subtree rooted with y
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node 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;
    }

    // Left rotate subtree rooted with x
    private Node leftRotate(Node x) {
        Node y = x.right;
        Node 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;
    }

    // Insert a key-value pair into the AVL tree
    public void insert(int key, String value) {
        root = insertRec(root, key, value);
    }

    private Node insertRec(Node node, int key, String value) {
        if (node == null) {
            return new Node(key, value);
        }

        if (key < node.key) {
            node.left = insertRec(node.left, key, value);
        } else if (key > node.key) {
            node.right = insertRec(node.right, key, value);
        } else {
            return node; // Duplicate keys not allowed
        }

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

        int balance = getBalance(node);

        // Left Left Case
        if (balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }

        // Right Right Case
        if (balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }

        // Left Right Case
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    // Search for a value by its key
    public String search(int key) {
        Node result = searchRec(root, key);
        return result != null ? result.value : null;
    }

    private Node searchRec(Node node, int key) {
        if (node == null || node.key == key) {
            return node;
        }

        if (key < node.key) {
            return searchRec(node.left, key);
        }

        return searchRec(node.right, key);
    }

    // In-order traversal to display the tree
    public void inOrderTraversal() {
        inOrderRec(root);
    }

    private void inOrderRec(Node node) {
        if (node != null) {
            inOrderRec(node.left);
            System.out.println("Key: " + node.key + ", Value: " + node.value);
            inOrderRec(node.right);
        }
    }

    public static void main(String[] args) {
        AvlTree tree = new AvlTree();

        // Insert key-value pairs into the AVL tree
        tree.insert(50, "Value50");
        tree.insert(30, "Value30");
        tree.insert(70, "Value70");
        tree.insert(20, "Value20");
        tree.insert(40, "Value40");
        tree.insert(60, "Value60");
        tree.insert(80, "Value80");

        // Display the AVL tree in in-order
        System.out.println("In-order traversal of the AVL tree:");
        tree.inOrderTraversal();

        // Search for a value by key
        int searchKey = 40;
        String result = tree.search(searchKey);
        System.out.println("\nSearch result for key " + searchKey + ": " + (result != null ? result : "Not found"));
    }
}

红黑树

特点

红黑树的特点如下：

1. 节点颜色属性：
   - 每个节点要么是红色，要么是黑色。
2. 根节点是黑色：
   - 红黑树的根节点必须是黑色。
3. 红色节点规则：
   - 红色节点不能有红色子节点，即红色节点的子节点必须是黑色（即不能有连续的红色节点）。
4. 每条路径黑节点一致：
   - 从任一节点到其叶子节点或空子节点的所有路径上必须包含相同数量的黑色节点。
5. 自平衡性：
   - 红黑树通过上述规则保持平衡，确保从根到叶子的最长路径不会超过最短路径的两倍。
   - 平衡性靠旋转和颜色变换实现。
6. 操作效率：
   - 插入、删除和查找的时间复杂度均为 O(log⁡n)O(\log n)。
   - 插入和删除操作中，需要通过旋转和重新着色来维持红黑树的性质。
7. 旋转操作：
   - 与AVL树类似，红黑树也有左旋和右旋操作，用于重新平衡树。
8. 应用场景：
   - 红黑树是 Java 的 TreeMap 和 TreeSet 的底层数据结构。
   - 它在动态数据集和需要快速插入、删除、查找的场景中广泛应用，例如数据库和文件系统的实现。

红黑树比AVL树的旋转操作更少，插入和删除操作的性能更优，但查询性能略逊于AVL树，因为它的高度可能比AVL树稍大。

代码示例

public class RedBlackTree {

    // Node class for the red-black tree
    static class Node {
        int key;
        String value;
        Node left, right, parent;
        boolean isRed;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
            this.isRed = true; // New nodes are always red initially
        }
    }

    private Node root;

    // Left rotate subtree rooted with x
    private void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // Right rotate subtree rooted with y
    private void rightRotate(Node y) {
        Node x = y.left;
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }
        x.parent = y.parent;
        if (y.parent == null) {
            root = x;
        } else if (y == y.parent.left) {
            y.parent.left = x;
        } else {
            y.parent.right = x;
        }
        x.right = y;
        y.parent = x;
    }

    // Insert a key-value pair into the red-black tree
    public void insert(int key, String value) {
        Node node = new Node(key, value);
        root = insertRec(root, node);
        fixViolation(node);
    }

    private Node insertRec(Node root, Node node) {
        if (root == null) {
            return node;
        }

        if (node.key < root.key) {
            root.left = insertRec(root.left, node);
            root.left.parent = root;
        } else if (node.key > root.key) {
            root.right = insertRec(root.right, node);
            root.right.parent = root;
        }

        return root;
    }

    // Fix the red-black tree violations after insertion
    private void fixViolation(Node node) {
        Node parent = null;
        Node grandParent = null;

        while (node != root && node.isRed && node.parent.isRed) {
            parent = node.parent;
            grandParent = parent.parent;

            // Case A: Parent is left child of grandparent
            if (parent == grandParent.left) {
                Node uncle = grandParent.right;

                // Case 1: Uncle is red (Recoloring)
                if (uncle != null && uncle.isRed) {
                    grandParent.isRed = true;
                    parent.isRed = false;
                    uncle.isRed = false;
                    node = grandParent;
                } else {
                    // Case 2: Node is right child (Left rotation)
                    if (node == parent.right) {
                        leftRotate(parent);
                        node = parent;
                        parent = node.parent;
                    }

                    // Case 3: Node is left child (Right rotation)
                    rightRotate(grandParent);
                    boolean temp = parent.isRed;
                    parent.isRed = grandParent.isRed;
                    grandParent.isRed = temp;
                    node = parent;
                }
            } else { // Case B: Parent is right child of grandparent
                Node uncle = grandParent.left;

                // Case 1: Uncle is red (Recoloring)
                if (uncle != null && uncle.isRed) {
                    grandParent.isRed = true;
                    parent.isRed = false;
                    uncle.isRed = false;
                    node = grandParent;
                } else {
                    // Case 2: Node is left child (Right rotation)
                    if (node == parent.left) {
                        rightRotate(parent);
                        node = parent;
                        parent = node.parent;
                    }

                    // Case 3: Node is right child (Left rotation)
                    leftRotate(grandParent);
                    boolean temp = parent.isRed;
                    parent.isRed = grandParent.isRed;
                    grandParent.isRed = temp;
                    node = parent;
                }
            }
        }

        root.isRed = false; // Root is always black
    }

    // In-order traversal to display the tree
    public void inOrderTraversal() {
        inOrderRec(root);
    }

    private void inOrderRec(Node node) {
        if (node != null) {
            inOrderRec(node.left);
            System.out.println("Key: " + node.key + ", Value: " + node.value + ", Color: " + (node.isRed ? "Red" : "Black"));
            inOrderRec(node.right);
        }
    }

    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();

        // Insert key-value pairs into the red-black tree
        tree.insert(50, "Value50");
        tree.insert(30, "Value30");
        tree.insert(70, "Value70");
        tree.insert(20, "Value20");
        tree.insert(40, "Value40");
        tree.insert(60, "Value60");
        tree.insert(80, "Value80");

        // Display the red-black tree in in-order
        System.out.println("In-order traversal of the red-black tree:");
        tree.inOrderTraversal();
    }
}