红黑树
发布日期:2021-11-04 22:04:20
浏览次数:7
分类:技术文章
本文共 983 字,大约阅读时间需要 3 分钟。
红黑树的性质:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
在根据算法导论可以得出一些算法的c++实现:(部分程序)
#include<iostream>
using namespace std; #include"RB_TREE.h" class RB_Tree{ private : TreeNode1 * root; TreeNode1 * findPos(int val){ TreeNode1* t = root; TreeNode1*pre = root; while (t != nill){ if (t->value == val)return t; pre = t; if (t->value < val) t = t->right; else t = t->left; } return pre; } void RB_left_rotate(TreeNode1* t){ TreeNode1* y = t->right; t->right = y->left; if (y->left != nill){ y->left->p = t; } y->p = t->p; if (t->p == nill){ root = y; }else if(t == t->p->left){ t->p->left = y; } else{ t->p->right = y; } y->left = t; t->p = y; } void RB_right_rotate(TreeNode1* t){ TreeNode1* y = t->left; t->left = y->right; if (y->right != nill){ y->right->p = t; } y->p = t->p; if (t->p == nill){ root = y; } else if (t == t->p->right){ t->p->right = y; } else{ t->p->left = y; } y->right = t; t->p = y; }转载地址:https://blog.csdn.net/xiaochen87654321/article/details/51213792 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年05月04日 17时01分58秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
守护线程与主线程等待子线程
2019-05-01
线程中的全局变量与抢占资源
2019-05-01
python中 global的使用
2019-05-01
多线程函数的传参
2019-05-01
多态和鸭子类型
2019-05-01
python 实现 抽象基类 abc模块
2019-05-01
python type和 isinstance is and ==
2019-05-01
多继承 查看继承顺序的‘__mro__’魔法方法
2019-05-01
python 多线程 互斥锁和死锁
2019-05-01
python实现死锁和重入锁
2019-05-01
线程同步
2019-05-01
进程和多进程实现多任务
2019-05-01
python模块os.getpid 和os.getppid在多进程中的应用
2019-05-01
python 实现多线程UDP聊天器
2019-05-01
多进程之间共享全局变量 python实现
2019-05-01
进程方法 run和start的区别
2019-05-01
python 多进程之进程池的操作
2019-05-01
进程池之间通信 python 实现
2019-05-01
基于进程池实现文件拷贝
2019-05-01
作最好的自己
2019-05-01