首页 >c++编程 >红黑树:C++实现与应用

红黑树:C++实现与应用

来源:www.hellomonster.net 时间:2024-05-16 16:36:15 作者:第一编程网 浏览: [手机版]

  红黑树是一种自平衡的二叉搜索树,它能够保在最坏情况下的时间复杂度O(log n)第~一~编~程~网。红黑树的实现有很多种,但是C++语言是一种非常适合实现红黑树的语言。本文将介绍红黑树的基本概念、C++实现以及应用

红黑树:C++实现与应用(1)

一、红黑树的基本概念

红黑树是一种自平衡的二叉搜索树,它满足以下五个性质:

  1. 每个节点要么是红色,要么是黑色。

  2. 根节点是黑色的来源www.hellomonster.net

  3. 每个叶节点(NIL节点,空节点)是黑色的。

4. 如果一个节点是红色的,则它的两个节点都是黑色的。

  5. 对于每个节点,从该节点到其所有后节点的简单路径上,均包含相同数目的黑色节点。

  通过这五个性质,红黑树能够保平衡性,从而保在最坏情况下的时间复杂度O(log n)yGM

红黑树:C++实现与应用(2)

二、C++实现

在C++语言中,我们可以使用模板类来实现红黑树。下是一个简单的红黑树模板类的实现:

