두 갈래 트리 시리즈 - 두 갈래 검색 트리 - 선형 시간 내에 질서 체인 테이블을 BST로 전환

인용문

이 문서는 Google의 제목입니다.
how to merge two binary search tree into balanced binary search tree. how to merge two binary search tree into balanced binary search tree.. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time and do it in place.
http://www.careercup.com/question?id=5261732222074880
 
선형 시간 내에 완성해야 하고 inplace를 요구하면 BST를 Double linked list로 전환할 생각을 하기 어렵지 않다.
그리고 두 개의dllmerge를그러나 선형 시간의 복잡도가 있는 알고리즘이 dll을 BST로 바꿉니까?
다음은 본고에서 기술하고자 하는 내용입니다. 알고리즘은
http://www.geeksforgeeks.org/in-place-conversion-of-sorted-dll-to-balanced-bst/
 

정렬된 Double linked list가 BST로 변환됨

선형 시간이 필요하기 때문에 DLL의 모든 노드가 consant에만 접근할 수 있도록 보증해야 합니다. 가장 좋은 것은 한 번입니다.
모든 노드에 한 번만 접근할 수 있도록 요구하는 이상 뿌리 노드에서 구조하는 것은 틀림없이 안 된다.이런 알고리즘은 BST를 잎 노드부터 구성하게 하고 유연하게 귀속을 운용함으로써 BST를 밑바닥에서 위로 구성하는 과정을 교묘하게 실현했고 BST가 균형적이라는 것을 보장할 수 있다.

#include<iostream>
#include<stack>
using namespace std;

struct BSTNode{
    int val;
    BSTNode *left;
    BSTNode *right;
    BSTNode(int v): val(v), left(NULL), right(NULL){}
};

class BSTtoDLL{
    public:
        BSTNode *func(BSTNode *root){
            BSTtoDLLCore(root);
            return head;
        }

    private:
        BSTNode* pre = NULL;
        BSTNode* head = NULL;
        void BSTtoDLLCore(BSTNode *root){
            if(!root) return;
            BSTtoDLLCore(root -> left);
            if(pre){
                pre -> right = root;
                root -> left = pre;
            }else{
                head = root;
            }
            pre = root;
            BSTtoDLLCore(root -> right);
        }
};

class DLLtoBalancedBST{ public: BSTNode* func(BSTNode* head){ if(!head) return head; int n = 0; for(BSTNode *p = head; p; ++n, p = p -> right); return DLLtoBalancedBSTCore(&head, n); } private: //DLL to BST in place, Time O(N), Space O(LogN) for stack, N is the amount of nodes. //DLL needs to be sorted.
        BSTNode* DLLtoBalancedBSTCore(BSTNode** headref, int n){ if(n == 0) return NULL; BSTNode* left = DLLtoBalancedBSTCore(headref, n/2); BSTNode *root = *headref; root -> left = left; *headref = root -> right; root -> right = DLLtoBalancedBSTCore(headref, n-n/2-1); return root; } }; void InorderPrint(BSTNode* root){
    if(!root) return;
    stack<BSTNode *> st;
    while(!st.empty() || root){
        if(!root){
            root = st.top();
            st.pop();
            cout << root -> val << ' ';
            root = root -> right;
        }else{
            st.push(root);
            root = root -> left;
        }
    }
    cout << endl;
}


int main(){
    
    //Construct oringal BST
    BSTNode *root = new BSTNode(5);
    BSTNode *left3 = new BSTNode(3);
    BSTNode *left1 = new BSTNode(1);
    BSTNode *left2 = new BSTNode(2);
    BSTNode *right6 = new BSTNode(6);
    BSTNode *right7 = new BSTNode(7);
    
    root -> left = left2;
    left2 -> left = left1;
    left2 -> right = left3;
    root -> right = right7;
    right7 -> left = right6;
    
    cout << "-------Inorder print BST-------
";
    InorderPrint(root);

    //Convert BST to DLL
    BSTtoDLL bstdll;
    BSTNode *head = bstdll.func(root);
    BSTNode *p = head;
    cout << "-------print converted double linked list----------
";
    for(; p->right != NULL; cout << p -> val << ' ', p = p -> right);
    cout << endl;
    for(; p != NULL; cout << p -> val << ' ', p = p -> left);
    cout << endl;

    //Convert DLL back to Balenced BST
    DLLtoBalancedBST dllbst;
    BSTNode *con_root = dllbst.func(head);
    cout << "-------Inorder print converted BST-------
";
    InorderPrint(con_root);

    return 0;
}

하이라이트 부분은 전환 과정이다.
매번 귀속될 때마다headdr라는 노드를 가리키는 바늘이 끝으로 한 번 이동합니다.따라서 모든 노드는 한 번만 방문하고 시간의 복잡도는 선형이다.
우리는 이런 알고리즘이 단방향 체인표에도 적용된다는 것을 발견할 수 있다.물론 단사슬표는 inplace를 보장할 수 없고 반드시 노드를 새로 설명해야 하지만 시간의 복잡도는 여전히 선형이다.
다음은 단방향 체인표의 실현을 제시한다.
 

