广东华电建设股份有限公司网站,做一个微信小程序要多少钱,自己做竞猜网站挣钱吗,中国建设网上银行个人登录目录
二叉树
1. 二叉树的定义
2. 二叉树的遍历
3. 二叉树的应用
4. 实现细节
5. C中的实现
面试准备
红黑树
红黑树的原理
红黑树的用途
示例代码
面试准备
1. 红黑树的工作原理及其规则
2. 红黑树的优势及与其他二叉搜索树#xff08;如AVL树#xff09;的比较…目录
二叉树
1. 二叉树的定义
2. 二叉树的遍历
3. 二叉树的应用
4. 实现细节
5. C中的实现
面试准备
红黑树
红黑树的原理
红黑树的用途
示例代码
面试准备
1. 红黑树的工作原理及其规则
2. 红黑树的优势及与其他二叉搜索树如AVL树的比较
3. 红黑树操作的时间复杂度
4. 红黑树的基本操作编写代码
代码
红黑树节点定义和基本结构
辅助函数实现
插入操作和违规修正
遍历函数
测试用例 二叉树
1. 二叉树的定义
基本概念二叉树是一种树形结构其中每个节点最多有两个子节点分别称为“左子节点”和“右子节点”。特殊类型 完全二叉树除了最后一层外每一层都被完全填满且所有节点都尽可能地向左对齐。满二叉树所有非叶子节点都有两个子节点所有叶子节点都在同一层级。平衡二叉树AVL树任何节点的两个子树的高度差不超过1。
2. 二叉树的遍历
前序遍历根-左-右先访问根节点然后递归地对左子树进行前序遍历最后对右子树进行前序遍历。中序遍历左-根-右先递归地对左子树进行中序遍历然后访问根节点最后对右子树进行中序遍历。后序遍历左-右-根先递归地对左子树进行后序遍历然后对右子树进行后序遍历最后访问根节点。层次遍历广度优先遍历按照树的层次从上到下从左到右遍历所有节点。
3. 二叉树的应用
二叉搜索树BST一种特殊的二叉树其中每个节点的值都大于其左子树上任何节点的值且小于其右子树上任何节点的值。堆特殊的完全二叉树用于实现优先队列。哈夫曼编码树用于数据压缩的二叉树。
4. 实现细节
节点结构通常包含数据部分和指向左、右子节点的指针。操作函数包括创建、遍历递归或迭代、插入、删除、查找等。
5. C中的实现 在C中二叉树可以通过结构体或类来实现。例如 struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};面试准备
理解不同遍历方法的应用场景。熟练实现二叉树的基本操作如插入、删除、查找等。解决实际问题例如如何在二叉搜索树中找到第K小的元素如何判断一棵树是否为平衡二叉树等。掌握递归和非递归遍历方法以及它们的时间和空间复杂度。
红黑树
红黑树的原理 红黑树的关键特性是保持树的平衡这通过以下规则实现
节点颜色每个节点被涂成红色或黑色。根节点规则根节点总是黑色的。红色节点规则红色节点的子节点必须是黑色的即不允许有连续的红色节点。黑色高度规则从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。新插入节点规则新插入的节点是红色的。 通过这些规则红黑树保持大致的平衡从而在插入、删除和查找操作中提供接近O(log n)的最坏情况时间复杂度。
红黑树的用途
红黑树在许多高级数据结构中都有应用如
关联数组在诸如C STL中的map和set中被用作底层结构。 在C的标准模板库STL中map和set通常是基于红黑树实现的。这些数据结构提供了高效的查找、插入和删除操作。 map
#include iostream
#include map
using namespace std;int main() {mapint, string exampleMap;// 插入键值对exampleMap[1] Tencent;exampleMap[2] Alibaba;exampleMap[3] ByteDance;// 遍历mapfor (auto pair : exampleMap) {cout pair.first pair.second endl;}return 0;
}set
#include iostream
#include set
using namespace std;int main() {setint exampleSet;// 插入元素exampleSet.insert(10);exampleSet.insert(30);exampleSet.insert(20);exampleSet.insert(5);// 遍历setfor (int element : exampleSet) {cout element endl;}return 0;
}优先队列可以构建以支持快速的元素插入和删除。 虽然C STL中的priority_queue通常是基于二叉堆实现的红黑树也可以用来实现一个功能类似的结构支持快速元素插入和删除。 注意这里提供的是一个简化的示例仅用于演示概念。
#include iostream
#include set
using namespace std;class PriorityQueue {setint pq;public:void insert(int value) {pq.insert(value);}int top() {if (!pq.empty())return *pq.begin();return -1; // 或抛出异常}void pop() {if (!pq.empty())pq.erase(pq.begin());}bool isEmpty() {return pq.empty();}
};int main() {PriorityQueue pq;pq.insert(10);pq.insert(5);pq.insert(20);while (!pq.isEmpty()) {cout pq.top() endl;pq.pop();}return 0;
}CPU调度系统用于维护任务的优先级队列。 在CPU调度系统中红黑树可以用来维护一个任务的优先级队列。以下示例展示了一个简化的任务调度系统其中任务按优先级排序。
#include iostream
#include set
using namespace std;struct Task {int priority;string taskName;bool operator(const Task t) const {return priority t.priority;}
};int main() {setTask schedule;// 添加任务schedule.insert({1, Task A});schedule.insert({3, Task C});schedule.insert({2, Task B});// 按优先级执行任务for (const auto task : schedule) {cout 执行任务: task.taskName (优先级: task.priority ) endl;}return 0;
}示例代码 以下是C中红黑树节点的基本结构示例
enum Color { RED, BLACK };struct Node {int data;bool color;Node *left, *right, *parent;// ConstructorNode(int data) : data(data) {parent left right nullptr;color RED;}
};class RedBlackTree {
private:Node *root;protected:void rotateLeft(Node *, Node *);void rotateRight(Node *, Node *);void fixViolation(Node *, Node *);public:RedBlackTree() { root nullptr; }void insert(const int n);// ... 其他函数例如遍历和删除
};在这个结构中每个节点都有一个数据值、一个颜色标记红色或黑色、指向左子节点、右子节点和父节点的指针。红黑树类包含用于维护树平衡的旋转和修复函数。 这只是一个非常简化的示例红黑树的完整实现需要包括详细的插入、删除和平衡调整逻辑。
面试准备
在面试中你可能需要
解释红黑树的工作原理及其各个规则。讨论红黑树的优势及其与其他二叉搜索树如AVL树的区别。分析红黑树操作的时间复杂度。可能需要对红黑树的基本操作编写代码特别是插入和删除。
1. 红黑树的工作原理及其规则
红黑树是一种自平衡二叉搜索树它通过以下规则确保高效的操作时间复杂度主要是插入和删除
节点颜色每个节点要么是红色要么是黑色。根节点根节点总是黑色的。红色节点规则红色节点的两个子节点都是黑色的即红色节点不相邻。每个节点到叶子节点的路径上黑色节点的数量相同从任一节点到其每个叶子节点的所有路径上的黑色节点数目相同。新插入节点为红色新插入的节点是红色的除非它是根节点。
2. 红黑树的优势及与其他二叉搜索树如AVL树的比较
红黑树的主要优势在于它提供了一种平衡插入、删除和查找操作的高效方式。与AVL树相比红黑树在插入和删除操作中更加高效因为它们需要更少的重新平衡操作。
插入和删除红黑树在插入和删除操作时通常只需要O(log n)时间并且不需要像AVL树那样频繁的旋转来维持平衡。查找操作AVL树由于是更加严格平衡的对于查找密集型应用可能稍微优于红黑树。
3. 红黑树操作的时间复杂度
红黑树的所有基本操作插入、删除、查找的时间复杂度都是O(log n)。由于树是大致平衡的所以这些操作的最坏情况性能也是很好的。
查找由于红黑树是二叉搜索树查找操作的时间复杂度为O(log n)。插入和删除尽管插入和删除可能需要额外的颜色更改和旋转来保持红黑树的性质但这些操作的时间复杂度依然是O(log n)。
4. 红黑树的基本操作编写代码
编写红黑树的代码需要注意其性质的维持。插入和删除操作特别复杂因为它们可能会破坏红黑树的性质所以需要通过旋转和重新着色来修复。由于代码实现较长我之前的回答已经提供了插入操作的一个示例。删除操作的代码更加复杂但基本思路是在删除节点后通过一系列的旋转和颜色更改来保持树的平衡和性质。
代码
红黑树节点定义和基本结构 首先定义红黑树的节点结构和基本的红黑树类 #include iostream
using namespace std;enum Color { RED, BLACK };struct Node {int data;bool color;Node *left, *right, *parent;Node(int data) : data(data) {parent left right nullptr;color RED;}
};class RedBlackTree {
private:Node *root;protected:void rotateLeft(Node *root, Node *pt);void rotateRight(Node *root, Node *pt);void fixViolation(Node *root, Node *pt);public:RedBlackTree() { root nullptr; }void insert(const int n);void inorder();void levelOrder();
};辅助函数实现 接下来实现旋转和修正违规的辅助函数
void RedBlackTree::rotateLeft(Node *root, Node *pt) {Node *pt_right pt-right;pt-right pt_right-left;if (pt-right ! nullptr)pt-right-parent pt;pt_right-parent pt-parent;if (pt-parent nullptr)root pt_right;else if (pt pt-parent-left)pt-parent-left pt_right;elsept-parent-right pt_right;pt_right-left pt;pt-parent pt_right;
}void RedBlackTree::rotateRight(Node *root, Node *pt) {Node *pt_left pt-left;pt-left pt_left-right;if (pt-left ! nullptr)pt-left-parent pt;pt_left-parent pt-parent;if (pt-parent nullptr)root pt_left;else if (pt pt-parent-right)pt-parent-right pt_left;elsept-parent-left pt_left;pt_left-right pt;pt-parent pt_left;
}插入操作和违规修正 插入操作和违规修正是红黑树最核心的部分
void RedBlackTree::fixViolation(Node *root, Node *pt) {Node *parent_pt nullptr;Node *grand_parent_pt nullptr;while ((pt ! root) (pt-color ! BLACK) (pt-parent-color RED)) {parent_pt pt-parent;grand_parent_pt pt-parent-parent;/* Case : AParent of pt is left child of Grand-parent of pt */if (parent_pt grand_parent_pt-left) {Node *uncle_pt grand_parent_pt-right;/* Case : 1The uncle of pt is also redOnly Recoloring required */if (uncle_pt ! nullptr uncle_pt-color RED) {grand_parent_pt-color RED;parent_pt-color BLACK;uncle_pt-color BLACK;pt grand_parent_pt;} else {/* Case : 2pt is right child of its parentLeft-rotation required */if (pt parent_pt-right) {rotateLeft(root, parent_pt);pt parent_pt;parent_pt pt-parent;}/* Case : 3pt is left child of its parentRight-rotation required */rotateRight(root, grand_parent_pt);swap(parent_pt-color, grand_parent_pt-color);pt parent_pt;}}/* Case : BParent of pt is right child of Grand-parent of pt */else {Node *uncle_pt grand_parent_pt-left;/* Case : 1The uncle of pt is also redOnly Recoloring required */if ((uncle_pt ! nullptr) (uncle_pt-color RED)) {grand_parent_pt-color RED;parent_pt-color BLACK;uncle_pt-color BLACK;pt grand_parent_pt;} else {/* Case : 2pt is left child of its parentRight-rotation required */if (pt parent_pt-left) {rotateRight(root, parent_pt);pt parent_pt;parent_pt pt-parent;}/* Case : 3pt is right child of its parentLeft-rotation required */rotateLeft(root, grand_parent_pt);swap(parent_pt-color, grand_parent_pt-color);pt parent_pt;}}}root-color BLACK;
}void RedBlackTree::insert(const int data) {Node *pt new Node(data);// Do a normal BST insertroot BSTInsert(root, pt);// fix Red Black Tree violationsfixViolation(root, pt);
}Node* BSTInsert(Node* root, Node* pt) {/* If the tree is empty, return a new node */if (root nullptr)return pt;/* Otherwise, recur down the tree */if (pt-data root-data) {root-left BSTInsert(root-left, pt);root-left-parent root;} else if (pt-data root-data) {root-right BSTInsert(root-right, pt);root-right-parent root;}/* return the (unchanged) node pointer */return root;
}遍历函数 遍历函数用于验证树的结构
void inorderHelper(Node *root) {if (root nullptr)return;inorderHelper(root-left);cout root-data ;inorderHelper(root-right);
}void RedBlackTree::inorder() { inorderHelper(root); }void levelOrderHelper(Node *root) {if (root nullptr)return;std::queueNode * q;q.push(root);while (!q.empty()) {Node *temp q.front();cout temp-data ;q.pop();if (temp-left ! nullptr)q.push(temp-left);if (temp-right ! nullptr)q.push(temp-right);}
}void RedBlackTree::levelOrder() { levelOrderHelper(root); }测试用例 最后定义一些测试用例以验证红黑树的功能
int main() {RedBlackTree tree;tree.insert(7);tree.insert(6);tree.insert(5);tree.insert(4);tree.insert(3);tree.insert(2);tree.insert(1);cout Inorder Traversal of Created Tree\n;tree.inorder();cout \n\nLevel Order Traversal of Created Tree\n;tree.levelOrder();return 0;
}