```cpp

template

class RBTree {

  public:

  RBTree() : root(nullptr) {}

  ~RBTree() { clear(); }

void insert(const T& val);

  void remove(const T& val);

bool search(const T& val) const;

  void clear();

  private:

  struct Node {

  T val;

bool is_black;

Node* parent;

  Node* left;

Node* right;

Node(const T& val, bool is_black=true, Node* parent=nullptr, Node* left=nullptr, Node* right=nullptr)

: val(val), is_black(is_black), parent(parent), left(left), right(right) {}

  };

Node* root;

Node* grandparent(Node* node) const;

Node* uncle(Node* node) const;

  Node* sibling(Node* node) const;

  void rotate_left(Node* node);

void rotate_right(Node* node);

  void insert_case1(Node* node);

  void insert_case2(Node* node);

  void insert_case3(Node* node);

  void insert_case4(Node* node);

  void insert_case5(Node* node);

void remove_case1(Node* node);

  void remove_case2(Node* node);

  void remove_case3(Node* node);

  void remove_case4(Node* node);

  void remove_case5(Node* node);

void remove_case6(Node* node);

Node* find_node(const T& val) const;

};

  template

  void RBTree::insert(const T& val) {

  Node* node = new Node(val);

  Node* parent = nullptr;

Node* current = root;

  while (current != nullptr) {

  parent = current;

  if (val val) {

  current = current->left;

  } else if (val > current->val) {

  current = current->right;

  } else {

  delete node;

  return;

  }

  }

  node->parent = parent;

  if (parent == nullptr) {

  root = node;

  } else if (val val) {

  parent->left = node;

  } else {

  parent->right = node;

  }

  insert_case1(node);

  }

  template

  void RBTree::insert_case1(Node* node) {

  if (node->parent == nullptr) {

node->is_black = true;

  } else {

  insert_case2(node);

  }

  }

  template

void RBTree::insert_case2(Node* node) {

if (node->parent->is_black) {

  return;

  } else {

  insert_case3(node);

  }

}

  template

void RBTree::insert_case3(Node* node) {

  Node* u = uncle(node);

  if (u != nullptr && u->is_black == false) {

node->parent->is_black = true;

  u->is_black = true;

  Node* g = grandparent(node);

  g->is_black = false;

  insert_case1(g);

  } else {

  insert_case4(node);

}

  }

template

  void RBTree::insert_case4(Node* node) {

  Node* g = grandparent(node);

  if (node == node->parent->right && node->parent == g->left) {

  rotate_left(node->parent);

node = node->left;

  } else if (node == node->parent->left && node->parent == g->right) {

rotate_right(node->parent);

node = node->right;

  }

  insert_case5(node);

  }

  template

void RBTree::insert_case5(Node* node) {

Node* g = grandparent(node);

  node->parent->is_black = true;

g->is_black = false;

  if (node == node->parent->left && node->parent == g->left) {

rotate_right(g);

} else {

  rotate_left(g);

  }

  }

  template

  void RBTree::remove(const T& val) {

  Node* node = find_node(val);

  if (node == nullptr) {

return;

  }

  Node* child = nullptr;

  if (node->left == nullptr || node->right == nullptr) {

  child = node;

  } else {

child = node->right;

while (child->left != nullptr) {

child = child->left;

}

  }

  Node* sibling = sibling(child);

  if (sibling != nullptr) {

if (sibling->is_black == false) {

  node->parent->is_black = false;

  sibling->is_black = true;

  if (child == node->left) {

  rotate_left(node->parent);

} else {

rotate_right(node->parent);

  }

  sibling = sibling(child);

  }

if (node->parent->is_black && sibling->is_black && sibling->left->is_black && sibling->right->is_black) {

  sibling->is_black = false;

  remove_case1(node->parent);

} else if (node->parent->is_black == false && sibling->is_black && sibling->left->is_black && sibling->right->is_black) {

sibling->is_black = false;

  node->parent->is_black = true;

  } else {

  if (child == node->left && sibling->right->is_black) {

sibling->is_black = false;

  sibling->left->is_black = true;

rotate_right(sibling);

sibling = sibling(child);

} else if (child == node->right && sibling->left->is_black) {

  sibling->is_black = false;

  sibling->right->is_black = true;

  rotate_left(sibling);

sibling = sibling(child);

}

sibling->is_black = node->parent->is_black;

node->parent->is_black = true;

  if (child == node->left) {

  sibling->right->is_black = true;

  rotate_left(node->parent);

} else {

sibling->left->is_black = true;

  rotate_right(node->parent);

  }

  }

}

  if (node->parent == nullptr) {

root = child;

} else if (node == node->parent->left) {

  node->parent->left = child;

  } else {

node->parent->right = child;

  }

  if (child != nullptr) {

child->parent = node->parent;

  }

  delete node;

}

  template

  void RBTree::remove_case1(Node* node) {

if (node->parent != nullptr) {

  remove_case2(node);

  }

}

  template

void RBTree::remove_case2(Node* node) {

  Node* sibling = sibling(node);

if (sibling->is_black == false) {

node->parent->is_black = false;

sibling->is_black = true;

  if (node == node->parent->left) {

  rotate_left(node->parent);

  } else {

  rotate_right(node->parent);

}

  }

  remove_case3(node);

}

template

  void RBTree::remove_case3(Node* node) {

Node* sibling = sibling(node);

  if (node->parent->is_black && sibling->is_black && sibling->left->is_black && sibling->right->is_black) {

sibling->is_black = false;

remove_case1(node->parent);

} else {

  remove_case4(node);

}

  }

template

  void RBTree::remove_case4(Node* node) {

  Node* sibling = sibling(node);

  if (node->parent->is_black == false && sibling->is_black && sibling->left->is_black && sibling->right->is_black) {

  sibling->is_black = false;

  node->parent->is_black = true;

  } else {

remove_case5(node);

  }

}

  template

void RBTree::remove_case5(Node* node) {

  Node* sibling = sibling(node);

  if (sibling->is_black) {

if (node == node->parent->left && sibling->right->is_black && sibling->left->is_black == false) {

  sibling->is_black = false;

sibling->left->is_black = true;

  rotate_right(sibling);

} else if (node == node->parent->right && sibling->left->is_black && sibling->right->is_black == false) {

  sibling->is_black = false;

sibling->right->is_black = true;

rotate_left(sibling);

  }

}

  remove_case6(node);

}

template

  void RBTree::remove_case6(Node* node) {

  Node* sibling = sibling(node);

sibling->is_black = node->parent->is_black;

  node->parent->is_black = true;

  if (node == node->parent->left) {

sibling->right->is_black = true;

  rotate_left(node->parent);

  } else {

  sibling->left->is_black = true;

rotate_right(node->parent);

}

  }

template

  typename RBTree::Node* RBTree::grandparent(Node* node) const {

  if (node != nullptr && node->parent != nullptr) {

  return node->parent->parent;

} else {

  return nullptr;

  }

  }

  template

typename RBTree::Node* RBTree::uncle(Node* node) const {

  Node* g = grandparent(node);

  if (g == nullptr) {

  return nullptr;

  } else if (node->parent == g->left) {

  return g->right;

  } else {

return g->left;

  }

  }

template

  typename RBTree::Node* RBTree::sibling(Node* node) const {

  if (node == node->parent->left) {

return node->parent->right;

  } else {

  return node->parent->left;

  }

}

  template

  void RBTree::rotate_left(Node* node) {

  Node* pivot = node->right;

  pivot->parent = node->parent;

  if (node->parent == nullptr) {

  root = pivot;

} else if (node == node->parent->left) {

  node->parent->left = pivot;

  } else {

  node->parent->right = pivot;

}

node->right = pivot->left;

if (pivot->left != nullptr) {

  pivot->left->parent = node;

  }

  node->parent = pivot;

pivot->left = node;

  }

  template

  void RBTree::rotate_right(Node* node) {

Node* pivot = node->left;

  pivot->parent = node->parent;

  if (node->parent == nullptr) {

  root = pivot;

} else if (node == node->parent->left) {

node->parent->left = pivot;

  } else {

  node->parent->right = pivot;

  }

  node->left = pivot->right;

  if (pivot->right != nullptr) {

  pivot->right->parent = node;

  }

node->parent = pivot;

pivot->right = node;

  }

template

typename RBTree::Node* RBTree::find_node(const T& val) const {

  Node* current = root;

  while (current != nullptr) {

if (val val) {

current = current->left;

} else if (val > current->val) {

  current = current->right;

  } else {

return current;

  }

  }

  return nullptr;

}

  template

bool RBTree::search(const T& val) const {

Node* node = find_node(val);

return node != nullptr;

}

  template

void RBTree::clear() {

  std::stack s;

  if (root != nullptr) {

  s.push(root);

  }

  while (!s.empty()) {

Node* node = s.top();

  s.pop();

if (node->left != nullptr) {

s.push(node->left);

}

  if (node->right != nullptr) {

  s.push(node->right);

  }

  delete node;

  }

root = nullptr;

}

```

  在这个实现中,我们使用了一个嵌套结构体Node来表示红黑树的节点。每个节点包含一个值val、一个bool型变量is_black表示节点颜色、一个指向父节点的指针parent、一个指向左节点的指针left和一个指向右节点的指针right。我们还定了一些私有成员函数来辅助实现红黑树的插入和删操作,包括grandparent、uncle、sibling、rotate_left、rotate_right、insert_case1-5和remove_case1-6www.hellomonster.net。这些函数的具体实现可以参考上码。

