두 갈래 나무_두 갈래 검색 트리_두 갈래 정렬 트리

두 갈래 정렬 트리는 두 갈래 찾기 트리, 두 갈래 검색 트리라고도 부른다.두 갈래 정렬 트리는 일반적인 두 갈래 나무와 구조적으로 같다. 그것은 빈 나무이거나 이런 두 갈래 나무이다. 임의의 결점에 대해 왼쪽 나무가 비어 있지 않으면 왼쪽 나무의 모든 결점의 값은 이 결점의 값보다 작다.오른쪽 트리가 비어 있지 않으면 오른쪽 트리의 모든 결점의 값이 이 결점의 값보다 크다.임의의 결점의 왼쪽 나무와 오른쪽 나무는 모두 두 갈래 정렬 나무이다.일반적으로 두 갈래 정렬 트리의 결점 값은 모두 유일하다.
두 갈래 정렬 트리에서 임의의 결점에 대해 왼쪽 트리와 오른쪽 트리가 있으면 왼쪽 트리의 결점 값은 오른쪽 트리의 결점 값보다 작다.
만약 중간 순서가 두 갈래 정렬 트리를 두루 돌아다니면, 작은 순서에서 큰 순서를 얻을 수 있다.
두 갈래 정렬 트리의 삽입과 검색 효율이 상대적으로 높고 최악의 경우 시간 복잡도는 O(n)이고 기대하는 시간 복잡도는 O(logn)이며 그 중에서 n은 트리의 결점 총 개수이다.
아까 저희가 두 갈래 정렬 트리의 최악의 경우 시간 복잡도가 O(n)라고 언급했는데 왜 그래요?최악의 경우 두 갈래 정렬 트리는 체인 테이블로 퇴화되어 뿌리 결점에서 왼쪽으로 차례로 감소하거나 뿌리 결점에서 오른쪽으로 차례로 증가한다.그럼 어떤 방법으로 이 문제를 해결할 수 있습니까?두 갈래 정렬 트리를 바탕으로 최적화를 해서 AVL 트리, 빨간색, 검은색 트리, SBT, Splay 등으로 만들 수 있다. 이런 고급 트리 구조는 위의 문제를 해결했고 삽입과 검색의 효율은 모두 O(logn)이다.

불완전 버전 구현:

#include<iostream>
using namespace std;
class Node {
public:
    int data;
    Node *lchild, *rchild, *father;
    Node(int _data, Node *_father = NULL) {
        data = _data;
        lchild = NULL;
        rchild = NULL;
        father = _father;
    }
    ~Node() {
        if (lchild != NULL) {
            delete lchild;
        }
        if (rchild != NULL) {
            delete rchild;
        }
    }
    void insert(int value) {
        if (value == data) {
            return;
        } else if (value > data) {
            if (rchild == NULL) {
                rchild = new Node(value, this);
            } else {
                rchild->insert(value);
            }
        } else {
            if (lchild == NULL) {
                lchild = new Node(value, this);
            } else {
                lchild->insert(value);
            }
        }
    }
    Node* search(int value) {
        if (data == value) {
            return this;
        } else if (value > data) {
            if (rchild == NULL) {
                return NULL;
            } else {
                return rchild->search(value);
            }
        } else {
            if (lchild == NULL) {
                return NULL;
            } else {
                return lchild->search(value);
            }
        }
    }
    Node* predecessor() {
        Node *temp = lchild;
        while (temp != NULL && temp->rchild != NULL) {
            temp = temp->rchild;
        }
        return temp;
    }
    Node* successor() {
        Node *temp = rchild;
        while (temp != NULL && temp->lchild != NULL) {
            temp = temp->lchild;
        }
        return temp;
    }
    void remove_node(Node* delete_node){
        Node* temp=NULL;
        //temp （0 /1 ） ， 
        if(delete_node->lchild!=NULL){
            temp=delete_node->lchild;
            temp->father=delete_node->father;
            delete_node->lchild=NULL;
        }
        if(delete_node->rchild!=NULL){
            temp=delete_node->rchild;
            temp->father=delete_node->father;
            delete_node->rchild=NULL;
        }
        // 
        // 
        if(delete_node->father->lchild==delete_node){
            delete_node->father->lchild=temp;
        }
        else{
            delete_node->father->rchild=temp;
        }
        delete delete_node;
    }
};
class BinaryTree {
private:
    Node *root;
public:
    BinaryTree() {
        root = NULL;
    }
    ~BinaryTree() {
        if (root != NULL) {
            delete root;
        }
    }
    void insert(int value) {
        if (root == NULL) {
            root = new Node(value);
        } else {
            root->insert(value);
        }
    }
    bool find(int value) {
        if (root->search(value) == NULL) {
            return false;
        } else {
           return true;
        }
    }
};
int main() {
    BinaryTree binarytree;
    int arr[10] = { 8, 9, 10, 3, 2, 1, 6, 4, 7, 5 }; for (int i = 0; i < 10; i++) { binarytree.insert(arr[i]); } int value; cin >> value; if (binarytree.find(value)) { cout << "search success!" << endl; } else { cout << "search failed!" << endl; } return 0; } 

