赞
踩
叶节点:没有孩子的节点称为叶节点(Leaf Node)
内节点:有孩子的节点则称为内节点(Internal Node)
BST:二叉查找树(Binary Search Tree)
对于任意一个节点 n,
- 其左子树(left subtree)下的每个后代节点(descendant node)的值都小于节点 n 的值;
- 其右子树(right subtree)下的每个后代节点的值都大于节点 n 的值。
如图所示:(a)不是,(b)是
从 BST 的根节点开始。算法不断地比较节点值的大小直到找到该节点,或者判定不存在。每一步我们都要处理两个节点:树中的一个节点,称为节点 c,和要查找的节点 n,然后并比较 c 和 n 的值。开始时,节点 c 为 BST 的根节点。然后执行以下步骤:
当向树中插入一个新的节点时,该节点将总是作为叶子节点。所以,最困难的地方就是如何找到该节点的父节点。类似于查找算法中的描述,我们将这个新的节点称为节点 n,而遍历的当前节点称为节点 c。开始时,节点 c 为 BST 的根节点。则定位节点 n 父节点的步骤如下:
// 可通过leetcode上的题目练习:二叉搜索树中的插入操作 // 地址:https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/ // 这边用的是递归法,迭代法也可以实现,空间复杂度会低点 public TreeNode insertIntoBST(TreeNode root, int val) { // 先排出极端情况,root为null if (root == null) { return new TreeNode(val); } traverse(root, val); return root; } public void traverse(TreeNode ptr, int val) { if (ptr.val > val){ // 插入到左子树 if (ptr.left == null){ //如果此时左子树为空,直接放入左端即可 ptr.left = new TreeNode(val); return; } else {//否则当前root的左子树 traverse(ptr.left, val); } } else { // 插入到右子树 if (ptr.right == null){ //如果此时右子树为空,直接放入右端即可 ptr.right = new TreeNode(val); return; } else { traverse(ptr.right, val); } } }
从 BST 中删除节点比插入节点难度更大。因为删除一个非叶子节点,就必须选择其他节点来填补因删除节点所造成的树的断裂。如果不选择节点来填补这个断裂,那么就违背了 BST 的性质要求。 删除节点算法的第一步是定位要被删除的节点,这可以使用前面介绍的查找算法,因此运行时间为 O(log2n)。接着应该选择合适的节点来代替删除节点的位置,它共有三种情况需要考虑。
情况 1:如果删除的节点没有右孩子,那么就选择它的左孩子来代替原来的节点。二叉查找树的性质保证了被删除节点的左子树必然符合二叉查找树的性质。因此左子树的值要么都大于,要么都小于被删除节点的父节点的值,这取决于被删除节点是左孩子还是右孩子。因此用被删除节点的左子树来替代被删除节点,是完全符合二叉搜索树的性质的。
情况 2:如果被删除节点的右孩子没有左孩子,那么这个右孩子被用来替换被删除节点。因为被删除节点的右孩子都大于被删除节点左子树的所有节点,同时也大于或小于被删除节点的父节点,这同样取决于被删除节点是左孩子还是右孩子。因此,用右孩子来替换被删除节点,符合二叉查找树的性质。
情况 3:如果被删除节点的右孩子有左孩子,就需要用被删除节点右孩子的左子树中的最下面的节点来替换它,就是说,我们用被删除节点的右子树中最小值的节点来替换。
这边不多赘述,这跟二叉树的遍历是一样的:前中后序遍历,可以看我数据结构专栏的解释
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。