查找¶

查找的基本概念¶

我的理解是把高的向上提，减少高度

1. 深度为 \(h\) 的平衡二叉树的最少结点数 \(N_h\) 的递推公式为：

红黑树中的叶子结点不是真实有数据的结点

性质1如何理解？

因为红黑树每条路上的黑结点个数是一定的，所以最短路径就一定是全黑的，那么最长就是往黑结点中间插红结点，同时根节点下也能插一个，所以整条路经长度就是黑结点个数×2。

每次插入若不是根节点，如果破坏了规则，那么一定是必定破坏不红红

对于给定数量的不同结点构造二叉查找树（Binary Search Tree, BST），其能构造出的树的形态数量仅取决于结点的个数，而与结点的具体数值无关。
这是因为：只要二叉树的形态（骨架）固定下来，把 \(n\) 个不同的数填进去并满足“左子树 < 根 < 右子树”的二叉查找树性质，只有唯一的一种填法。因此，“\(n\) 个不同结点构造二叉查找树的形态数”等价于“\(n\) 个结点能构成多少种不同的二叉树形态”。
卡特兰数：\[C_n = \frac{1}{n+1} \binom{2n}{n}\]
题目中指出有 5 个不同的结点，所以令 \(n = 5\)，代入公式：

\[C_5 = \frac{1}{5+1} \binom{2 \times 5}{5} = \frac{1}{6} \binom{10}{5}\]

接下来我们计算组合数 \(\binom{10}{5}\) 的值：

\[\binom{10}{5} = \frac{10 \times 9 \times 8 \times 7 \times 6}{5 \times 4 \times 3 \times 2 \times 1} = 252\]

最后将结果代回原式得出最终答案：

\[C_5 = \frac{252}{6} = 42\]
非空二叉排序树T1删除某结点v后形成二叉排序树T2，再将v插入T2形成二叉排序树T3
若v是T1叶结点，则T1 == T3；若v不是T1叶结点，则T1 !=T3