Java를 사용하여 레드-블랙 트리 알고리즘을 구현하는 방법-java지도 시간-php.cn

Java를 사용하여 레드-블랙 트리 알고리즘을 구현하는 방법

PHPz

풀어 주다： 2023-09-19 11:24:25

원래의

1348명이 탐색했습니다.

Java를 사용하여 레드-블랙 트리 알고리즘을 구현하는 방법

레드-블랙 트리는 많은 고성능 데이터 구조 및 알고리즘에 널리 사용되는 자체 균형 이진 검색 트리입니다. 이 기사에서는 Java 언어를 사용하여 레드-블랙 트리 알고리즘을 구현하는 방법을 자세히 소개하고 구체적인 코드 예제를 제공합니다.

1. 레드-블랙 트리의 정의

레드-블랙 트리는 다음과 같은 특성을 갖는 이진 검색 트리입니다.

각 노드는 빨간색 또는 검은색 색상을 갖습니다.
모든 리프 노드(NIL 노드, 즉 빈 노드)는 검정색입니다.
노드가 빨간색이면 두 하위 노드는 검정색입니다.
각 노드에 대해 이 노드에서 모든 하위 노드까지의 단순 경로입니다. 리프 노드에는 동일한 수의 검정색 노드가 포함됩니다.
이러한 특성은 트리의 높이를 O(log n) 수준으로 유지하면서 레드-블랙 트리의 균형을 보장합니다.

2. 레드-블랙 트리의 기본 작업

레드-블랙 트리에는 주로 다음과 같은 기본 작업이 포함됩니다.

삽입: 레드-블랙 트리에 노드를 삽입하면 레드-블랙 트리의 특성이 필요합니다.

삭제: 레드-블랙 트리에서 노드를 삭제하려면 레드-블랙 트리의 특성을 유지해야 합니다.
검색: 레드-블랙 트리에서 지정된 노드를 찾습니다. 복구: 레드-블랙 트리의 특성이 삽입으로 인해 파괴될 수 있으며, 직렬 연산 복구를 통과해야 합니다.
삭제 복구: 삭제로 인해 레드-블랙 트리의 특성이 손상될 수 있습니다. 일련의 작업을 통해 수리됩니다.
다음은 Java 언어를 사용하여 레드-블랙 트리를 구현하는 코드 예제입니다.

// 定义红黑树节点类
class Node {
    int key;
    Node parent;
    Node left;
    Node right;
    boolean isRed; // 红色节点为true，黑色节点为false

    public Node(int key) {
        this.key = key;
        this.parent = null;
        this.left = null;
        this.right = null;
        this.isRed = true; // 默认插入的节点为红色节点
    }
}

// 定义红黑树类
class RedBlackTree {
    private Node root;
    private final Node NIL;

    public RedBlackTree() {
        NIL = new Node(-1); // 定义一个表示NIL节点的对象
        NIL.isRed = false; // NIL节点为黑色节点
        root = NIL;
    }

    // 插入节点
    public void insert(int key) {
        Node node = new Node(key);
        Node current = root;
        Node parent = null;
        while (current != NIL) {
            parent = current;
            if (key < current.key) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        node.parent = parent;
        if (parent == null) {
            root = node;
        } else if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        node.left = NIL;
        node.right = NIL;
        node.isRed = true;
        insertFixup(node);
    }

    // 插入修复
    private void insertFixup(Node node) {
        while (node.parent.isRed) {
            if (node.parent == node.parent.parent.left) {
                Node uncle = node.parent.parent.right;
                if (uncle.isRed) { // Case 1: 叔节点为红色
                    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 {
                Node uncle = node.parent.parent.left;
                if (uncle.isRed) { // Case 1: 叔节点为红色
                    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(Node node) {
        Node child = node.right;
        node.right = child.left;
        if (child.left != NIL) {
            child.left.parent = node;
        }
        child.parent = node.parent;
        if (node.parent == NIL) {
            root = child;
        } else if (node == node.parent.left) {
            node.parent.left = child;
        } else {
            node.parent.right = child;
        }
        child.left = node;
        node.parent = child;
    }

    // 右旋转
    private void rightRotate(Node node) {
        Node child = node.left;
        node.left = child.right;
        if (child.right != NIL) {
            child.right.parent = node;
        }
        child.parent = node.parent;
        if (node.parent == NIL) {
            root = child;
        } else if (node == node.parent.right) {
            node.parent.right = child;
        } else {
            node.parent.left = child;
        }
        child.right = node;
        node.parent = child;
    }

    // 查找节点
    public Node search(int key) {
        Node current = root;
        while (current != NIL && key != current.key) {
            if (key < current.key) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return current;
    }
}

// 测试红黑树的代码
public class Main {
    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(40);
        tree.insert(50);
        tree.insert(60);
        tree.insert(70);
        Node node = tree.search(50);
        if (node != tree.NIL) {
            System.out.println("找到了节点：" + node.key);
        } else {
            System.out.println("没有找到节点");
        }
    }
}

로그인 후 복사

위 코드를 Java 클래스 파일로 컴파일하고 실행하여 레드-블랙 트리의 삽입 및 검색 작업을 구현합니다. 필요에 따라 삭제 작업과 삭제 복구 코드를 추가할 수도 있습니다.

요약:

이 글에서는 레드-블랙 트리의 정의와 기본 동작을 소개하고, Java를 사용하여 레드-블랙 트리를 구현하기 위한 코드 예제를 제공합니다. 레드-블랙 트리는 자체 균형 이진 검색 트리로서 대용량 데이터 처리 및 고성능 알고리즘에 중요한 역할을 합니다. 레드-블랙 트리의 원리와 구현을 익히면 데이터 구조와 알고리즘의 설계와 적용을 더 잘 이해하는 데 도움이 됩니다. 이 글이 독자들에게 도움이 되기를 바랍니다.

위 내용은 Java를 사용하여 레드-블랙 트리 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!