두 갈래 나무의 기본 조작 완전판

#include<iostream>
using namespace std;
class Node {
public:
    int data;
    Node *lchild, *rchild, *father;
    Node(int _data, Node *_father = NULL) {
        data = _data;
        lchild = NULL;
        rchild = NULL;
        father = _father;
    }
    ~Node() {
        if (lchild != NULL) {
            delete lchild;
        }
        if (rchild != NULL) {
            delete rchild;
        }
    }
    void insert(int value) {
        if (value == data) {
            return;
        } else if (value > data) {
            if (rchild == NULL) {
                rchild = new Node(value, this);
            } else {
                rchild->insert(value);
            }
        } else {
            if (lchild == NULL) {
                lchild = new Node(value, this);
            } else {
                lchild->insert(value);
            }
        }
    }
    Node* search(int value) {
        if (data == value) {
            return this;
        } else if (value > data) {
            if (rchild == NULL) {
                return NULL;
            } else {
                return rchild->search(value);
            }
        } else {
            if (lchild == NULL) {
                return NULL;
            } else {
                return lchild->search(value);
            }
        }
    }
    Node* predecessor() {
        Node *temp = lchild;
        while (temp != NULL && temp->rchild != NULL) {
            temp = temp->rchild;
        }
        return temp;
    }
    Node* successor() {
        Node *temp = rchild;
        while (temp != NULL && temp->lchild != NULL) {
            temp = temp->lchild;
        }
        return temp;
    }
    void remove_node(Node *delete_node) {
        Node *temp = NULL;
        if (delete_node->lchild != NULL) {
            temp = delete_node->lchild;
            temp->father = delete_node->father;
            delete_node->lchild = NULL;
        }
        if (delete_node->rchild != NULL) {
            temp = delete_node->rchild;
            temp->father = delete_node->father;
            delete_node->rchild = NULL;
        }
        if (delete_node->father->lchild == delete_node) {
            delete_node->father->lchild = temp;
        } else {
            delete_node->father->rchild = temp;
        }
        delete delete_node;
    }

    // ， 2 
    bool delete_tree(int value){
        Node *delete_node,*current_node;
        current_node=search(value);
        if(current_node==NULL){
            return false;   
        }
        if(current_node->lchild!=NULL){
            // ， ， 
           delete_node=current_node->predecessor();
        }
        else if(current_node->rchild!=NULL){
            // ， ， 
            delete_node=current_node->successor();   
        }
        else{
            delete_node=current_node;   
        }
        current_node->data=delete_node->data;
        remove_node(delete_node);
        return true;
    }

};
class BinaryTree {
private:
    Node *root;
public:
    BinaryTree() {
        root = NULL;
    }
    ~BinaryTree() {
        if (root != NULL) {
            delete root;
        }
    }
    void insert(int value) {
        if (root == NULL) {
            root = new Node(value);
        } else {
            root->insert(value);
        }
    }
    bool find(int value) {
        if (root->search(value) == NULL) {
            return false;
        } else {
           return true;
        }
    }
    bool delete_tree(int value){
        return root->delete_tree(value);
    }
};
int main() {
    BinaryTree binarytree;
    int arr[10] = { 8, 9, 10, 3, 2, 1, 6, 4, 7, 5 }; for (int i = 0; i < 10; i++) { binarytree.insert(arr[i]); } int value; cin >> value; if (binarytree.find(value)) { cout << "search success!" << endl; } else { cout << "search failed!" << endl; } cin>>value; if (binarytree.delete_tree(value)) { cout << "delete success!" << endl; } else { cout << "delete failed!" << endl; } return 0; }