Javaを使用して赤黒ツリーアルゴリズムを実装する方法

Java を使用して赤黒ツリー アルゴリズムを実装する方法

赤黒ツリーは、多くの高機能で使用される自己平衡型二分探索ツリーです。パフォーマンス データ構造とアルゴリズムは広く使用されています。この記事では、Java 言語を使用して赤黒ツリー アルゴリズムを実装する方法と具体的なコード例を詳しく紹介します。

1. 赤黒ツリーの定義

赤黒ツリーは二分探索木であり、次の特徴があります:

1. 各ノードは次の特徴を持っています。 a 色、赤または黒;
2. ルート ノードは黒です;
3. 各リーフ ノード (NIL ノード、つまり空のノード) は黒です;
4. Ifノードが赤、その 2 つの子ノードが黒;
5. 各ノードについて、そのノードからそのすべての子孫リーフ ノードへの単純なパスには、同じ数の黒いノードが含まれます。

これらの機能により、赤と黒の木のバランスが確保され、木の高さが O(log n) レベルに維持されます。

2. 赤黒ツリーの基本操作

赤黒ツリーには主に以下の基本操作が含まれます:

1. 挿入: 赤黒ツリーにノードを挿入します。黒ツリー、赤黒ツリーの特性を維持する必要があります;
2. 削除: 赤黒ツリーからノードを削除します、赤黒ツリーの特性を維持する必要があります;
3. 検索: 赤黒ツリー ノード内の指定されたノードを検索します。
4. 挿入修復: 赤黒ツリーの特性は挿入により損傷している可能性があるため、一連の手順を通じて修復する必要があります。操作;
5. 削除修復: 削除により赤黒ツリーの特性が損なわれている可能性があるため、一連の操作を通じて修復する必要があります。

次は、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("没有找到节点");
        }
    }
}

テスト コードを実行した出力結果は次のとおりです: "ノードが見つかりました: 50" 、赤黒ツリーを示します。挿入操作と検索操作の両方が正常に機能します。

上記のコードを Java クラス ファイルとしてコンパイルして実行し、赤黒ツリーの挿入と検索操作を実現します。必要に応じて、削除操作や削除修復コードを追加することもできます。

概要:

この記事では、赤黒ツリーの定義と基本操作を紹介し、Java を使用して赤黒ツリーを実装するコード例を示します。赤黒ツリーは、自己平衡型二分探索ツリーとして、大量のデータと高性能アルゴリズムの処理において重要な役割を果たします。赤黒ツリーの原理と実装をマスターすることは、データ構造とアルゴリズムの設計と適用をより深く理解するのに役立ちます。この記事が読者のお役に立てば幸いです。

以上がJavaを使用して赤黒ツリーアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。