정렬된 단방향 Linked list가 BST로 변환됨

#include<iostream>
#include<stack>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int v): val(v), next(NULL){}
};

struct BSTnode{
    int val;
    BSTnode* left;
    BSTnode* right;
    BSTnode(int v): val(v), left(NULL), right(NULL){}
};

BSTnode *LLtoBSTCore(ListNode **headaddr, int n){ if(n <= 0) return NULL; BSTnode *left = LLtoBSTCore(headaddr, n/2); BSTnode *root = new BSTnode((*headaddr) -> val); root -> left = left; *headaddr = (*headaddr) -> next; root -> right = LLtoBSTCore(headaddr, n-n/2-1); return root; } BSTnode *LLtoBST(ListNode *head){ if(!head) return NULL; int n = 0; ListNode *p = head; for(; p; ++n, p = p -> next); return LLtoBSTCore(&head, n); } int main(){
    ListNode *head = new ListNode(1);
    ListNode *end = head;
    for(int i = 2; i <= 9; end -> next = new ListNode(i++), end = end -> next);
    cout << "List: 
";
    for(ListNode *p = head; p; cout << p -> val << ' ', p = p -> next);
    cout << endl;

    BSTnode *root = LLtoBST(head);

    cout << "BST inorder: " << endl;
    stack<BSTnode *> st;
    while(!st.empty() || root){
        if(!root){
            root = st.top();
            st.pop();
            cout << root -> val << " ";
            root = root -> right;
        }else{
            st.push(root);
            root = root -> left;
        }
    }
    cout << endl;
    
}

하이라이트 부분은 전환 과정이다.
 

정렬된 시퀀스에 대한 Iterator, 시퀀스를 BST로 변환

다시 미루어 보면 넥스트로만 이동할 수 있는 iterator를 지정하면 이 알고리즘을 통해iterator가 지나간 노드를 BST로 구성할 수 있다.그러나 우리는 사전에 알고 있거나 서열의 길이를 계산해 냈다.
여기서 C#의 구현 코드를 제공합니다.IENumerator는 MoveNext () 를 지원하는 교체기입니다. - 교체기를 뒤로 옮기고, Current 속성 - 교체기가 현재 가리키는 값을 되돌려줍니다.
강조 부분은 IENumrator 기반 구조 프로세스입니다.
인터페이스 IENumerator가 아니기 때문이다.NET CLR의 primitive type(기원 유형)은 IENumerator에 값을 부여하거나 함수 매개 변수로 사용할 때 인용에 따라 전달됩니다. 이것이 바로 우리가 필요로 하는 것입니다.따라서 C#의 구현 코드는 C++에서 두 개의 **를 사용하는 번거로움을 줄였다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    public class BSTNode<T>
    {
        public T val;
        public BSTNode<T> left;
        public BSTNode<T> right;
        public BSTNode(T v)
        {
            val = v;
            left = null;
            right = null;
        }
    }

    /// <summary>
    /// Build Binary search tree from given iterator
    /// </summary>
    public class BuildBST
    {
        public BSTNode<T> BuildFromIEt<T>(IEnumerator<T> it, int n)
        {
            if (n == 0) return null; BSTNode<T> left = BuildFromIEt(it, n / 2); it.MoveNext(); BSTNode<T> node = new BSTNode<T>(it.Current); node.left = left; node.right = BuildFromIEt(it, n - n / 2 - 1); return node;
        }
    }

    /// <summary>
    /// A class to out put nodes in a tree
    /// </summary>
    public class TreeTrav
    {
        public static void Inorde<T>(BSTNode<T> root)
        {
            if (root == null) return;
            Stack<BSTNode<T>> st = new Stack<BSTNode<T>>();
            while (root != null || st.Count > 0)
            {
                if (root == null)
                {
                    root = st.Peek();
                    st.Pop();
                    Console.Write(root.val.ToString() + ' ');
                    root = root.right;
                }
                else
                {
                    st.Push(root);
                    root = root.left;
                }
            }
            Console.WriteLine();
        }
    }

    class Program
    {

        static void Main(string[] args)
        {
            IEnumerable<int> list = new List<int>() { 1, 2, 3, 6, 7, 9 };

            Console.WriteLine("----Original list----");
            for (IEnumerator<int> it = list.GetEnumerator(); it.MoveNext(); Console.Write(it.Current.ToString() + ' ')) ;
            Console.WriteLine();

            BuildBST buildBST = new BuildBST();
            BSTNode<int> root = buildBST.BuildFromIEt(list.GetEnumerator(), list.Count());
            Console.WriteLine("----Inorder traverse generated BST----");
            TreeTrav.Inorde(root);
            Console.Read();
        }
    }
}