红黑树:C++实现与应用(3)

三、应用

  红黑树是一种非常常用的数据结构,它经常被用来实现C++ STL中的map和set等器。这些器都是基于红黑树实现的,因此它们具有红黑树的所有特性,包括自平衡、快速查找和插入等。下是一个简单的使用map器的例

  ```cpp

  #include

  #include

  int main() {

  std::map m;

m["Alice"] = 1;

  m["Bob"] = 2;

m["Charlie"] = 3;

std::cout << m["Alice"] << std::endl;

  std::cout << m["Bob"] << std::endl;

std::cout << m["Charlie"] << std::endl;

  return 0;

}

  ```

  在这个例中,我们创建了一个名m的map器,并向其中插入了三个键值对第+一+编+程+网。然后我们使用下标运算符来访问这些键值对,并输出它们的值。由于map器是基于红黑树实现的,因此它能够快速地查找和插入键值对,而且在插入和删操作时会自动进行平衡,从而保器的性能和正确性。

四、总结

  红黑树是一种非常重要的数据结构,它具有自平衡、快速查找和插入等特性,因此被广泛应用于各种场景中。在C++语言中,我们可以使用模板类来实现红黑树,并且可以通过STL中的map和set等器来快速地使用红黑树第一编程网。通过学习本文所介绍的内,相信经掌握了红黑树的基本概念、C++实现以及应用,可以在实际编程中灵活运用。

0% (0)
0% (0)
版权声明:《红黑树:C++实现与应用》一文由第一编程网(www.hellomonster.net)网友投稿,不代表本站观点,版权归原作者本人所有,转载请注明出处,如有侵权、虚假信息、错误信息或任何问题,请尽快与我们联系,我们将第一时间处理!

我要评论

评论 ( 0 条评论)
网友评论仅供其表达个人看法,并不表明好好孕立场。
最新评论

