Remove Node from Binary Search Tree

See also questions close to this topic

• Export Project from Netbeans as 32 bit Installer

  I want to export my Java Swing project as .exe Installer for 32 bit platform.

  I've OS : Windows 10, 64 bit Netbeans Version : 8.2

  What should I do?

  Also I want to know whether I can make .exe Installer with embedded Oracle Database.
• Incorrect parsing response from feign client

  I have a simple Feign client:

  @FeignClient(
  serviceId = "${com.service}",
  fallbackFactory = AccountFeignServiceClient.AccountFallBackFactory.class)
  public interface AccountFeignServiceClient {
  
    @GetMapping("/users/{id}")
    ResponseEntity<AccountDto> getUser(@PathVariable("id") String id);
  }
  

  Method in another server:

  @GetMapping(value = "/users/{id}")
  ResponseEntity<?> getUser(@PathVariable(value = "id") String id) {
    return ok(...);
  }
  

  Problem is that AccountDto have only null fields. After debag I found the following reason for this behavior. If i get the response in in feign client of type string it will be like:

  {"headers":{},"body":{"id":"d267294f-d4b2-493b-9829-63ece48922e9"},"statusCode":"OK","statusCodeValue":200}
  

  But if i get the response of type ResponseEntity<?> i will get this:

  You can see it have double body and i have no ideas why. With type ResponseEntity<?> i expect response like:

  
