Хоёртын модны зангилааны залгамжлагч  


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Амазоны Expedia Morgan Stanley OYO өрөөнүүд Snapchat
Хоёртын хайлтын мод Мод

Асуудлын мэдэгдэл  

Асуудал нь "Хоёртын модон дахь зангилааны залгамжлагчийг" олохыг хүсч байна. Зангилааны inorder залгамжлагч нь өгөгдсөн хоёртын модны inorder хөндлөн огтлолын өгөгдсөн зангилааны дараа гарах хоёртын модны зангилаа юм.

Жишээ нь  

Pin  

Inorder successor of 6 is 4

Тайлбар

Модны хөндлөн огтлол нь 9 7 1 6 4 5 3. Ийнхүү 1-ийн залгамж халаа нь 6 болно.

арга барил  

Ерөнхийдөө а-ийн хөндлөн огтлолын дараагийн зангилаа олохыг бидэнд хэлдэг хоёртын хайлтын мод. Гэхдээ энэ нь хоёртын модноос өөр юм. Тиймээс бид анхаарах ёстой нэг зүйл бол ерөнхий хоёртын модны хөндлөн огтлолцол нь өсөх дарааллаар биш юм. Одоо урагшаа явцгаая. Хэрэв бидэнд зангилаа байгаа бол 3 тохиолдлыг үзэх хэрэгтэй.

Бидний анхаарах ёстой 3 тохиолдол нь түүний зөв хүүхэдтэй холбоотой эсвэл одоогийн зангилаа өөрөө хамгийн баруун талын хүүхэдтэй холбоотой юм. Тэгэхээр зангилаа зөв хүүхэдтэй бол. Дараа нь inorder залгамжлагч бол түүний баруун дэд модны хамгийн зүүн талын хүүхэд юм. Гэхдээ энэ нь зөв хүүхэдгүй бол. Дараа нь өгөгдсөн зангилааны өвөөгийн зүүн дэд модонд байхаар өгөгдсөн зангилааны хамгийн доод өвөгдлийг ол. Үүнийг хийхийн тулд зангилааг рекурсив байдлаар хайж олоод рекурсионоос буцахдаа зүүн чиглэлийг сонгосон газраас эцэг эхэд хадгална.

мөн үзнэ үү
Хамгийн ойрхон Палиндромын дугаарыг олох

Одоо сүүлчийн тохиолдол бол зангилаа нь хамгийн зөв хүүхэд юм. Хэрэв ийм зүйл тохиолдвол зангилааны залгамж халаа байхгүй болно.

код  

Хоёртын модон дахь зангилааны залгамжлагчийг олох 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;
  return tmp;
}

node* findLeftMostNode(node* root){
  while(root && root->left) root = root->left;
  return root;
}

node* findRightMostNode(node* root){
  while(root && root->right) root = root->right;
  return root;
}

node* findAncestorSuccessor(node* root, node* given)
{
  if(root){
    if(root == given)
      return root;
    node* tmp = findAncestorSuccessor(root->left, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
    tmp = findAncestorSuccessor(root->right, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
  }
    return NULL;
}

void findInorderSuccesor(node* root, node* given)
{
    // if right child exists
    if(given->right)
    {
    	node* leftmost = findLeftMostNode(given);
    	cout<<"Inorder Succesor of "<<given->data<<" is "<<leftmost->data;
    	return;
    }
    // if right child does not exists
    if(given->right == NULL)
    {
        node* rightmost = findRightMostNode(root);
        if(rightmost == given)
            cout<<"Inorder Successor does not exists";
        else
        	findAncestorSuccessor(root, given);
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);
  findInorderSuccesor(root, root->left->right->left);
}
Inorder Successor of 1 is 6

Хоёртын модон дахь зангилааны залгамжлагчийг олох Java код

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static node findLeftMostNode(node root){
    while(root != null && root.left != null) root = root.left;
    return root;
  }

  static node findRightMostNode(node root){
    while(root != null && root.right != null) root = root.right;
    return root;
  }

  static node findAncestorSuccessor(node root, node given)
  {
    if(root != null){
      if(root == given)
        return root;
      node tmp = findAncestorSuccessor(root.left, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
      tmp = findAncestorSuccessor(root.right, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
    }
      return null;
  }

  static void findInorderSuccesor(node root, node given)
  {
      // if right child exists
      if(given.right != null)
      {
      	node leftmost = findLeftMostNode(given);
      	System.out.print("Inorder Successor of "+given.data+" is "+leftmost.data);
      	return;
      }
      // if right child does not exists
      else
      {
          node rightmost = findRightMostNode(root);
          if(rightmost == given)
              System.out.print("Inorder Successor does not exists");
          else
          	findAncestorSuccessor(root, given);
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);
    findInorderSuccesor(root, root.left.right.left);
  }
}
Inorder Successor of 1 is 6

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N), учир нь хамгийн хэцүү тохиолдолд бид бүх зангилаа дээгүүр өнгөрөх шаардлагатай болдог.

мөн үзнэ үү
Хоёртын хайлтын модыг тайрч ав

Сансрын нарийн төвөгтэй байдал

O (H), яагаад гэвэл бид рекурсийг ашигласан. Тиймээс хөрвүүлэгч стекийн авсан зайг авч үзвэл. Сансрын нарийн төвөгтэй байдал нь модны өндрөөс хамаарна.