二叉搜索树中的插入操作

记住「小往左、大往右,走到空位就新建叶子挂上」,下面逐帧套它。新节点一定是作为叶子插入,不会改动已有节点的连接。

二叉搜索树中的插入操作：先看这棵 BST:根 40,左边 20(挂着 10、30)、右边 60(挂着 50、70)。要插入的值是 25,我们从根开始一路比较着往下找它该待的空位。

二叉搜索树中的插入操作：先找感觉:BST 里每个节点左边整棵都比它小、右边整棵都比它大。按叶子插入法,拿 25 和路上的节点一路比较,小就向左、大就向右,这条下行路线就被有序性钉死了,最后会走到一个空孩子。

二叉搜索树中的插入操作：第一拍,当前停在根 40,先把要插入的 25 和 40 比一比,问一句:25 比 40 小吗?

二叉搜索树中的插入操作：答案是成立的,25 确实比 40 小。按「小往左」的规矩,下一步就走进 40 的左子树。

二叉搜索树中的插入操作：顺着左边来到 20,这是第二拍。还是同样动作,把 25 和 20 比一比,问:25 比 20 小吗?

二叉搜索树中的插入操作：这回不成立,25 不比 20 小,反而 25 > 20。那就按「大往右」,下一步走进 20 的右子树。

二叉搜索树中的插入操作：走到 20 的右孩子 30,第三拍。继续比,把 25 和 30 放一起:25 比 30 小吗?

二叉搜索树中的插入操作：成立,25 比 30 小,该往 30 的左边走。可是看一眼 30 的左孩子,它是空的。一路比下来终于撞到了空位,这就是叶子插入法这条下行路线对应的落点。

二叉搜索树中的插入操作：在这个空位新建一个值为 25 的节点,标成绿色,把它接到 30 的左孩子位置。25 作为一片新叶子长了出来,没有动到任何已有节点的连接。

二叉搜索树中的插入操作：插入完成。25 现在是 30 的左孩子,中序遍历变成 10,20,25,30,40,50,60,70,严格升序,整棵树依旧满足「左小右大」,还是一棵合法的 BST,25 正好落在它该在的 20 和 30 之间。

二叉搜索树中的插入操作：回头看 25 这一趟:从 40 到 20 到 30,最后落到 30 左边的空位。规律就一句话,小往左、大往右,走到空位就新建叶子挂上。下面换个值,把这条规律再走一遍。

二叉搜索树中的插入操作：这次要插入的值是 65,我们重新回到根 40。规则一点没变,还是小往左、大往右,看看 65 会走出一条完全不同的路。

二叉搜索树中的插入操作：先停在根 40,把 65 和 40 比一比,问一句:65 比 40 小吗?

二叉搜索树中的插入操作：不成立,65 不比 40 小,反而 65 > 40。按「大往右」,下一步走进 40 的右子树,和刚才 25 往左正好相反。

二叉搜索树中的插入操作：顺着右边来到 60。继续比,65 > 60,还是比它大,继续往右,走进 60 的右子树。

二叉搜索树中的插入操作：走到 60 的右孩子 70。再比一次,这回问:65 比 70 小吗?

二叉搜索树中的插入操作：成立,65 比 70 小,该往 70 的左边走。看一眼 70 的左孩子,又是空的。空位找到了,65 就该挂在这里。

二叉搜索树中的插入操作：在 70 的左孩子位置新建一个值为 65 的节点,标绿挂上。65 同样是作为一片新叶子长出来的,没有动任何已有连接。

二叉搜索树中的插入操作：两次插入都完成了。现在中序遍历是 10,20,25,30,40,50,60,65,70,依旧严格升序,25 和 65 各自落在自己该在的位置,整棵树仍是合法 BST。

二叉搜索树中的插入操作：回头看这两趟:25 走的是左半边、65 走的是右半边,可用的规则一模一样。从根出发,val 比当前小就往左、比当前大就往右,一路下行直到某一侧是空,就在那个空位新建叶子挂上。BST 的有序性钉死了这条下行路线,一趟 O(h) 就插好了。

边界:空树则新建根;极小值挂最左、极大值挂最右。

两个追问:题目允许任意合法 BST,叶子插入法落点固定;可改迭代做到 O(1) 空间。