C++에서 상위 포인터가 있는 이진 검색 트리 삽입

<시간/>

재귀적 방식으로 새 노드를 BST에 삽입할 수 있습니다. 이 경우 각 하위 트리의 루트 주소를 반환합니다. 여기에서 부모 포인터를 유지 관리해야 하는 또 다른 접근 방식을 볼 수 있습니다. 부모 포인터는 노드 등의 조상을 찾는 데 도움이 됩니다.

아이디어는 왼쪽 및 오른쪽 하위 트리의 주소를 저장하는 것입니다. 재귀 호출 후 반환된 포인터의 부모 포인터를 설정합니다. 이것은 삽입하는 동안 모든 상위 포인터가 설정되었음을 확인합니다. 루트의 부모는 null로 설정됩니다.

알고리즘

삽입(노드, 키) -

begin
   if node is null, then create a new node and return
      if the key is less than the key of node, then
         create a new node with key
         add the new node with the left pointer or node
      else if key is greater or equal to the key of node, then
            create a new node with key
         add the new node at the right pointer of the node
      end if
   return node
end

예시

#include<iostream>
using namespace std;
class Node {
   public:
      int data;
      Node *left, *right, *parent;
};
struct Node *getNode(int item) {
   Node *temp = new Node;
   temp->data = item;
   temp->left = temp->right = temp->parent = NULL;
   return temp;
}
void inorderTraverse(struct Node *root) {
   if (root != NULL) {
      inorderTraverse(root->left);
      cout << root->data << " ";
      if (root->parent == NULL)
         cout << "NULL" << endl;
      else
         cout << root->parent->data << endl;
      inorderTraverse(root->right);
   }
}
struct Node* insert(struct Node* node, int key) {
   if (node == NULL) return getNode(key);
   if (key < node->data) { //to the left subtree
      Node *left_child = insert(node->left, key);
      node->left = left_child;
      left_child->parent = node;
   }
   else if (key > node->data) { // to the right subtree
      Node *right_child = insert(node->right, key);
      node->right = right_child;
      right_child->parent = node;
   }
   return node;
}
int main() {
   struct Node *root = NULL;
   root = insert(root, 100);
   insert(root, 60);
   insert(root, 40);
   insert(root, 80);
   insert(root, 140);
   insert(root, 120);
   insert(root, 160);
   inorderTraverse(root);
}

출력