• Find an object in Hibernate without id

  I'm using Spring. I have a user table.

  When a person logins to the system, he sends me his credentials (i.e. username and password).

  I stored my users in database with "incremental generated uid" (i.e. userid is primary key).

  I also stored the username password etc. in the database. What I need to do is, when the user connects to the Rest connection, I need to check whether the database has this user or not. If he exists, then I need to check if passwords are matching. And I need to do that checking by username, rather than uid

  I dont have session or anything at all in my program (Or as far as I know, I didn't write any session or sessionfactory in my code at all)

  My repository class:

  public interface UserRepository extends JpaRepository<User, Long>{
  }
  

  My user DAO

  @Service
  public class UserDAO {
  
      @Autowired
      UserRepository userRepository;
  
      public User findByUsername(String username)
      {
          //what to write here
  
      }
  }
  

  I've looked up this solution but as I stated above, I don't have session.
• Are there any efficient ways to populate a balanced tree structure

  I have a balanced binary tree structure:

  Node 0 at depth 0 is the root. The root's left child is 1 and right child is 2, and so on.

  Please see image:

  The total depth of the tree is given as N. This N is the only parameter of the problem. Nodes at level N are designated as leaf nodes.

  I am storing this tree using the following node structure.

  struct node_s{
      int n, depth, parent;//n is node number
      int nodescendents;//number of descendents of the current node
      std::vector<int> descendents;//Descendents in ascending order
      int lchild, rchild;//Immediate left child and right child
      std::vector<int> lchildleaves;//leaf nodes that descend from the immediate 
                                                        //left child
      std::vector<int> rchildleaves;//leaf nodes that descend from the immediate 
                                                        //right child
  };
  

  I intend to store the tree itself as:

  std::vector<node_s> tree;
  

  Is there a way to numerically efficiently populate the tree vector using simple algebra roughly as:

  //Creating the nth node, beginning from 0th node, then 1st node and so on
  nodes_s node;
  //populate all data structures of the nth node
  //precisely, here, there are loops, algebraic calculations, etc., that can help 
  //populate all of the node_s data members.
  tree.push_back(node);
  

  The only way I can think of as of now is to construct a graph explicitly and run some sort of Dijkstra algorithm to figure out these data structure values for each node.
• Decision Tree How to insert items to the right or left of node?

  Say I have a List of Numbers I want to insert everything in the A1 column to the left if it's bigger than A1, if it's not bigger than I want to insert it to the right of my decision node. Something like this diagram.

  To manage the data I created a struct and each line would be a data object of its own so the first line (1,4) is one data and (77,6) is another.

  I'm not sure how to organize that data where values in the A1 column that A1 > 8 is on the left else on the right.

  How would I store the values of my vector in to one node, and map the correct classification to the values for instance right of A1 > 8 would have values (8, 1) and their respective classification is (yes, yes)

  struct data
  {
      string group;
      vector<double> values;
  };
  
• weka desicion tree has empty conjuctions

  picture of tree

  Here is the Tree, near the top of the tree by the root, the branched off conjuctions are empty which I don't understand.

  The TextDirectoryLoader, StringToWordVector filter, AttributeSelection filter, and J48 decision tree classification operations were applied to the data as well as Lovins Stemmer.

  The data has to do with identifying fake news articles by text files.

  What are these empty conjutions? I can't find anything similar.
• How can i Find biggest binary number before a number in c++?

  I want to find biggest binary number before a number Like Biggest binary number before 3567 is 1111 In c++
• Java numeric conversion is unclear

  Consider the following piece of code:

  byte newBytes[] = new byte[(myBytes.length + 8) & ~7];
  

  I understand java doesn't really deal with unsigned ints, so if the length of myBytes was INT_MAX, then adding to the length would overflow into a negative number.

  But, what is the ~7 doing?

  If: myBytes = 2147483647, then 2147483647 + 8 = -2,147,483,641

  ANDing ~7 to that, just makes it -2,147,483,648 .. still a negative number.

  Is this just wonky code or is there a java subtlety that a clever programmer is exploiting here?
• Serve xlsx file from MongoDB binary using Node.js

  I have some Excel documents (xlsx) saved in MongoDB in binary. I would like node.js to retrieve a file from the database when a user navigates to a url and serve the file for the user to download. I'm successfully downloading a file, but I'm getting an error from Excel when trying to open the file:

  "Excel cannot open the file '5beec8ef3cf3e70b5ce8972e.xlsx' because the file format or file extension is not valid. Verify that the file has not been corrupted and that the file extension matches the format of the file."

  The file is also saving with 0 bytes. I think I am not correctly converting the data from MongoDB before trying to create the buffer. Here's my script:

  app.get('//downloadReport/:id', (req, res) => {
      dbo = db.db('test');
      dbo.collection("reports").findOne(
          {'_id': mongodb.ObjectId(req.params.id)}
      ).then(doc => {
  
          console.log('type of doc.file: ' + typeof doc.file);
          // returns:
          // type of doc.file: object
  
          console.log(doc.file);
          // returns:
          // Binary {
          //   _bsontype: 'Binary',
          //   sub_type: 0,
          //   position: 1146504,
          //   buffer: <Buffer 50 4b 03 04 14 00 00 00 08 00 12 66 6f 4d f8 64 19 ... > }
  
  
          res.writeHead(200, [['Content-Type',  'application/vnd.openxmlformats-officedocument.spreadsheetml.sheet']]);
  
          // This one doesn't work
          // res.end(doc.file, 'binary');
          // returns:
          // TypeError: First argument must be a string or Buffer
  
          res.end(new Buffer(doc.file, 'binary') );
      });
  });
  

  I've tried drilling down to doc.file.Binary.buffer, but I get an error saying doc.file.Binary is not defined.

  I also want the file to download with the correct file name. I've tried adding this to writeHead:

  ['Content-disposition', 'filename=' + doc.filename]
  

  but I get an error in Chrome: ERR_RESPONSE_HEADERS_MULTIPLE_CONTENT_DISPOSITION

  Anyone know how to make this work? Thanks in advance!
• Absolutely fried on implementing rotation in a C++ binary search tree

  I've spent several hours trying to make this darn thing work, and at this point my brain is so fried I can barely explain what I'm trying to do. I'll admit it's homework, but I'm 100% lost on how to make progress, and it's one of the very few things I have left in this project. The rotation functions are taken (with permission) from lecture notes, but by god I can't get them to work.

  contains() is supposed to check whether an element exists somewhere in the tree, and if that element has been searched for search_threshold times, rotate it one position higher in the tree.

  I tried my own messy solution for a while, but it didn't work nearly the way it needed to. For now I was just shooting to get a really basic case for rotation working, where the node that's being moved up has no children, but even that seems to be dropping nodes. Any tips how to get back on track?

  //BSTNode is a struct with
  T element, 
  BSTNode *left = NULL, 
  BSTNode *right = NULL, 
  BSTNode *parent = NULL, 
  int search_count = 0
  

  Abbreviated code as follows:

  template <typename T>
  void BST< T >::rotateWithLeftChild(BSTNode *& k2)
  {
      BSTNode *k1 = k2->left;
      k2->left = k1->right;
      k1->right = k2;
      k2 = k1;
  }
  
  template <typename T>
  void BST< T >::rotateWithRightChild( BSTNode *& k2)
  {
      BSTNode *k1 = k2->right;
      k2->right = k1->left;
      k1->left = k2;
      k2 = k1;
  }
  
  template <typename T>
  void BST< T >::doubleWithRightChild( BSTNode *& k3 )
  {
      rotateWithLeftChild( k3->right );
      rotateWithRightChild( k3 );
  }
  
  template <typename T>
  void BST< T >::doubleWithLeftChild( BSTNode *& k3 )
  {
      rotateWithRightChild( k3->left );
      rotateWithLeftChild( k3 );
  }
  
  template <typename T>
  bool BST< T >::contains(const T& v, BSTNode *&t)
  {
      // If the node doesn't exist, return false
      if (t == NULL)
          return false;
      // If the node exists, return true
      if (t->element == v)
      {
          // Increment search count
          t->search_count++;
          // If search count is above threshold,
          if (t->search_count >= threshold)
          {
              cout << "Search count above threshold" << endl;
              // Reset search count
              t->search_count = 0;
  
              if (t == root)
                  return true;
  
              // Faaaaaairly confident that my bug is here
              if (t->left != NULL && t->right != NULL)
              {
                  cout << "parent element: " << t->parent->element << endl;
                  if (t == t->parent->left)
                      rotateWithLeftChild(t->parent);
              }
          }
          return true;
      }
      // Otherwise, return the OR of the children's contains()
      else
          return (contains(v, t->left) || contains(v,t->right));
  }
  
• Comparing BST node with str issue

  This is the search function I'm using to try and find a specific value held in a BST that holds words. However when I run it I am given an error on the line elif root < root.value:

  def search(root, target):
      print("Target is: " + target + "\n")
      if root.value == target or root == None:
          print("Found target: " + target)
          return root
      elif root < root.value:
          return search(root.left, target)
          print("Searching left")
      else:
          return search(root.right, target)
          print("Searching right")
  

  It says TypeError: '<' not supported between instances of 'Node' and 'str', now as far as I know I can use < and > too compare regular strings, but I cant seem to use it to compare a root a node containing a string and another node containing a string? Is their another way I should go about comparing?
• Which node do I check in an AVL Tree to decide whether I need to rotate the tree? Sample code in C++

  I'm trying to understand why this code works.

  It seems to me that there's a mistake in the function insert.

  Since prev will be the parent node of the new node we're going to insert into the tree, I don't see how the difference in the heights of the left and right children of the parent can be more than one, and so I don't see why rotation would ever occur.

  After insertion, prev will either have a left and a right child, or just one child.

  If the parent has one child then the difference in heights is 1.

  If the parent has two children then the difference in heights is 0.

  Can someone tell me what I'm missing here?

  #include <iostream>
  #include <ctime>
  
  using namespace std;
  
  template <class T>
  class AVL;
  
  template <class T>
  T& max(T& left, T& right){
      if (left > right)
          return left;
      else
          return right;
  
  }
  template <class T>
  T max(const T& left, const T& right){
      if (left > right)
          return left;
      else
          return right;
  
  }
  
  /*
  
   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
   */
  
  
  
  template <class T>
  class AVLNode{
      AVLNode<T>* parent, *left, *right;
      int height;
      T data;
  public:
      friend class AVL < T >;
      AVLNode(const T& newdata = T(), AVLNode<T>* newparent = nullptr, AVLNode<T>* newleft = nullptr, AVLNode<T>* newright = nullptr) :
      data(newdata), parent(newparent), left(newleft), right(newright) { calcHeight(); }
      void calcHeight(){
          int leftHeight = -1;
          int rightHeight = -1;
          if (left != nullptr)
              leftHeight = left->height + 1;
          if (right != nullptr)
              rightHeight = right->height + 1;
          height = max(leftHeight, rightHeight) + 1;
      }
      void printInOrder()const{
          if (left != nullptr)
              left->printInOrder();
          cout << data << endl;
          if (right != nullptr)
              right->printInOrder();
      }
      int size()const{
          int leftSize = 0;
          int rightSize = 0;
          if (left != nullptr)
              leftSize = left->size();
          if (right != nullptr)
              rightSize = right->size();
          return 1 + leftSize + rightSize;
      }
      /*    int height()const{
       int leftSize = -1;
       int rightSize = -1;
       if (left != nullptr)
       leftSize = left->height();
       if (right != nullptr)
       rightSize = right->height();
       return 1 + max(leftSize, rightSize);
       }*/
      int depth() const{
          int parentDepth = -1;
          if (parent != nullptr)
              parentDepth = parent->depth();
          return 1 + parentDepth;
      }
  };
  
  
  /*
   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
   */
  
  
  
  
  
  
  
  template <class T>
  class AVL{
      AVLNode<T>* root;
      int size;
      AVLNode<T>* recursiveCopy(AVLNode<T>* toCopy);
      void singleCCR(AVLNode<T>*& point);
      void doubleCR(AVLNode<T>*& point);
      void singleCR(AVLNode<T>*& point);
      void doubleCCR(AVLNode<T>*& point);
      int heightDiff(AVLNode<T>* point);
      void doRotation(AVLNode<T>* point);
  public:
      AVL() :size(0){ root = nullptr; }
  
      //memory on the heap so.... here comes the big 3!
      AVL(const AVL<T>& rhs) :root(nullptr){ *this = rhs; }
      virtual ~AVL(){ clear(); }
      AVL& operator=(const AVL<T>& rhs);
  
      bool isInTree(const T& toFind) const{ return find(toFind) != nullptr; }
      bool isEmpty()const{ return root == nullptr; }
      int getSize()const { return size; }
      void remove(const T& toRemove){
          AVLNode<T>* item = find(toRemove);
          if (item != nullptr)
              remove(item);
      }
      void insert(const T&);
      void remove(AVLNode<T>*);
      AVLNode<T>* find(const T& toFind) const;
      void clear(){ while (!isEmpty()) remove(root); }
      void printInOrder()const{ root->printInOrder(); }
  };
  template <class T>
  void AVL<T>::doubleCCR(AVLNode<T>*& point){
      singleCR(point->right);
      singleCCR(point);
  }
  
  template <class T>
  void AVL<T>::doubleCR(AVLNode<T>*& point){
      singleCCR(point->left);
      singleCR(point);
  }
  
  template <class T>
  void AVL<T>::singleCR(AVLNode<T>*& point){
      AVLNode<T>* grandparent = point;
      AVLNode<T>* parent = point->left;
      parent->parent = grandparent->parent;
      grandparent->parent = parent;
      grandparent->left = parent->right;
      parent->right = grandparent;
      if (grandparent->left != nullptr) //if we now have a left child, update its parent pointer
          grandparent->left->parent = grandparent;
      if (parent->parent == nullptr)//if we were the root, update the root!
          root = parent;
      else if (parent->parent->left == grandparent)
          parent->parent->left = parent;
      else
          parent->parent->right = parent;
      grandparent->calcHeight();
      parent->calcHeight();
  }
  
  template <class T>
  void AVL<T>::singleCCR(AVLNode<T>*& point){
      AVLNode<T>* grandparent = point;
      AVLNode<T>* parent = point->right;
      parent->parent = grandparent->parent;
      grandparent->parent = parent;
      grandparent->right = parent->left;
      parent->left = grandparent;
      if (grandparent->right != nullptr) //if we now have a right child, update its parent pointer
          grandparent->right->parent = grandparent;
      if (parent->parent == nullptr)//if we were the root, update the root!
          root = parent;
      else if (parent->parent->right == grandparent)
          parent->parent->right = parent;
      else
          parent->parent->left = parent;
      grandparent->calcHeight();
      parent->calcHeight();
  }
  
  
  template <class T>
  AVLNode<T>* AVL<T>::recursiveCopy(AVLNode<T>* toCopy){
      if (toCopy == nullptr)
          return nullptr;
      AVLNode<T>* temp = new AVLNode<T>(toCopy->data, nullptr, recursiveCopy(toCopy->left), recursiveCopy(toCopy->right));
      if (temp->left != nullptr)
          temp->left->parent = temp;
      if (temp->right != nullptr)
          temp->right->parent = temp;
      return temp;
  }
  
  template <class T>
  AVL<T>& AVL<T>::operator=(const AVL<T>& rhs){
      if (this == &rhs)
          return *this;
      clear();
      root = recursiveCopy(rhs.root);
      size = rhs.size;
      return *this;
  }
  
  template <class T>
  void AVL<T>::remove(AVLNode<T>* toRemove){
      if (root == nullptr)
          return; //Remove from an empty tree????
      if (toRemove->left == nullptr && toRemove->right == nullptr){ //leaf node case
          if (toRemove->parent == nullptr){
              root = nullptr;
          }
          else if (toRemove == toRemove->parent->left) //left child!
              toRemove->parent->left = nullptr; //fix the parent's pointer!
          else
              toRemove->parent->right = nullptr;
          delete toRemove;
          size--;
      }
      else if (toRemove->right == nullptr){ //has one (left) child
          if (toRemove->parent == nullptr){
              root = toRemove->left;
              root->parent = nullptr;
          }
          else if (toRemove == toRemove->parent->left){ //we're the left child of our parent
              toRemove->parent->left = toRemove->left;
              toRemove->left->parent = toRemove->parent;
          }
          else{
              toRemove->parent->right = toRemove->left;
              toRemove->left->parent = toRemove->parent;
          }
          delete toRemove;
          size--;
      }
      else if (toRemove->left == nullptr){ //has one right child, almost same solution as left child only
          if (toRemove->parent == nullptr){
              root = toRemove->right;
              root->parent = nullptr;
          }
          else if (toRemove == toRemove->parent->left){ //we're the left child of our parent
              toRemove->parent->left = toRemove->right;
              toRemove->right->parent = toRemove->parent;
          }
          else{
              toRemove->parent->right = toRemove->right;
              toRemove->right->parent = toRemove->parent;
          }
          delete toRemove;
          size--;
      }
      else{ //sigh... two children!
          AVLNode<T>* temp = toRemove->right;
          while (temp->left != nullptr)
              temp = temp->left;
          toRemove->data = temp->data;
          remove(temp);
      }
  
  }
  
  template <class T>
  AVLNode<T>* AVL<T>::find(const T& toFind) const{
      AVLNode<T>* temp = root;
      while (temp != nullptr && temp->data != toFind){
          if (toFind < temp->data)
              temp = temp->left;
          else
              temp = temp->right;
      }
      return temp;
  }
  
  template <class T>
  void AVL<T>::insert(const T& toInsert){
      size++;
      if (root == nullptr){
          root = new AVLNode<T>(toInsert);
      }
      else{ // if prev isn't root then shouldn't we look at prev's parent for heightDiff and rotation?
          AVLNode<T>* temp = root;
          AVLNode<T>* prev = temp;
          while (temp != nullptr){
              prev = temp;
              if (toInsert < temp->data)
                  temp = temp->left;
              else
                  temp = temp->right;
          }
          //now temp points to null and prev points to the node we want to insert onto
          if (toInsert < prev->data){ //insert onto the left of Prev
              prev->left = new AVLNode<T>(toInsert, prev);
          }
          else
              prev->right = new AVLNode<T>(toInsert, prev);
  
          if(prev != nullptr){ // when would prev be nullptr?
              prev->calcHeight();
              if (heightDiff(prev)>1) // wouldn't only prev's parent have the possibility of > 1? ****
                  doRotation(prev); // how could it ever be larger than 1?
          }
      }
  }
  template <class T>
  void AVL<T>::doRotation(AVLNode<T>* point){
      int leftChild = -1;
      int rightChild = -1;
      if (point->left != nullptr)
          leftChild = point->left->height;
      if (point->right != nullptr)
          rightChild = point->right->height;
  
      if (leftChild > rightChild){//CR, but is it single or double?
          int leftGC = -1;
          int rightGC = -1;
          if (point->left->left != nullptr)
              leftGC = point->left->left->height;
          if (point->left->right != nullptr)
              rightGC = point->left->right->height;
          if (leftGC > rightGC) // single rotation
              singleCR(point);
          else
              doubleCR(point);
      }
      else{//definitely a CCR, but which one?
          int leftGC = -1;
          int rightGC = -1;
          if (point->right->left != nullptr)
              leftGC = point->right->left->height;
          if (point->right->right != nullptr)
              rightGC = point->right->right->height;
          if (leftGC > rightGC) // double rotation
              doubleCCR(point);
          else
              singleCR(point);
      }
  }
  
  
  template<class T>
  int AVL<T>::heightDiff(AVLNode<T>* point){
      int leftHeight = -1;
      int rightHeight = -1;
      if (point->left != nullptr)
          leftHeight = point->left->height;
      if (point->right != nullptr)
          rightHeight = point->right->height;
      return (abs(leftHeight - rightHeight));
  }
  
  
  /*
   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
  
   */
  
  
  
  int main(){
      {
  
          AVL<int> b;
          srand(time(NULL));
          for (int i = 0; i < 100; i++)
              b.insert(rand() % 1000);
  
          b.printInOrder();
          cout << "Got here!" << endl;
      }
      cout << "Got here #2" << endl;
  }