Skip to content

Files

Latest commit

 

History

History
29 lines (17 loc) · 2.13 KB

原理补充.md

File metadata and controls

29 lines (17 loc) · 2.13 KB

完全二叉树

给定索引$i$,其左子节点的索引为$2i + 1$,右子节点的索引为$2i + 2$,父节点的索引为$(i - 1), // ,2$

证明: 二叉树第$k$层的节点数最多为$2^{k-1}$,所以前$k$层最多有$\sum_{n=1}^k 2^{n-1} = 2^k - 1$个节点。

设父节点是第$k$层的第$m$个节点,则其索引为$i = (2^{k - 1} - 1) + m -1 = 2^{k - 1} + m -2$。

若其左子节点存在的话,则必须要走完第$k$层剩下的$2^{k - 1} - m$个节点,且到下一层之后,还得加上左边$m - 1$个父节点留下的左右子节点;所以其左子节点的索引为$i + (2^{k - 1} - m) + 2(m - 1) + 1 = (2^{k - 1} + m -2) + (2^{k - 1} - m) + 2(m - 1) + 1 = 2^k + 2m - 3 = 2(2^{k - 1} + m -2) + 1 = 2i + 1$

所以右子节点的索引为$(2i + 1) + 1 = 2i + 2$,父节点的索引为$(i - 1), // ,2$

AVL 树

插入造成的失衡只需要调整一次;而删除造成的失衡可能需要进行多次调整,必须沿着真正被删除节点的父节点到根节点的路径一路检查并调整。

这本质上是因为再平衡会使得以失衡节点为根节点的子树的树高减$1$,并且子树的新根节点的平衡因子一定会变为$0$。

插入可能使得插入节点到根节点路径上一系列节点的最高子树高度加$1$,从而导致失衡;因为这种子树高度的变化是从下往上传导的,所以只需要将离插入节点最近的失衡节点再平衡即可,该子树的高度减$1$,向上传导后其他失衡节点的最高子树高度依次回到失衡前的状态。 而删除导致的失衡必然是因为删除节点到根节点路径上一系列节点的最低子树高度减$1$,将离删除节点最近的失衡节点再平衡后,该子树的高度减$1$,不但不能保证其他失衡节点的最低子树高度回到失衡前的状态,反而还可能使得其他调整之前平衡的节点由于最低子树高度减$1$而失衡。 所以插入造成的失衡只需要调整一次,而删除造成的失衡必须沿着被删除节点的父节点到根节点的路径一路检查并调整。

证明

dijkstra 算法

floyd 算法

RSA 加密