HBC20319[SDOI2008]红黑树(TREE)题解

冷夕颜 算法基础篇 55 0
挑战自我,勇攀编程高峰!全网最全C++题库,助您成为编程达人。
红黑树是一类特殊的二叉搜索树,其中每个结点被染成红色或黑色,若将二叉搜索树结点中的空指针看作是指向一个空结点,则称这类空结点为二叉搜索树的前端结点,并规定所有前端结点的高度为-1, 一棵红黑树是满足下面“红黑性质”的染色二叉搜索树: (1) 每个结点被染成红色或黑色; (2) 每个前端结点为黑色结点; (3) 任一红结点的子结点均为黑结点; (4) 在从任一结点到

红黑树是一类特殊的二叉搜索树,其中每个结点被染成红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点,则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为-1。  一棵红黑树是满足下面“红黑性质”的染色二叉搜索树: (1) 每个结点被染成红色或黑色; (2) 每个前端结点为黑色结点; (3) 任一红结点的子结点均为黑结点; (4) 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。  从红黑树中任一结点x出发(不包括结点x),到达一个前端结点的任意一条路径上的黑结点个数称为结点x的黑高度,记作bh(x)。红黑树的黑高度定义为其根结点的黑高度。 给定正整数N,试设计一个算法,计算出在所有含有N个结点的红黑树中,红色内结点个数的最小值和最大值。  

HBC20319[SDOI2008]红黑树(TREE)题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
想要在职场中立于不败之地?那就来试试全网最全C++题库,让您在练习中快速提升技能。

标签: HBC20319[SDOI2008]红黑树(TREE)题解