117.info
人生若只如初见

实现一个红黑树迭代器:C++编程挑战

#include 
#include 
#include 

enum Color {
    RED,
    BLACK
};

struct Node {
    int data;
    Color color;
    Node* left;
    Node* right;
    Node* parent;

    Node(int data, Color color) : data(data), color(color), left(nullptr), right(nullptr), parent(nullptr) {}
};

class RedBlackTree {
private:
    Node* root;

public:
    RedBlackTree() : root(nullptr) {}

    void insert(int data) {
        Node* new_node = new Node(data, RED);
        if (root == nullptr) {
            root = new_node;
            root->color = BLACK;
            return;
        }

        Node* current = root;
        Node* parent = nullptr;

        while (current != nullptr) {
            parent = current;
            if (data < current->data) {
                current = current->left;
            } else {
                current = current->right;
            }
        }

        new_node->parent = parent;
        if (data < parent->data) {
            parent->left = new_node;
        } else {
            parent->right = new_node;
        }

        fix_insert(new_node);
    }

    void fix_insert(Node* node) {
        while (node != root && node->parent->color == RED) {
            if (node->parent == node->parent->parent->left) {
                Node* uncle = node->parent->parent->right;
                if (uncle != nullptr && uncle->color == RED) {
                    node->parent->color = BLACK;
                    uncle->color = BLACK;
                    node->parent->parent->color = RED;
                    node = node->parent->parent;
                } else {
                    if (node == node->parent->right) {
                        node = node->parent;
                        rotate_left(node);
                    }
                    node->parent->color = BLACK;
                    node->parent->parent->color = RED;
                    rotate_right(node->parent->parent);
                }
            } else {
                Node* uncle = node->parent->parent->left;
                if (uncle != nullptr && uncle->color == RED) {
                    node->parent->color = BLACK;
                    uncle->color = BLACK;
                    node->parent->parent->color = RED;
                    node = node->parent->parent;
                } else {
                    if (node == node->parent->left) {
                        node = node->parent;
                        rotate_right(node);
                    }
                    node->parent->color = BLACK;
                    node->parent->parent->color = RED;
                    rotate_left(node->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }

    void rotate_left(Node* node) {
        Node* right_child = node->right;
        node->right = right_child->left;
        if (right_child->left != nullptr) {
            right_child->left->parent = node;
        }
        right_child->parent = node->parent;
        if (node->parent == nullptr) {
            root = right_child;
        } else if (node == node->parent->left) {
            node->parent->left = right_child;
        } else {
            node->parent->right = right_child;
        }
        right_child->left = node;
        node->parent = right_child;
    }

    void rotate_right(Node* node) {
        Node* left_child = node->left;
        node->left = left_child->right;
        if (left_child->right != nullptr) {
            left_child->right->parent = node;
        }
        left_child->parent = node->parent;
        if (node->parent == nullptr) {
            root = left_child;
        } else if (node == node->parent->right) {
            node->parent->right = left_child;
        } else {
            node->parent->left = left_child;
        }
        left_child->right = node;
        node->parent = left_child;
    }

    void inorder_traversal(Node* node, std::queue<int>& q) {
        if (node == nullptr) {
            return;
        }
        inorder_traversal(node->left, q);
        q.push(node->data);
        inorder_traversal(node->right, q);
    }

    std::queue inorder() {
        std::queue q;
        inorder_traversal(root, q);
        return q;
    }
};

class RedBlackTreeIterator {
private:
    std::queue inorder_list;

public:
    RedBlackTreeIterator(RedBlackTree& tree) {
        inorder_list = tree.inorder();
    }

    int next() {
        int data = https://www.yisu.com/ask/inorder_list.front();"hljs">bool hasNext() {
        return !inorder_list.empty();
    }
};

int main() {
    RedBlackTree tree;
    tree.insert(10);
    tree

未经允许不得转载 » 本文链接:https://www.117.info/ask/fe7f4AzsIBgVfBlw.html

推荐文章

  • c#中return的特点有哪些

    在C#中,return语句具有以下特点: 返回值:return语句用于从方法中返回一个值。返回值的类型必须与方法声明的返回类型相匹配。 终止方法执行:当执行return语句...

  • c#中return的用法是什么

    在C#中,return语句用于从当前方法中返回一个值,并终止该方法的执行。当return语句执行时,它会立即结束当前方法的执行,并将控制权返回给调用该方法的地方。返...

  • c#中grpc的作用是什么

    C#中的gRPC是一种远程过程调用(RPC)框架,它使用HTTP/2协议进行通信,并支持多种编程语言。gRPC在C#中的作用是用于实现客户端和服务器之间的通信,可以在不同的...

  • c#中grpc的用法是什么

    在 C# 中使用 gRPC 主要通过以下几个步骤: 定义 gRPC 服务和消息类型:在 .proto 文件中定义 gRPC 服务和消息类型,并使用 Protocol Buffers 定义数据结构和服务...

  • 红黑树的查询效率:C++实例分析

    红黑树是一种自平衡的二叉搜索树,其查询效率非常高,时间复杂度为O(log n),其中n为树中节点的个数。下面通过一个C++实例来演示红黑树的查询效率。
    #inclu...

  • 使用红黑树优化C++应用程序的数据结构

    红黑树是一种自平衡的二叉搜索树,它能够在插入和删除操作时保持树的平衡,从而确保树的高度不会过高,提高了查找、插入和删除操作的效率。
    在C++应用程序中...

  • 分析红黑树与AVL树在C++中的性能差异

    在C++中,红黑树和AVL树是两种常见的自平衡二叉搜索树。它们都具有对数时间复杂度的查找、插入和删除操作,但在某些情况下它们的性能会有一些差异。 插入和删除操...

  • 应对C++红黑树的常见面试问题

    什么是红黑树?
    红黑树是一种自平衡的二叉搜索树,它在每个节点上增加了一个额外的属性表示节点的颜色(红色或黑色),并通过一些规则来确保树的平衡性。 红...