Remove Node from Binary Search Tree
I am working on Binary Search Tree for the first time and trying to remove a node from the Binary Search Tree.
However, everytime I remove it and then I use inOrder()
or preOrder()
to check if it's removed or not, it still shows up, which means I fail to remove that particular node.
This is my code:
public class BinaryTree<T extends Comparable<T>> {
TreeNode<T> root;
ArrayList<Integer> myArr = new ArrayList<Integer>();
Random random;
}
public void add(T o) {
if (root == null) {
root = new TreeNode<T>(o);
} else {
root.insert(o);
}
}
public TreeNode<T> deleteNode(TreeNode<T> root, int value) {
if (root == null)
return null;
if (root.data > value) {
root.left = deleteNode(root.left, value);
} else if (root.data < value) {
root.right = deleteNode(root.right, value);
} else {
// if nodeToBeDeleted have both children
if (root.left != null && root.right != null) {
TreeNode<T> temp = root;
// Finding minimum element from right
TreeNode<T> minNodeForRight = minimumElement(temp.right);
// Replacing current node with minimum node from right subtree
root.data = minNodeForRight.data;
// Deleting minimum node from right now
deleteNode(root.right, minNodeForRight.data);
}
// if nodeToBeDeleted has only left child
else if (root.left != null) {
root = root.left;
}
// if nodeToBeDeleted has only right child
else if (root.right != null) {
root = root.right;
}
// if nodeToBeDeleted do not have child (Leaf node)
else
root = null;
}
return root;
}
public TreeNode<T> minimumElement(TreeNode<T> root) {
if (root.left == null){
return root;
} else {
return minimumElement(root.left);
}
}
public static void main(String[] args){
BinaryTree<Integer> bst = new BinaryTree<Integer>();
bst.add(20);
bst.add(30);
bst.add(40);
bst.add(80);
bst.add(1200);
bst.inOrder();
bst.deleteNode(bst.root, 80);
bst.inOrder();
}
How to solve this problem?
1 answer
-
answered 2018-11-08 06:09
efex09
Change following line
// Deleting minimum node from right now deleteNode(root.right, minNodeForRight.data);
To
// Deleting minimum node from right now root.right = deleteNode(root.right, minNodeForRight.data);
See also questions close to this topic
-
Multiple JOIN with JPA
I have 3 entity Group with Student (1 - ∞) and Ratings in Students (1 - ∞)
Group@Entity @Table(name = "`group`") public class Group implements Serializable { @OneToMany(fetch = FetchType.EAGER) @JoinColumn(name = "id_group") private List<Student> students; }
Student
@Entity @Table(name = "student") public class Student implements Serializable { @OneToMany(cascade = CascadeType.ALL,fetch = FetchType.EAGER) @JoinColumn(name = "id_student") public List<Rating> ratings; @Temporal(TemporalType.DATE) @Column private Date date; @ManyToOne @JoinColumn(name = "id_student") public Student student; }
My goal is to select all grop by id with students with student ratings between 2 dates. Solutions that I tried
@Query(value = "select g from Group g INNER JOIN g.students s ON g.id = :id INNER JOIN s.ratings r ON r.student.id = s.id and r.date between :dateStart and :dateEnd GROUP BY g.id") @Query(value = "SELECT * FROM Group g INNER JOIN student ON g.id_group = :id RIGHT JOIN rating on student.id_student = rating.id_student and rating.`date` between :dateStart and :dateEnd GROUP BY g.id_group",nativeQuery = true) @Query(value = "select g from Group g WHERE g.id = :id and g.students IN (select s from g.students s JOIN s.ratings r where r.date between :dateStart and :dateEnd) GROUP BY g.id")
-
can I use an Ignite CPP with Ignite Java nodes?
I have been executed 2 Java Ignite Nodes.
and i execute one CPP Ignite Node. but this didn't work.
[10:26:56] Configured failure handler: [hnd=StopNodeOrHaltFailureHandler [tryStop=false, timeout=0, super=AbstractFailureHandler [ignoredFailureTypes=UnmodifiableSet [SYSTEM_WORKER_BLOCKED, SYSTEM_CRITICAL_OPERATION_TIMEOUT]]]] [10:26:56] Message queue limit is set to 0 which may lead to potential OOMEs when running cache operations in FULL_ASYNC or PRIMARY_SYNC modes due to message queues growth on sender and receiver sides. [10:26:56] Security status [authentication=off, tls/ssl=off] [10:26:56,669][SEVERE][main][IgniteKernal] Failed to start manager: GridManagerAdapter [enabled=true, name=o.a.i.i.managers.discovery.GridDiscoveryManager] class org.apache.ignite.IgniteCheckedException: Failed to start SPI: TcpDiscoverySpi [addrRslvr=null, sockTimeout=-300, ackTimeout=5000, marsh=JdkMarshaller [clsFilter=org.apache.ignite.marshaller.MarshallerUtils$1@6a66a204], reconCnt=10, reconDelay=2000, maxAckTimeout=600000, soLinger=5, forceSrvMode=false, clientReconnectDisabled=false, internalLsnr=null, skipAddrsRandomization=false] at org.apache.ignite.internal.managers.GridManagerAdapter.startSpi(GridManagerAdapter.java:300) at org.apache.ignite.internal.managers.discovery.GridDiscoveryManager.start(GridDiscoveryManager.java:940) at org.apache.ignite.internal.IgniteKernal.startManager(IgniteKernal.java:1736) at org.apache.ignite.internal.IgniteKernal.start(IgniteKernal.java:1080) at org.apache.ignite.internal.IgnitionEx$IgniteNamedInstance.start0(IgnitionEx.java:1992) at org.apache.ignite.internal.IgnitionEx$IgniteNamedInstance.start(IgnitionEx.java:1683) at org.apache.ignite.internal.IgnitionEx.start0(IgnitionEx.java:1109) at org.apache.ignite.internal.IgnitionEx.start(IgnitionEx.java:607) at org.apache.ignite.internal.processors.platform.PlatformAbstractBootstrap.start(PlatformAbstractBootstrap.java:43) at org.apache.ignite.internal.processors.platform.PlatformIgnition.start(PlatformIgnition.java:74) Caused by: class org.apache.ignite.spi.IgniteSpiException: SPI parameter failed condition check: sockTimeout > 0 at org.apache.ignite.spi.IgniteSpiAdapter.assertParameter(IgniteSpiAdapter.java:330) at org.apache.ignite.spi.discovery.tcp.TcpDiscoverySpi.initializeImpl(TcpDiscoverySpi.java:2101) at org.apache.ignite.spi.discovery.tcp.TcpDiscoverySpi.spiStart(TcpDiscoverySpi.java:2061) at org.apache.ignite.internal.managers.GridManagerAdapter.startSpi(GridManagerAdapter.java:297) ... 9 more [10:26:56,670][SEVERE][main][IgniteKernal] Got exception while starting (will rollback startup routine). class org.apache.ignite.IgniteCheckedException: Failed to start manager: GridManagerAdapter [enabled=true, name=org.apache.ignite.internal.managers.discovery.GridDiscoveryManager] at org.apache.ignite.internal.IgniteKernal.startManager(IgniteKernal.java:1741) at org.apache.ignite.internal.IgniteKernal.start(IgniteKernal.java:1080) at org.apache.ignite.internal.IgnitionEx$IgniteNamedInstance.start0(IgnitionEx.java:1992) at org.apache.ignite.internal.IgnitionEx$IgniteNamedInstance.start(IgnitionEx.java:1683) at org.apache.ignite.internal.IgnitionEx.start0(IgnitionEx.java:1109) at org.apache.ignite.internal.IgnitionEx.start(IgnitionEx.java:607) at org.apache.ignite.internal.processors.platform.PlatformAbstractBootstrap.start(PlatformAbstractBootstrap.java:43) at org.apache.ignite.internal.processors.platform.PlatformIgnition.start(PlatformIgnition.java:74) Caused by: class org.apache.ignite.IgniteCheckedException: Failed to start SPI: TcpDiscoverySpi [addrRslvr=null, sockTimeout=-300, ackTimeout=5000, marsh=JdkMarshaller [clsFilter=org.apache.ignite.marshaller.MarshallerUtils$1@6a66a204], reconCnt=10, reconDelay=2000, maxAckTimeout=600000, soLinger=5, forceSrvMode=false, clientReconnectDisabled=false, internalLsnr=null, skipAddrsRandomization=false] at org.apache.ignite.internal.managers.GridManagerAdapter.startSpi(GridManagerAdapter.java:300) at org.apache.ignite.internal.managers.discovery.GridDiscoveryManager.start(GridDiscoveryManager.java:940) at org.apache.ignite.internal.IgniteKernal.startManager(IgniteKernal.java:1736) ... 7 more Caused by: class org.apache.ignite.spi.IgniteSpiException: SPI parameter failed condition check: sockTimeout > 0 at org.apache.ignite.spi.IgniteSpiAdapter.assertParameter(IgniteSpiAdapter.java:330) at org.apache.ignite.spi.discovery.tcp.TcpDiscoverySpi.initializeImpl(TcpDiscoverySpi.java:2101) at org.apache.ignite.spi.discovery.tcp.TcpDiscoverySpi.spiStart(TcpDiscoverySpi.java:2061) at org.apache.ignite.internal.managers.GridManagerAdapter.startSpi(GridManagerAdapter.java:297) ... 9 more [10:26:56] Ignite node stopped OK [uptime=00:00:01.464] terminate called after throwing an instance of 'ignite::IgniteError' what(): Failed to start manager: GridManagerAdapter [enabled=true, name=org.apache.ignite.internal.managers.discovery.GridDiscoveryManager] Signal: SIGABRT (Aborted)
can not I use Ignite CPP Node between Java Nodes? or did I omit some options? Java node works well with another Java node.
thank you.
-
How to persist LocalDate with JPA?
I want to store date without time into my database. So I choose to use
LocalDate
type.As mentionned here https://thoughts-on-java.org/persist-localdate-localdatetime-jpa/ I use a converter to convert
LocalDate
toDate
.However, I have some troubles when I want to persist my entity (with POST and PUT requests).
Error
2019-02-23 11:26:30.254 WARN 2720 --- [-auto-1-exec-10] .w.s.m.s.DefaultHandlerExceptionResolver : Resolved [org.springframework.http.converter.HttpMessageNotReadableException: JSON parse error: Expected array or string.; nested exception is com.fasterxml.jackson.databind.exc.MismatchedInputException: Expected array or string. at [Source: (PushbackInputStream); line: 1, column: 104] (through reference chain: ...entity.MyObject["startdate"])] org.springframework.http.converter.HttpMessageConversionException: Type definition error: [simple type, class org.springframework.http.ResponseEntity]; nested exception is com.fasterxml.jackson.databind.exc.InvalidDefinitionException: Cannot construct instance of `org.springframework.http.ResponseEntity` (no Creators, like default construct, exist): cannot deserialize from Object value (no delegate- or property-based Creator) at [Source: (PushbackInputStream); line: 1, column: 2]
Code
Converter
package ...entity; import javax.persistence.AttributeConverter; import javax.persistence.Converter; import java.time.LocalDate; import java.sql.Date; @Converter(autoApply = true) public class LocalDateAttributeConverter implements AttributeConverter<LocalDate, Date> { @Override public Date convertToDatabaseColumn(LocalDate locDate) { return (locDate == null ? null : Date.valueOf(locDate)); } @Override public LocalDate convertToEntityAttribute(Date sqlDate) { return (sqlDate == null ? null : sqlDate.toLocalDate()); } }
Entity
package ...entity; import org.hibernate.annotations.ColumnDefault; import javax.persistence.*; import java.time.LocalDate; import java.util.HashSet; import java.util.Set; @Entity public class MyObject { @Id private String id; private LocalDate startdate; private LocalDate enddate; public MyObject() {} public MyObject(LocalDate enddate) { this.startdate = LocalDate.now(); this.enddate = enddate; } ... }
"Wrong code"
private DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-dd"); MyObject myobject = new MyObject(LocalDate.parse("2019-03-01", formatter));
Thanks for help.
-
How to make array of arrays from a tree datastructure in javascript?
how do i convert the above data structure to
[['Tywin'],['Jamie','Cersi', 'Tyrion'], ['Joeffry', 'Myrcella', 'Tomen', 'Lin']]
Here's my code:
let Tree = function(name) { this.name = name; this.children = []; } Tree.prototype.addChild = function(parent, name) { const node = lannister.contains(parent); node.children.push(new Tree(name)); } var lannister = new Tree('Tywin'); lannister.addChild('Tywin', 'Jamie'); lannister.addChild('Tywin', 'Cersi'); lannister.addChild('Tywin', 'Tyrion'); lannister.addChild('Cersi', 'Joffery'); lannister.addChild('Cersi', 'Myrcella'); lannister.addChild('Cersi', 'Tomen'); lannister.addChild('Tyrion', 'Lin'); bfs(); function bfs(check) { // console.log('traverseBFS called: ', this); bfsArray = []; var queue = [this]; var node; var tempAr = []; bfsArray.push([this.name]); while (queue.length > 0) { node = queue.shift(); callback(node.name, node.children.length); console.log('current node is: ', node, node.children.length); for (var i = 0; i < node.children.length; i++) { queue.push(node.children[i]); tempAr.push(node.children[i].name); if (i === node.children.length - 1) { // console.log('The bfs is ', bfsArray, tempAr); bfsArray.push(tempAr); tempAr = []; } } } function callback(itm, length) { // console.log('itm is: ', itm); if (itm === check) { node; } } };
-
Navigate through dynamically generated detail pages - OpenUi5
I have a splitApp with a Tree in the Master Page and each time a treeNode is expanded, I generate a new Detail Page and display it in the detail section. I want to be able to navigate back to the previous detail Page but I don't know how can I achieve that.
var app = this.getView().byId("SplitAppDemo"); var page = new sap.m.Page({ title: lItem, showNavButton: true, navButtonPress: function(){ app.getSplitAppObj().backDetail(); } }); app.addDetailPage(page); app.toDetail(page);
The lItem is the text of the node. In this code I get an error that "app.getSplitAppObj()" is not a function.
Any ideas? Thank you!!
-
Retrieve the parents and children using HyperGraphQL
I'm querying go.owl file containing the Gene Ontology using HyperGraphQL in order to retrieve the parents/ancestors and children/descendents of a giving GO id
I could retrieve the parents using the query:
{ Class_GET_BY_ID(uris:[ "http://purl.obolibrary.org/obo/GO_0032259", "http://purl.obolibrary.org/obo/GO_0007267"]) { id label subClassOf { id label subClassOf { id label subClassOf { ... } } } } }
but I don't know how to do the same to extract the descendents.
The
schema.graphql
:type __Context { Class: _@href(iri: "http://www.w3.org/2002/07/owl#Class") id: _@href(iri: "http://www.geneontology.org/formats/oboInOwl#id") label: _@href(iri: "http://www.w3.org/2000/01/rdf-schema#label") subClassOf: _@href(iri: "http://www.w3.org/2000/01/rdf-schema#subClassOf") } type Class @service(id:"go-local") { id: [String] @service(id:"go-local") label: [String] @service(id:"go-local") subClassOf: [Class] @service(id:"go-local") }
I know it depends on the fields defined in the ontology, for instance in the first query I used
subClassOf
to get the top level.In SPARQL we can get the parents like this:
GO:0000XYZ rdfs:subClassOf* ?parents
And the children:
?chilren rdfs:subClassOf* GO:0000XYZ
As you see we can get both just by switching the query, is there a way to do something similar using GraphQL ?
-
How to use binary-only package with "go get"
My binary package have some dependencies installed from
go get
command. After building and create sourcode with//go:binary-only-package
There are some errors like:
cannot find package github.com/robfig/cron (using -importcfg) cannot find package github.com/go-chi/chi/middleware (using -importcfg)
How do i import binary-only package?
-
Need assistance with Octal number subtraction
So I am trying to understand the difference between unsigned and signed octal number subtraction if the octal numbers were 6 bits. For example, octal 76 - octal 64: I first convert 76 to binary which becomes 111 110 and 64 to binary which becomes 110 and 100:
But the problem is, if these octal numbers represent signed 6-bit octal numbers, would that mean the 111 110 is negative and 110 100 is also negative, meaning that the subtraction operator will cancel with the negative sign of the second octal number, resulting in an addition? Or do we just treat it normally, subtract the 2 binary numbers normally, and then look at the sign after?
-
Why is this binary search program giving me an Infinite Loop?
See Line no 5. If I Replace it with mid = l + (r - 1) / 2; Then it is working Fine. Why? Is it issue with my compiler? I have tried compiling with online compliers but its still not working.
#include<stdio.h> int binary_search(int a[], int l, int r, int x){ int mid; while(l<=r){ mid = (l + r - 1) / 2; //See Here printf("%d ",mid); //To Check values of mid if(a[mid]==x){ return 1; } if(a[mid] < x){ l=mid+1; } else{ r=mid-1; } } return 0; } void main(){ int a[] = {1,2,3,4,5,6,7,8,9,10}; int size = sizeof(a)/sizeof(a[0]); if(binary_search(a,0,size-1,4)){ printf("Found"); } else{ printf("Not Found"); } }
-
stackoverflow error in recursive function
I have the following function is in class implementing a set of numbers as a binary search tree.The function checks if the input integer is in the tree.
public boolean isIn(int v){ if(root != null){ if(v == root.element){ System.out.print(root.element); return true; } isIn(root.left.element); isIn(root.right.element); } return false; }
I am getting Exception in thread "main" java.lang.StackOverflowError if I check anything other than the first element of the tree with the function.
-
boost c++ binary tree with hooks to let me know when/where a node is inserted or moved
I've implemented myself an Interval Tree similar but not the same as in this article.. Like the article I've used a simple non self balancing binary tree. I'd like to use something like a red-black tree to keep look-ups efficient.
However an interval tree maintains extra metadata per node such as the maximum and minimum of all intervals of all sub-trees. This means that on any tree manipulation such as insert/remove/re-balancing these values need to be recalculated.
To simplify my concept imagine I had a tree node like below ( not the same as for an interval tree but the concept is similar )
struct Node { double value; // the value the tree is partitioned on Node * left; Node * right; double max; // max of all values in right subtree double min; // min of all values in left subtree }
each node contains a value and a pointer to the left and right. However the node also contains a computation of the max value of the right sub tree and a computation of the min value of the left sub tree. So I might start with an unbalanced tree like
A(10,8,10) / B(9,8,9) / D(8,8,8)
where the tuple represent name(value,min,max). After re balancing via whatever algorithm the tree uses I would end up with
B(9,8,10) / \ D(8,8,8) A(10,10,10)
However you notice the meta data is now updated. I would need some hooks in the tree code to allow me to efficiently recalculate these values for sub trees that change.
If somebody could show how to use a boost c++ red-black tree or another self balancing tree to do the above simple structure then I am sure I could extended it to my more complex interval tree code.
An attempt has been made to do this with boost::intrusive but it will not really work.
http://coliru.stacked-crooked.com/a/1ec5d00968532035
This is because the available hooks provide no guarantees on the state of the tree when the call is made, thus trying to navigate the tree at this point is equivalent to a race condition in multithreaded code. Anything might happen.
#include <boost/intrusive/rbtree_algorithms.hpp> #include <cassert> #include <algorithm> #include <stack> #include <tuple> #include <iostream> namespace Foo { template <typename T> struct TNode { TNode(T i = T()) : left(nullptr) , right(nullptr) , color(0) , value(i) , min(value) , max(value) {} TNode *parent, *left, *right; int color; int value; int min; int max; }; //Define our own rbtree_node_traits template <typename T> struct my_rbtree_node_traits { typedef TNode<T> node; typedef TNode<T> * node_ptr; typedef const TNode<T> * const_node_ptr; typedef int color; static node_ptr get_parent(const_node_ptr n) { return n->parent; } static void set_parent(node_ptr n, node_ptr parent){ n->parent = parent; } static node_ptr get_left(const_node_ptr n) { return n->left; } static void set_left(node_ptr n, node_ptr left) { n->left = left; bubbleMinMax(n); } static node_ptr get_right(const_node_ptr n) { return n->right; } static void set_right(node_ptr n, node_ptr right) { n->right = right; bubbleMinMax(n); } static color get_color(const_node_ptr n) { return n->color; } static void set_color(node_ptr n, color c) { n->color = c; } static color black() { return color(0); } static color red() { return color(1); } static void bubbleMinMax(node_ptr n) { if(n==nullptr) return; typedef boost::intrusive::rbtree_algorithms<my_rbtree_node_traits<T>> algo; auto parent = n; while(parent!=nullptr&&!algo::is_header(parent)) { if(parent->left) parent->min = std::min(parent->left->min, parent->value); else parent->min = parent->value; if(parent->right) parent->max = std::max(parent->right->max, parent->value); else parent->max = parent->value; if(parent->parent == parent) break; parent = parent->parent; } } }; template <typename T> struct node_ptr_compare { bool operator()(const TNode<T> *a, const TNode<T> *b) { return a->value < b->value; } }; template <typename T> struct Traits{ typedef TNode<T> Node; typedef my_rbtree_node_traits<T> RbTraits; typedef node_ptr_compare<T> Compare; static void Print(Node const& root, int n = 0) { std::stack<std::tuple<Node const *,int,char>> stack; stack.push(std::make_tuple(&root, 0, 'R')); while(!stack.empty()) { auto item = stack.top(); auto tree = std::get<0>(item); auto depth = std::get<1>(item); auto dir = std::get<2>(item); stack.pop(); if(tree == nullptr) { std::cerr << std::string(depth * 2, ' ') << dir << "-" << std::endl; } else { std::cerr << std::string(depth * 2, ' ') << dir << " " << "value: " << tree-> value << " min: " << tree-> min << " max: " << tree->max << std::endl; stack.push(std::make_tuple(tree->right, depth + 1,'R')); stack.push(std::make_tuple(tree->left, depth + 1,'L')); } } } }; } int main() { typedef Foo::Traits<int> Traits; typedef boost::intrusive::rbtree_algorithms<Traits::RbTraits> algo; Traits::Node header, two(2), three(3); // Create an empty rbtree container: //"header" will be the header node of the tree algo::init_header(&header); for(int i = 0; i < 8 ; i++){ algo::insert_equal_upper_bound(&header, new Traits::Node(i), Traits::Compare()); } Traits::Print(*algo::root_node(&header)); }
and the output is
L value: 1 min: 0 max: 7 L value: 0 min: 0 max: 0 L- R- R value: 2 min: 2 max: 2 L- R- R value: 5 min: 4 max: 7 L value: 4 min: 4 max: 4 L- R- R value: 6 min: 6 max: 7 L- R value: 7 min: 7 max: 7 L- R-
which is clearly wrong. The first left node has a max of 7 in its subtree but there are no nodes there with a value of 7.
-
Building a Binary Search Tree from a file
I have a text file of lines in the format
2 0 0 7 0 0 4 1 1 10 0 0 9 0 1 8 1 1
These lines represent the data in a binary search tree where the first element is the node data, the second is whether or not a left child exists ( 0 if no, 1 if yes) and the third is whether or not a right child exists (0 if no, 1 if yes)
I have a class called "BinarySearchTree" which has the following initialization function
def __init__(self, value=None): # Initializes the tree with a value node, a left child and a right child self.leftChild = None self.rightChild = None self.height = 1 self.value = value
I also have a stack class with the following "push" and "pop" functions:
def push(self, item): # Adds an item to the beginning of the stack ending = self.stack self.stack = [item] + [ending] def pop(self): # Removes and returns the first element from the stack if self.isEmpty(): return None top_element = self.stack[0] self.stack = self.stack[1:] return top_element
I am trying to create a binary search tree instance from the lines in the text file and using the stack class. So far I have:
def loadTreeFromFile(filename): binarySearchTree = stack.Stack() with open(filename) as file: # gets a list containing only the elements in the txt file for level in file.readlines(): nodeInfo = level.rstrip().split() data, lc, rc = int(nodeInfo[0]), int(nodeInfo[1]), int(nodeInfo[2]) print(data, lc, rc) if rc == 1: right_tree = binarySearchTree.pop() if lc == 1: left_tree = binarySearchTree.pop() newTree = BinarySearchTree(data) if rc == 1: newTree.rightChild = right_tree if lc == 1: newTree.leftChild = left_tree binarySearchTree.push(newTree) return newTree
I am running into the problem when I try to display the BST, I get
8: [[[<__main__.BinarySearchTree object at 0x1033e4390>, []]], 9: [None, 10: [None, None]]]
(I have a display function written for the BST class so this is not the problem) AND when I try to do anything with this newly created BST (such as get the depth, search it, etc), I get errors. Any help is much appreciated, thanks .