데이터 구조 - 4 자체 균형 이 진 트 리 (AVL)

간단 한 자기 평형 이 진 트 리 구현 (AVL)
이 진 트 리 (BST) 구현 에 고도 균형 회전 추가
구조 체 노드: 왼쪽 결점 left, 오른쪽 결점 right, 데이터 data, 고도 height 류 BST: 뿌리 결점 root
주요 기능 은 균형 회전, 추가, 삭제, 조회, 옮 겨 다 니 기 (앞 순서 옮 겨 다 니 기, 중간 순서 옮 겨 다 니 기, 뒤 순서 옮 겨 다 니 기, 층 차 옮 겨 다 니 기, 깊이 우선 검색, 넓이 우선 검색), 높이 계산 등 이 있다.
시간 복잡 도: 1. 밸 런 스 회전 은 좌우 나무 뿌리 노드 의 높이 를 비교 하고 시간 복잡 도 는 O (1) 2 이 며 시간 복잡 도 를 O (logn) 로 추가 합 니 다. 최대 두 번 의 단일 회전 (같은 곳) 3. 삭제 시간 복잡 도 는 O (logn) 이 고 여러 번 회전 하 며 뿌리 까지 가능 합 니 다.
이 진 트 리 의 삭제 과정 을 간단하게 설명 하면 다음 과 같은 네 가지 상황 으로 나 눌 수 있 습 니 다. a) 삭제 할 노드 는 좌우 아이 가 없습니다. b) 삭제 할 노드 는 왼쪽 아이 (왼쪽 노드 로 대체) 만 삭제 할 노드 는 오른쪽 아이 (오른쪽 노드 로 대체) 만 삭제 할 노드 는 좌우 아이 (후계 노드 로 대체) 가 있 습 니 다.
저 는 삭 제 된 노드 대신 후계 노드 를 사용 하지 않 고 좌우 두 개의 서브 트 리 높이 에 따라 전 계 노드 나 후계 노드 를 선택 합 니 다. 결점 이상 의 회전 작업 을 삭제 할 필요 가 없 기 때문에 두 가지 상황 만 있 습 니 다. a) 삭제 할 노드 는 좌우 아이 가 없습니다. b) 삭제 할 노드 는 아이 가 있 습 니 다 (좌우 두 개의 서브 트 리 높이 에 따라 전 계 노드 나 후계 노드 를 선택 합 니 다)
4. 조회 시간 복잡 도 는 O (logn) 5 이 고 전체 노드 를 옮 겨 다 니 며 시간 복잡 도 는 O (n) 6 이 며 높이 계산 은 AVL 트 리 가 노드 높이 를 유지 하기 때문에 루트 노드 높이 로 돌아 가 고 시간 복잡 도 는 O (1) 이다.
요약: 1. 이 진 트 리 알고리즘 의 핵심 은 재 귀 입 니 다. 이 진 트 리 를 실현 하 는 모든 기능 은 재 귀 를 통 해 2 를 실현 할 수 있 습 니 다. 앞 순 서 는 dfs 의 한 종류 입 니 다. BFS 는 바로 층 차 를 옮 겨 다 니 는 것 입 니 다. 대열 의 특징 으로 4 를 실현 할 수 있 습 니 다. 중간 순 서 는 이 진 트 리 의 결점 이 어 릴 때 부터 큰 순 서 를 5 까지 계산 할 수 있 습 니 다. 높이 계산 은 앞 순 서 를 통 해 6 을 실현 하고 모든 분기 의 절반 을 재 귀 처리 할 수 있 습 니 다.이분법 과 유사 하여 감 치 법 또는 분 치 법 에 속 하 며 분 치 법의 주 정리 로 T (n) = aT (n / b) + f (n), f (n) 8712 ° O (nd) 를 계산 합 니 다. 여기 a = 1, b = 2, d = 0, a = bd 를 계산 합 니 다. 따라서 T (n) 8712 ° O (ndlogn) = O (logn) 7, AVL 나 무 는 결점 높이 를 유지 함으로써 균형 요 소 를 계산 합 니 다. 각 층 의 재 귀 는 좌우 서브 트 리 높이 (O (n) 를 계산 할 필요 가 없습니다.그렇지 않 으 면 결점 을 추가 하고 삭제 하 는 시간의 복잡 도 는 모두 O (nlogn) 이다.

#include
#include//  max  
#include
using namespace std;

template<typename T>
struct Node {
	Node<T>* left;
	Node<T>* right;
	T data;
	int height;
	Node(T val) :data(val), height(1),left(nullptr), right(nullptr) {}
};

template<typename T>
class AVL {
private:
	Node<T>* root;

	//     ：   、   、    、    
	Node<T>* insert_rotate(Node<T>* root, T val, int lr) {
		if (lr == 0) {
			if (rheight(root->left) - rheight(root->right) == 2) {
				if (root->left->data >val)
					root = rightRotate(root);
				else root = lrRotate(root);
			}
		}
		else {
			if (rheight(root->right) - rheight(root->left) == 2) {
				if (root->right->data < val)
					root = leftRotate(root);
				else root = rlRotate(root);
			}
		}
		return root;
	}

	Node<T>* delete_rotate(Node<T>* root, T val, int lr) {
		if (lr == 1) {
			if (rheight(root->left) - rheight(root->right) == 2) {
				if (root->left->data > val)
					root = rightRotate(root);
				else root = lrRotate(root);
			}
		}
		else {
			if (rheight(root->right) - rheight(root->left) == 2) {
				if (root->right->data < val)
					root = leftRotate(root);
				else root = rlRotate(root);
			}
		}
		return root;
	}

	Node<T>* rightRotate(Node<T>* root) {
		Node<T>* rleft = root->left;
		root->left = rleft->right;
		rleft->right = root;
		root->height = max(rheight(root->left), rheight(root->right)) + 1;
		rleft->height = max(rheight(rleft->left), rheight(rleft->right)) + 1;
		return rleft;
	}
	Node<T>* leftRotate(Node<T>* root) {
		Node<T>* rright = root->right;
		root->right = rright->left;
		rright->left = root;
		root->height = max(rheight(root->left), rheight(root->right)) + 1;
		rright->height = max(rheight(rright->left), rheight(rright->right)) + 1;
		return rright;
	}
	Node<T>* lrRotate(Node<T>* root) {
		root->left = leftRotate(root->left);
		return rightRotate(root);
	}
	Node<T>* rlRotate(Node<T>* root) {
		root->right = rightRotate(root->right);
		return leftRotate(root);
	}

	//      
	Node<T>* insert(Node<T>* root, T val) {
		if (root) {
			if (root->data > val) {
				root->left = insert(root->left, val);
				root->height = max(rheight(root->left), rheight(root->right)) + 1;
				root = insert_rotate(root, val, 0);
				return root;
			}
			if (root->data < val) {
				root->right = insert(root->right, val);
				root->height = max(rheight(root->left), rheight(root->right)) + 1;
				root = insert_rotate(root, val, 1);
				return root;
			}
			return nullptr;
		}
		return new Node<T>(val);
	}

	//      
	Node<T>* del(Node<T>* root, T val) {
		if (root) {
			if (root->data > val) {
				root->left = del(root->left, val);
				if(root->left)
				root->left->height= max(rheight(root->left->left), rheight(root->left->right)) + 1;
				root->height = max(rheight(root->left), rheight(root->right)) + 1;
				if (root->right) {
					if (root->right->right)
						root = delete_rotate(root, root->right->right->data, 0);
				}
			}
			else if (root->data < val) {
				root->right = del(root->right, val);
				if (root->right)
				root->right->height = max(rheight(root->right->left), rheight(root->right->right)) + 1;
				root->height = max(rheight(root->left), rheight(root->right)) + 1;
				if (root->left) {
					if (root->left->left)
						root = delete_rotate(root, root->left->left->data, 1);
				}
			}
			else {
				Node<T>* r = nullptr;
				if (root->left || root->right) {
					r = root;
					if (rheight(root->left) > rheight(root->right)) {
						Node<T>* left = r->left;
						int i;
						for (i = 0; left->right != nullptr; i++) {
							left = left->right;
							if (i)
								r = r->right;
							else r = r->left;
						}
						if (i) {
							r->right = left->left;
							if (root)
								del(root, left->data);
							left->right = root->right;
							left->left = root->left;
						}
						else left->right = root->right;
						r = left;

					}
					else {
						Node<T>* right = r->right;
						int i;
						for (i = 0; right->left != nullptr;i++) {
							right = right->left;
							if (i)
								r = r->left;
							else r = r->right;
						}

						if (i) {
							r->left = right->right;
							if (root)
								del(root, right->data);
							right->right = root->right;
							right->left = root->left;
						}
						else right->left = root->left;
						r = right;
					}
				}
				root->left = nullptr;
				root->right = nullptr;
				root = r;

			}
			return root;
		}
		return nullptr;
	}

	//      
	bool find(Node<T>* root, T val) {
		if (root) {
			if (root->data == val)
				return true;
			if (root->data > val)
				return find(root->left, val);
			else return find(root->right, val);
		}
		return false;
	}

	//      ：    、    、    
	void preOrder(Node<T>* root) {
		if (root) {
			cout << root->data;
			preOrder(root->left);
			preOrder(root->right);
		}
	}
	void inOrder(Node<T>* root) {
		if (root) {
			inOrder(root->left);
			cout << root->data;
			inOrder(root->right);
		}
	}
	void postOrder(Node<T>* root) {
		if (root) {
			postOrder(root->left);
			postOrder(root->right);
			cout << root->data;
		}
	}

	int rheight(Node<T>* node) {
		if (node)
			return node->height;
		return 0;
	}

public:
	AVL(T val) { root = new Node<T>(val); }
	~AVL() {}

	//  
	bool insert(T val) {
		Node<T>* p = insert(root, val);
		if (p) {
			root = p;
			return true;
		}
		return false;
	}

	//  
	bool del(T val) {
		Node<T>* p = del(root, val);
		root->height = max(rheight(root->left), rheight(root->right)) + 1;
		if (p) {
			root = p;
			return true;
		}
		return false;
	}

	//  
	bool find(T val) {
		return find(root, val);
	}

	//  ：    （dfs）、    、    、    （bfs）
	//    
	void preOrder() {
		preOrder(root);
		cout << endl;
	}
	//    
	void inOrder() {
		inOrder(root);
		cout << endl;
	}
	//    
	void postOrder() {
		postOrder(root);
		cout << endl;
	}
	//    
	void levelOrder() {
		if (root) {
			vector<Node<T>*> nodes;
			nodes.push_back(root);
			int n = 1;
			for (int i = 0; i < n; i++) {
				cout << nodes[i]->data;
				if (nodes[i]->left) {
					nodes.push_back(nodes[i]->left);
					n++;
				}
				if (nodes[i]->right) {
					nodes.push_back(nodes[i]->right);
					n++;
				}
			}
		}
		cout << endl;
	}
	//      
	void dfs() { preOrder(); }
	//      
	void bfs() { levelOrder(); }

	int height() { return root->height; }
};


int main() {
	AVL<int> avl(4);
	//    
	cout << "----------    ----------" << endl;
	cout << "    ：";
	avl.preOrder();
	avl.insert(2);
	cout << "    ：";
	avl.preOrder();
	avl.insert(6);
	cout << "    ：";
	avl.preOrder();
	avl.insert(1);
	cout << "    ：";
	avl.preOrder();
	avl.insert(3);
	cout << "    ：";
	avl.preOrder();
	avl.insert(7);
	cout << "    ：";
	avl.preOrder();
	avl.insert(5);
	cout << "    ：";
	avl.preOrder();
	avl.insert(8);
	cout << "    ：";
	avl.preOrder();

	/*
		   4
		 ↙	↘
		2     6
	  ↙ ↘ ↙ ↘
	  1   3 5   7
			     ↘
			      8
	*/

	//      
	cout << "----------      ----------" << endl;
	avl.insert(9);
	cout << "    ：";
	avl.preOrder();
	/*
		   4
		 ↙	↘
		2     6
	  ↙ ↘ ↙ ↘
	  1   3 5   8
			  ↙ ↘
			  7   9
	*/

	//    
	cout << "----------    ----------" << endl;
	cout << "    ：";
	avl.preOrder();
	cout << "    ：";
	avl.inOrder();
	cout << "    ：";
	avl.postOrder();
	cout << "    ：";
	avl.levelOrder();
	cout << "      ：";
	avl.dfs();
	cout << "      ：";
	avl.bfs();

	//      
	cout << "----------      ----------" << endl;
	cout << "height:" << avl.height() << endl;

	//    
	cout << "----------    ----------" << endl;
	cout << "  4：" << avl.del(4) << endl;
	cout << "    ：";
	avl.preOrder();

	//    
	cout << "----------    ----------" << endl;
	cout << "  7：" << avl.find(7) << endl;
}

테스트 용례 를 동봉 합 니 다. 만약 잘못 되 었 다 면, 큰 사람 이 orz 를 지적 해 주 십시오.