AVLTree(C++구현)의 일괄 회전 동작 에 대한 문제 가 없습니다.
대학 선생님 은 비교적 간단 한 데이터 구조 와 알고리즘 만 말씀 하 십 니 다.이런 고급 데이터 구 조 는 스스로 공부 하고 실천 해 야 합 니 다.
예전 에 AVLTree 라 는 말 만 들 었 어 요.저 는 책 을 읽 고 원 리 를 알 아 보고 조금씩 적어 서 디 버 깅 하 는 데 3 일 정도 걸 렸 어 요.꽤 오래 됐 을 거 야.
일반적인 상황 에서 AVL 트 리 는 제 가 직접 쓰 지 않 지만 이미 실 현 된 코드 를 제 가 나중에 알고리즘 이 실 현 된 근 거 를 되 돌아 보기 위해 저 는 자신 에 게 독 하 게 그것 을 실현 하기 로 결 정 했 습 니 다.
아래 코드 는 모두 C++11 기준 을 사용한다.
ubuntu 18.04 에서 컴 파일 과 디 버 깅 을 거 쳤 습 니 다.
/*
* BinarySearchTree.h
* 1.
* 2. ， ， ，
* 3. AVL ， LL,LR,RR,RL
* Created on: 2020 1 29
* Author: LuYonglei
*/
#ifndef SRC_BINARYSEARCHTREE_H_
#define SRC_BINARYSEARCHTREE_H_
#include <queue>
template<typename Element>
class BinarySearchTree {
public:
BinarySearchTree(int (*cmp)(Element e1, Element e2)); //
virtual ~BinarySearchTree();
int size(); //
bool isEmpty(); //
void clear() {
//
NODE *node = root_;
root_ = nullptr;
using namespace std;
queue<NODE*> q;
q.push(node);
while (!q.empty()) {
NODE *tmp = q.front();
if (tmp->left != nullptr)
q.push(tmp->left);
if (tmp->right != nullptr)
q.push(tmp->right);
delete tmp;
q.pop();
}
}
void add(Element e) {
//
add(e, cmp_);
}
void remove(Element e) {
//
remove(Node(e, cmp_));
}
bool contains(Element e) {
//
return Node(e, cmp_) != nullptr;
}
void preorderTraversal(bool (*visitor)(Element &e)) {
//
if (visitor == nullptr)
return;
bool stop = false; // ， stop true，
preorderTraversal(root_, stop, visitor);
}
void inorderTraversal(bool (*visitor)(Element &e)) {
//
if (visitor == nullptr)
return;
bool stop = false; // ， stop true，
inorderTraversal(root_, stop, visitor);
}
void postorderTraversal(bool (*visitor)(Element &e)) {
//
if (visitor == nullptr)
return;
bool stop = false; // ， stop true，
postorderTraversal(root_, stop, visitor);
}
void levelOrderTraversal(bool (*visitor)(Element &e)) {
// ，
if (visitor == nullptr)
return;
levelOrderTraversal(root_, visitor);
}
int height() {
//
return height(root_);
}
bool isComplete() {
//
return isComplete(root_);
}
private:
int size_;
typedef struct _Node {
Element e;
_Node *parent;
_Node *left;
_Node *right;
int height; //
_Node(Element e_, _Node *parent_) :
e(e_), parent(parent_), left(nullptr), right(nullptr), height(1) {
//
}
inline bool isLeaf() {
return (left == nullptr && right == nullptr);
}
inline bool hasTwoChildren() {
return (left != nullptr && right != nullptr);
}
inline int balanceFactor() {
//
int leftHeight = left == nullptr ? 0 : left->height; //
int rightHeight = right == nullptr ? 0 : right->height; //
return leftHeight - rightHeight;
}
inline bool isBalanced() {
// node
int balanceFactor_ = balanceFactor();
return balanceFactor_ >= -1 && balanceFactor_ <= 1; // -1,0,1 true
}
inline void updateHeight() {
//
int leftHeight = left == nullptr ? 0 : left->height; //
int rightHeight = right == nullptr ? 0 : right->height; //
height = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); // +1
}
inline bool isLeftChild() {
//
return parent != nullptr && parent->left == this;
}
inline bool isRightChild() {
//
return parent != nullptr && parent->right == this;
}
inline _Node* tallerChild() {
//
int leftHeight = left == nullptr ? 0 : left->height; //
int rightHeight = right == nullptr ? 0 : right->height; //
if (leftHeight > rightHeight)
return left;
if (leftHeight < rightHeight)
return right;
return isLeftChild() ? left : right;
}
} NODE;
NODE *root_;
int (*cmp_)(Element e1, Element e2); // ，
NODE* Node(Element e, int (*cmp_)(Element e1, Element e2)) {
// e
NODE *node = root_;
while (node != nullptr) {
int cmp = cmp_(e, node->e);
if (cmp == 0) //
return node;
if (cmp > 0) { //
node = node->right;
} else { //
node = node->left;
}
}
return nullptr;
}
NODE* predecessor(NODE *node) {
// node
if (node == nullptr)
return nullptr;
//
NODE *tmp = node->left;
if (tmp != nullptr) {
while (tmp->right != nullptr)
tmp = tmp->right;
return tmp;
}
// ，
while (node->parent != nullptr && node == node->parent->left) {
node = node->parent;
}
return node->parent;
}
NODE* successor(NODE *node) {
// node
if (node == nullptr)
return nullptr;
//
NODE *tmp = node->right;
if (tmp != nullptr) {
while (tmp->left != nullptr)
tmp = tmp->left;
return tmp;
}
// ，
while (node->parent != nullptr && node == node->parent->right) {
node = node->parent;
}
return node->parent;
}
void afterRotate(NODE *gNode, NODE *pNode, NODE *child) {
//
pNode->parent = gNode->parent;
if (gNode->isLeftChild())
gNode->parent->left = pNode;
else if (gNode->isRightChild())
gNode->parent->right = pNode;
else
// gNode->parent nullptr，gNode root
root_ = pNode;
if (child != nullptr)
child->parent = gNode;
gNode->parent = pNode;
// ，
gNode->updateHeight();
pNode->updateHeight();
}
void rotateLeft(NODE *gNode) {
// gNode
NODE *pNode = gNode->right;
NODE *child = pNode->left;
gNode->right = child;
pNode->left = gNode;
afterRotate(gNode, pNode, child);
}
void rotateRight(NODE *gNode) {
// gNode
NODE *pNode = gNode->left;
NODE *child = pNode->right;
gNode->left = child;
pNode->right = gNode;
afterRotate(gNode, pNode, child);
}
void rebalance(NODE *gNode) {
// ,grand
NODE *pNode = gNode->tallerChild();
NODE *nNode = pNode->tallerChild();
if (pNode->isLeftChild()) {
if (nNode->isLeftChild()) {
//LL
/*
* gNode
* / gNode
* pNode ====> pNode
* / / \
* nNode nNode gNode
*/
rotateRight(gNode);
} else {
//LR
/*
* gNode gNode
* / pNode / gNode
* pNode ====> nNode ====> nNode
* \ / / \
* nNode pNode pNode gNode
*/
rotateLeft(pNode);
rotateRight(gNode);
}
} else {
if (nNode->isLeftChild()) {
//RL
/*
* gNode gNode
* \ pNode \ gNode
* pNode ====> nNode ====> nNode
* / \ / \
* nNode pNode gNode pNode
*/
rotateRight(pNode);
rotateLeft(gNode);
} else {
//RR
/*
* gNode
* \ gNode
* pNode ====> pNode
* \ / \
* nNode gNode nNode
*/
rotateLeft(gNode);
}
}
}
void afterAdd(NODE *node) {
// node
if (node == nullptr)
return;
node = node->parent;
while (node != nullptr) {
if (node->isBalanced()) {
// ，
node->updateHeight();
} else {
// ，
rebalance(node);
// ,
break;
}
node = node->parent;
}
}
void add(Element e, int (*cmp_)(Element e1, Element e2)) {
// ，
if (root_ == nullptr) {
root_ = new NODE(e, nullptr);
size_++;
//
afterAdd(root_);
return;
}
//
NODE *parent = root_;
NODE *node = root_;
int cmp = 0; //
while (node != nullptr) {
parent = node; //
cmp = cmp_(e, node->e); //
if (cmp > 0) {
node = node->right; //
} else if (cmp < 0) {
node = node->left; //
} else {
node->e = e; //
return; // ,
}
}
//
NODE *newNode = new NODE(e, parent); //
if (cmp > 0) {
parent->right = newNode; //
} else {
parent->left = newNode; //
}
size_++;
//
afterAdd(newNode);
}
void afterRemove(NODE *node) {
// node
if (node == nullptr)
return;
node = node->parent;
while (node != nullptr) {
if (node->isBalanced()) {
// ，
node->updateHeight();
} else {
// ，
rebalance(node);
}
node = node->parent;
}
}
void remove(NODE *node_) {
//
if (node_ == nullptr)
return;
size_--;
// 2
if (node_->hasTwoChildren()) {
NODE *pre = successor(node_); // node_
node_->e = pre->e; // 2
// ( 1 0)
node_ = pre;
}
// node_ 0 1
NODE *replacement = node_->left != nullptr ? node_->left : node_->right;
if (replacement != nullptr) { //node_ 1
replacement->parent = node_->parent;
if (node_->parent == nullptr) // 1
root_ = replacement;
else if (node_->parent->left == node_)
node_->parent->left = replacement;
else
node_->parent->right = replacement;
// ，
afterRemove(node_);
delete node_;
} else if (node_->parent == nullptr) { //node_ ，
root_ = nullptr;
// ，
afterRemove(node_);
delete node_;
} else { //node_ ，
if (node_->parent->left == node_)
node_->parent->left = nullptr;
else
node_->parent->right = nullptr;
// ，
afterRemove(node_);
delete node_;
}
}
void preorderTraversal(NODE *node, bool &stop,
bool (*visitor)(Element &e)) {
//
if (node == nullptr || stop == true)
return;
stop = visitor(node->e);
preorderTraversal(node->left, stop, visitor);
preorderTraversal(node->right, stop, visitor);
}
void inorderTraversal(NODE *node, bool &stop, bool (*visitor)(Element &e)) {
//
if (node == nullptr || stop == true)
return;
inorderTraversal(node->left, stop, visitor);
if (stop == true)
return;
stop = visitor(node->e);
inorderTraversal(node->right, stop, visitor);
}
void postorderTraversal(NODE *node, bool &stop,
bool (*visitor)(Element &e)) {
//
if (node == nullptr || stop == true)
return;
postorderTraversal(node->left, stop, visitor);
postorderTraversal(node->right, stop, visitor);
if (stop == true)
return;
stop = visitor(node->e);
}
void levelOrderTraversal(NODE *node, bool (*visitor)(Element &e)) {
if (node == nullptr)
return;
using namespace std;
queue<NODE*> q;
q.push(node);
while (!q.empty()) {
NODE *node = q.front();
if (visitor(node->e) == true)
return;
if (node->left != nullptr)
q.push(node->left);
if (node->right != nullptr)
q.push(node->right);
q.pop();
}
}
int height(NODE *node) {
//
return node->height;
}
bool isComplete(NODE *node) {
if (node == nullptr)
return false;
using namespace std;
queue<NODE*> q;
q.push(node);
bool leaf = false; //
while (!q.empty()) {
NODE *node = q.front();
if (leaf && !node->isLeaf()) //
return false;
if (node->left != nullptr) {
q.push(node->left);
} else if (node->right != nullptr) { //node->left == nullptr && node->right != nullptr
return false;
}
if (node->right != nullptr) {
q.push(node->right);
} else { //node->right==nullptr
leaf = true;
}
q.pop();
}
return true;
}
};
template<typename Element>
BinarySearchTree<Element>::BinarySearchTree(int (*cmp)(Element e1, Element e2)) :
size_(0), root_(nullptr), cmp_(cmp) {
//
}
template<typename Element>
BinarySearchTree<Element>::~BinarySearchTree() {
//
clear();
}
template<typename Element>
inline int BinarySearchTree<Element>::size() {
//
return size_;
}
template<typename Element>
inline bool BinarySearchTree<Element>::isEmpty() {
//
return size_ == 0;
}
#endif /* SRC_BINARYSEARCHTREE_H_ */
main
/*
* main.cpp
*
* Created on: 2020 1 29
* Author: LuYonglei
*/
#include "BinarySearchTree.h"
#include <iostream>
#include <time.h>
using namespace std;
template<typename Element>
int compare(Element e1, Element e2) {
// , 0,e1<e2 -1,e1>e2 1
return e1 == e2 ? 0 : (e1 < e2 ? -1 : 1);
}
template<typename Elemnet>
bool visitor(Elemnet &e) {
cout << e << " ";
cout << endl;
return false; // true，
}
int main(int argc, char **argv) {
BinarySearchTree<double> a(compare);
// a.add(85);
// a.add(19);
// a.add(69);
// a.add(3);
// a.add(7);
// a.add(99);
// a.add(95);
// a.add(2);
// a.add(1);
// a.add(70);
// a.add(44);
// a.add(58);
// a.add(11);
// a.add(21);
// a.add(14);
// a.add(93);
// a.add(57);
// a.add(4);
// a.add(56);
// a.remove(99);
// a.remove(85);
// a.remove(95);
clock_t start = clock();
for (int i = 0; i < 1000000; i++) {
a.add(i);
}
for (int i = 0; i < 1000000; i++) {
a.remove(i);
}
// a.inorderTraversal(visitor);
clock_t end = clock();
cout << end - start << endl;
// cout <<a.height()<< endl;
// cout << a.isComplete() << endl;
// a.remove(7);
// a.clear();
// a.levelOrderTraversal(visitor);
// cout << endl;
// cout<<a.contains(0)<<endl;
}
위 에서 말 한 것 은 소 편 이 소개 한 AVLTree(C++실현)의 통일 적 인 회전 조작 이 없 는 문제 입 니 다.도움 이 되 셨 으 면 좋 겠 습 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
OpenCV && AKAZE && Windows10 && VisualStudio2017작동하는 버전의 조합을 찾고 ... OpenCV에서 AKAZE로 이미지 간의 특징점을 일치시키고 싶다면, OS(Windows10 64bit)와 OpenCV 버전과 Visual Studio 버전의 조합을 찾는데 힘들었...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
