When we delete a node, there possibilities arise.
1) Node to be deleted is leaf: Simply remove from the tree.
50 50 / \ delete(20) / \ 30 70 ---------> 30 70 / \ / \ \ / \ 20 40 60 80 40 60 80
2) Node to be deleted has only one child: Copy the child to the node and delete the child
50 50 / \ delete(30) / \ 30 70 ---------> 40 70 \ / \ / \ 40 60 80 60 80
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
50 60 / \ delete(50) / \ 40 70 ---------> 40 70 / \ \ 60 80 80
The important thing to note is, inorder successor is needed only when right child is not empty. In this particular case, inorder successor can be obtained by finding the minimum value in right child of the node.
/* Given a binary search tree and a key, this function deletes the key and returns the new root */ public TreeNode deleteBSTNode(TreeNode root, int target) { // base case if(root == null) return null; // If the key to be deleted is smaller than the root's key, // then it lies in left subtree if(target < root.val) { root.left = deleteBSTNode(root.left, target); // If the key to be deleted is greater than the root's key, // then it lies in right subtree } else if(target > root.val){ root.right = deleteBSTNode(root.right, target); // if key is same as root's key, then This is the node // to be deleted } else { if(root.left == null) return root.right; if(root.right == null) return root.left; // Get the in-order successor (smallest in the right subtree) // and delete it from the subtree TreeNode successor = root.right; while(successor.left != null) { successor = successor.left; } // Copy the in-order successor's content to this node root.val = successor.val; // Delete the in-order successor root.right = deleteBSTNode(root.right, successor.val); } return root; }
Reference:
http://algs4.cs.princeton.edu/32bst/BST.java.html
http://geeksquiz.com/binary-search-tree-set-2-delete/
相关推荐
A application about binary search tree, Insert, Delete, Find, Print node.
实施方法#build_tree方法,该方法获取数据数组(例如[1、7、4、23、8、9、4、3、5、7、9、67、6345、324])并将其转换为平衡的二叉树充分放置了适当放置的Node对象(排序和唯一元素)。 #build_tree方法返回1级根...
Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate Reverse Polish Notation #169 Majority Element #171 Excel Sheet ...
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
Splitting a page when full is simple and does not require a tree traversal for node overflow checking as in a b+tree. Main page list updates are infrequent and hence the locking of the main page list...
0-binary_tree_node.c 创建一个二叉树节点 1-binary_tree_insert_left.c 插入一个节点作为另一个节点的左子节点 2-binary_tree_insert_right.c 插入一个节点作为另一个节点的右子节点 3-binary_tree_delete.c ...
infile0.open("hfmTree.dat",ios::binary|ios::in); if(infile0.fail()) { cout文件打开失败!\n"; return; } infile0.read((char*)&T.LeafNum,sizeof(T.LeafNum)); //读取叶子数 T.Info=new char[T....
Fixed problem with NodeAdd from another tree (Document reference gets updated now) ! Fixed deletion of empty attributes Version 2.36 (11Nov2007) ! Do not save empty encoding (e.g. encoding=""). * ...
①平衡二叉树(Balanced Binary Tree)是指树中任一结点的左右子树的高度大致相同。 ②任一结点的左右子树的高度均相同(如满二叉树),则二叉树是完全平衡的。通常,只要二叉树的高度为O(1gn),就可看作是平衡的。 ...
(ADDRESS=(PROTOCOL=decnet)(OBJECT=outa)(NODE=zeus)) 此参数在 8.1.3 版中已废弃。 值范围: TRUE | FALSE 默认值: FALSE mts_servers: 说明 : 指定在启动例程后, 要为共享服务器环境创建的服务器进程的数量。 值...