还没有评论,快来做评论第一人吧!
相关文章
  • 简单的c++代码

    1. 确定主题和目标受众:在开始写作之前,您需要确定您要写什么样的文章以及您的目标受众是谁。这将有助于您在文章中保持焦点并确保您的内容与受众的兴趣和需求相符。2. 研究和策划:在开始写作之前,您需要进行一些研究和策划。这将有助于您理解您的主题,并收集和组织您的想法和信息。您可以使用大纲或思维导图来帮助您组织您的想法。

    [ 2024-05-16 14:59:12 ]
  • 如何使用C++算法实现快速排序

    快速排序是一种常用的排序算法,其时间复杂度为O(nlogn),比其他排序算法如冒泡排序和插入排序更快。在本文中,我们将介绍如何使用C++算法实现快速排序。快速排序的基本思想是通过分治法将一个大问题分解成小问题,然后递归地解决这些小问题。具体来说,快速排序的实现过程如下:1. 选择一个基准元素,通常选择第一个元素或最后一个元素。

    [ 2024-05-16 13:30:49 ]
  • 面向对象程序设计c++答案

    面向对象程序设计是一种基于对象的编程范式,它将数据和操作封装在一起,通过对象之间的交互来实现程序的功能。C++是一种支持面向对象编程的高级编程语言,它结合了C语言的高效性和面向对象的特性,被广泛应用于软件开发、游戏开发、嵌入式系统等领域。在本文中,我们将探讨面向对象程序设计的基本概念和C++语言的相关特性,以及如何使用C++实现面向对象编程。

    [ 2024-05-16 12:03:16 ]
  • c++缺少函数标题(如何在快节奏的生活中保持心理健康?)

    在当今快节奏的生活中,人们面临着越来越多的压力和挑战。这些压力和挑战可能来自于工作、家庭、社交关系等方面,给人们的身心健康带来了很大的负担。因此,如何在快节奏的生活中保持心理健康成为了一个非常重要的话题。本文将从以下几个方面探讨如何保持心理健康。一、良好的生活习惯

    [ 2024-05-16 03:36:13 ]
  • c和c++区别

    C语言和C++语言是两种非常常见的编程语言,它们都是高级语言,也都是面向过程的编程语言。但是,它们之间还是有很多不同的地方。在本文中,我们将详细介绍C语言和C++语言的区别。1. 语言历史C语言是由Dennis Ritchie在20世纪70年代开发的。它是一种面向过程的编程语言,最初是为Unix操作系统开发的。

    [ 2024-05-16 01:46:00 ]
  • c++缓冲区是什么

    C++缓冲区是计算机内存中的一块区域,用于存储数据。缓冲区可以是硬件缓冲区,也可以是软件缓冲区。在C++中,缓冲区主要用于输入和输出操作。在进行输入和输出操作时,数据通常会被存储在缓冲区中,然后再进行实际的读取或写入操作。C++缓冲区的作用

    [ 2024-05-15 16:06:27 ]
  • c++是什么专业_C++编程语言:从入门到精通

    C++是一种高级编程语言,是C语言的扩展版本。它是一种面向对象的编程语言,具有强大的数据处理能力和高效的运行速度,被广泛应用于软件开发、游戏设计、系统编程、嵌入式设备等领域。本文将从C++的基础知识、语法规则、常用函数库等方面详细介绍C++编程语言,帮助读者从入门到精通。一、C++的基础知识1.1 C++的历史

    [ 2024-05-14 10:21:09 ]
  • c++string用法

    C++中的字符串类型是一个非常常用的数据类型,它可以用来表示任意长度的文本,包括数字、字母、符号等等。字符串类型在C++中是通过一个叫做string的类来实现的,它提供了许多方便的函数和操作符来处理字符串。本文将介绍C++中string类的基本用法和一些实用技巧。1. 字符串的定义和初始化

    [ 2024-05-13 23:15:59 ]
  • 如何利用分布估计算法提高数据分析的准确性

    随着数据科学的发展,数据分析已经成为了各个领域中不可或缺的一部分。然而,数据分析并不是一件简单的事情,因为数据中往往存在着各种各样的误差和噪声。为了提高数据分析的准确性,我们需要采用一些有效的算法来对数据进行处理和分析。其中,分布估计算法是一种非常重要的算法之一。

    [ 2024-05-13 21:09:25 ]
  • 如何在C++中使用数据库函数

    C++是一种强大的编程语言,可以用于开发各种类型的应用程序,包括数据库应用程序。在本文中,我们将介绍如何在C++中使用数据库函数来连接和操作数据库。一、数据库数据库是一个结构化数据集合,可以通过计算机程序进行访问和管理。数据库可以存储和检索大量数据,这些数据可以是文本、数字、图像等等。

    [ 2024-05-13 11:04:07 ]