Екілік іздеу ағашын жою әрекеті


Күрделілік дәрежесі қиын
Жиі кіреді Акколит Amazon Qualcomm Samsung
Екілік іздеу ағашы Екілік ағаш ағаш

Проблемалық мәлімдеме

«Екілік іздеу ағашын жою әрекеті» проблемасы бізден жою әрекетін жүзеге асыруды сұрайды екілік іздеу ағашы. Жою функциясы дегеніміз - берілген кілт / деректермен түйінді жою функционалдығы.

мысал

енгізу

Екілік іздеу ағашын жою әрекеті

Жойылатын түйін = 5

шығыс

Жақындау Екілік іздеу ағашын жою әрекеті

Сонымен, екілік іздеу ағашынан түйінді жою туралы айтатын болсақ. Назар аударатын бір нәрсе - түйінді жойған кезде, BST барлық қасиеттері орындалуы керек. Егер біз ішкі түйінді алып тастасақ, онда жаңа тамырмен бірге ағаштың BST қасиеттерін қанағаттандыратындығына көз жеткізуіміз керек.

Енді бізде үш іс бар. Бұл жағдайлар түйінді балалар санына негізделген. Сұраққа жауап беру үшін неге түйіндерді балалар санына қарай жіктейсіз? Сонымен, жалғызбасты баламен қорғасынмен және түйінмен күресу оңайырақ. Сонымен, барлық үш жағдайды қысқаша талқылайық.

  1. Баласыз түйін (жапырақ)
  2. Жалғыз балалы түйін
  3. Екі бала бар түйін

Егер түйін жапырақ болса, біз түйінді ағаштан алып тастай аламыз. Бұл операция BST қасиеттерінің ешқайсысының бұзылуына әкелуі мүмкін емес. Енді жалғыз баланың жағдайын қарастыратын болсақ. Біз түйінді алып тастап, оның баласын орнына орналастыра аламыз. Жалғыз проблема екі баламен түйінді алып тастауға тырысқанда туындайды.

Екі баласы бар түйінді алып тастау үшін алдымен осы түйіннің инордерлы ізбасарын табамыз. Жойылатын түйін орнына мұрагерді қойыңыз. Енді мұрагерді алып тастауға BST қасиеттерін бұзбайтынына қалай кепілдік бере аламыз? Біз бұған кепілдік бере аламыз, өйткені мұрагер болатын түйін ешқашан екі балалы бола алмайды. Немесе оның бір баласы болады немесе мүлде баласы болмайды. Сондықтан мұрагерді алып тастау BST қасиеттерін бұзбайды. 

код

Екілік іздеу ағашын жою операциясына арналған C ++ коды

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int data;
    node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
}

void inorder(node* root){
  if(root){
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
  }
}

// return the node which is in the most left direction of root
// the smallest node in the entire subtree rooted at current node
node* minNode(node* root)
{
  node* tmp = root;
  while(tmp && tmp->left)
    tmp = tmp->left;
  return tmp;
}

// deleted the node with given data from tree
node* deleteNode(node* root, int data)
{
  // if current node is empty return current node(NULL)
  if(!root) return root;

  	// node to be deleted is in left sub-tree
    if (data < root->data)
        root->left = deleteNode(root->left, data);
  	// node to be deleted in right sub-tree
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    // current node is node to be deleted
    else
    {
        // Case 1 + Case 2
        // if left is null this means that it is either of the two cases
        if (root->left == NULL)
        {
            node* tmp = root->right;
            free(root);
            return tmp;
        }
        // Case 2 node has a left child but not right child
        // thus it has only a single child
        else if (root->right == NULL)
        {
            node* tmp = root->left;
            free(root);
            return tmp;
        }
  		// Case 3
  		// first find the successor
  		// successor is the element which comes next in inorder traversal of BST
  		// so it is the node in most left direction in right sub-tree
        node *successor = minNode(root->right);
        // place successor in place of current node
        root->data = successor->data;
        // now simply delete the successor from root's right child
        root->right = deleteNode(root->right, successor->data);
    }
    return root;
}

