c++写一个红黑树代码

小咪咪 2024-03-27 12:10 34阅读 0赞

这是一段红黑树的 C 代码的例子：

\`\`\` \#include <stdio.h> \#include <stdlib.h>

// 定义红黑树的节点 typedef struct rbtree\_node \{ int val; char color; struct rbtree\_node \*left, \*right, \*parent; \} node;

// 定义红黑树 typedef struct rbtree \{ node \*root; \} rbtree;

// 创建新节点 node \*create\_node(int val, char color, node \*left, node \*right, node \*parent) \{ node *new\_node = (node*) malloc(sizeof(node)); new\_node->val = val; new\_node->color = color; new\_node->left = left; new\_node->right = right; new\_node->parent = parent; return new\_node; \}

// 左旋转 void rotate\_left(rbtree \*tree, node \*x) \{ node \*y = x->right; x->right = y->left; if (y->left != NULL) y->left->parent = x; y->parent = x->parent; if (x->parent == NULL) \{ tree->root = y; \} else if (x == x->parent->left) \{ x->parent->left = y; \} else \{ x->parent->right = y; \} y->left = x; x->parent = y; \}

// 右旋转 void rotate\_right(rbtree \*tree, node \*x) \{ node \*y = x->left; x->left = y->right; if (y->right != NULL) y->right->parent = x; y->parent = x->parent; if (x->parent == NULL) \{ tree->root = y; \} else if (x == x->parent->right) \{ x->parent->right = y; \} else \{ x->parent->left = y; \} y->right = x; x->parent = y; \}

// 向红黑树中插入新节点 void insert(rbtree \*tree, int val) \{ node \*new\_node = create\_node(val, 'R', NULL, NULL, NULL); node \*temp = tree->root; if (temp == NULL) \{ tree->root = new\_node; \} else \{ while (1) \{ if (val < temp->val) \{ if (temp->left == NULL) \{ temp->left = new\_node; new\_node->parent = temp; break; \} else \{ temp = temp->left; \} \} else if (val > temp->val)

发表评论取消回复

表情：

评论列表（有 0 条评论，34人围观）

还没有评论，来说两句吧...

相关阅读

相关【C++】红黑树

红黑树的模拟实现

朴灿烈づ我的快乐病毒、/ 2024年04月27日 07:33/ 0 赞/ 34 阅读

相关【C++】红黑树

他来了他来了，红黑树他真来了！！

以你之姓@/ 2024年04月26日 11:03/ 0 赞/ 36 阅读

相关 c++写一个红黑树代码

这是一段红黑树的 C 代码的例子： \`\`\` \include <stdio.h> \include <stdlib.h> // 定义红黑树的节点 typedef st

小咪咪/ 2024年03月27日 12:10/ 0 赞/ 35 阅读

相关 java 红黑树代码

java 红黑树是一种二叉搜索树，其中的每个节点都具有颜色属性，要么是红色，要么是黑色。红黑树的节点颜色可以是"红色"或"黑色"。这种树遵循以下几条规则： 1. 每个节点要

￡神魔★判官ぃ/ 2024年03月25日 18:52/ 0 赞/ 27 阅读

相关树：红黑树

1，红黑树引入红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1，超过后需要进行左旋或者右旋操作再次对树进行平衡，虽然这样能够解决二叉树退化为链表的缺

╰半橙微兮°/ 2023年02月28日 01:25/ 0 赞/ 92 阅读

相关红黑树——C/C++

红黑树由于红黑树本质上就是一棵二叉查找树，所以在了解红黑树之前，咱们先来看下二叉查找树。 1. 二叉查找树二叉查找树（Binary Search Tree），

刺骨的言语ヽ痛彻心扉/ 2022年12月19日 13:28/ 0 赞/ 129 阅读

相关手写红黑树

手写红黑树辅助方法定义左旋方法定义：leftRotate(node) 右旋方法定义：rightRotate(node) 公开插入接口方法定义：

谁借莪１个温暖的怀抱￠/ 2022年12月17日 08:46/ 0 赞/ 64 阅读

相关红黑树java代码记录

2020-10-08目前代码只记录了插入过程和插入之后的恢复过程代码，删除过程代码还在整理. package com.lsx.tree; publi

不念不忘少年蓝@/ 2022年12月13日 01:21/ 0 赞/ 36 阅读

相关 C++ 红黑树

ifndef WRAPPER_H define WRAPPER_H include "Except.h" template<class Objc

淩亂°似流年/ 2022年08月20日 12:16/ 0 赞/ 149 阅读

相关 C++实现红黑树

一、概念红黑树是一棵二叉搜索树，它和AVL树的区别就是，红黑树没有平衡因子，而是在每个结点上增加了一个存储位来表示结点的颜色，可以是red或者black，通过对任何一条

傷城~/ 2022年06月01日 11:10/ 0 赞/ 173 阅读