int main()
{
  node* root = create(7);
  root->left = create(5);
  root->right = create(8);
  root->left->left = create(3);
  root->left->left->right = create(4);
  root->left->right = create(6);
  cout<<"current inorder traversal of tree"<<endl;
  inorder(root);
  cout<<endl;
  root = deleteNode(root, 5);
  cout<<"inorder traversal after deleting node with value 5"<<endl;
  inorder(root);
  cout<<endl;
    return 0;
}
current inorder traversal of tree
3 4 5 6 7 8
inorder traversal after deleting node with value 5
3 4 6 7 8

Екілік іздеу ағашын жою операциясына арналған Java коды

import java.util.*;
// Class that denotes a node of the tree
class node
{ 
    int data; 
    node left, right, random; 
  
    public node(int data) 
    { 
        this.data = data;
        left = right = random = null; 
    } 
}

class Tree 
{ 
    static node root;
  static node create(int data) {
    node tmp = new node(data);
    return tmp;
  }

  static void inorder(node root){
    if(root != null){
      inorder(root.left);
      System.out.print(root.data + " ");
      inorder(root.right);
    }
  }

  // return the node which is in the most left direction of root
  // the smallest node in the entire subtree rooted at current node
  static node minNode(node root) 
  {
    node tmp = root;
    while(tmp != null && tmp.left != null)
      tmp = tmp.left;
    return tmp;
  }
    
  // deleted the node with given data from tree
  static node deleteNode(node root, int data) 
  {
    // if current node is empty return current node(NULL)
    if(root == null) return root;
    	// node to be deleted is in left sub-tree
      if (data < root.data)
          root.left = deleteNode(root.left, data); 
    	// node to be delted in right sub-tree
      else if (data > root.data) 
          root.right = deleteNode(root.right, data); 
      // current node is node to be deleted
      else
      { 
          // Case 1 + Case 2
          // if left is null this means that it is either of the two cases
          if (root.left == null) 
          { 
              return root.right;
          } 
          // Case 2 node has a left child but not right child
          // thus it has only a single child
          else if (root.right == null)
          { 
              return root.left;
          }
    		// Case 3
    		// first find the successor
    		// successor is the element which comes next in inorder traversal of BST
    		// so it is the node in most left direction in right sub-tree
          node successor = minNode(root.right);
          // place successor in place of current node
          root.data = successor.data;
          // now simply delete the successor from root's right child
          root.right = deleteNode(root.right, successor.data); 
      } 
      return root; 
  }

  public static void main(String[] args) 
  {
    root = create(7);
    root.left = create(5);
    root.right = create(8);
    root.left.left = create(3);
    root.left.left.right = create(4);
    root.left.right = create(6);
    System.out.println("current inorder traversal of tree");
    inorder(root);
    System.out.println();
    root = deleteNode(root, 5);
    System.out.println("inorder traversal after deleting node with value 5");
    inorder(root);
    System.out.println();
  }
}
current inorder traversal of tree
3 4 5 6 7 8 
inorder traversal after deleting node with value 5
3 4 6 7 8 

Күрделілікті талдау

Уақыттың күрделілігі

O (N), жою үшін. Оң және оң жақ балалары бар ағаштың түбірін жою керек деп есептеңіз. Ал дұрыс балалар - тамырдың бірден оң жақ баласынан кейін солға қарай қисайған ағаш. Сонымен, бұл жою операциясын сызықтық уақыттың күрделілігінде орындайды.

Ғарыштың күрделілігі

O (1), жою кезінде. Біз ешқандай ақпарат сақтамадық, осылайша тұрақты кеңістікті алгоритмге айналдырамыз.

Жоғарыда аталған тәсілге оңтайландыру бар, бірақ ол O (N) уақытты алады. Біз әр түрлі түйіннің ата-анасын сақтап, инерциалды траверсал жасай аламыз. Осылайша, мұрагерді жою қажет болғанда, біз оның ата-анасының сол немесе оң баласын сәйкесінше нөлге ауыстырамыз. Бірақ бұл тәсіл O (N) кеңістігін алады және ең нашар уақыт күрделілігіне әсер етпейді.