AVLTree(C++実装)は回転動作が統一されていない
48937 ワード
最近疫病が比較的に深刻で、家で休むことしかできなくて、休みの余暇を利用して、私はC++でAVLの木を一回実現しました
大学の先生は簡単なデータ構造とアルゴリズムしか話していません.これらの高度なデータ構造はやはり自分で自発的に勉強して実現する必要があります.
以前はAVLTreeしか聞いたことがありませんが、本を読んで原理を知ることから少しずつ書くことまで、最後にデバッグに3日ほどかかりました.もうずいぶん時間が経ったはずだ.
一般的にはAVLツリーは私たちが自分で書く必要はありませんが、すでに実現したコードを私が後でアルゴリズムの実現の根拠として振り返るために、私はやはり自分に対して少し厳しくそれを実現することにしました.
以下のコードはすべてC++11標準を採用する
ubuntu 18.04でコンパイルおよびデバッグ
mainメソッド
大学の先生は簡単なデータ構造とアルゴリズムしか話していません.これらの高度なデータ構造はやはり自分で自発的に勉強して実現する必要があります.
以前は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
template
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 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 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 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
BinarySearchTree::BinarySearchTree(int (*cmp)(Element e1, Element e2)) :
size_(0), root_(nullptr), cmp_(cmp) {
//
}
template
BinarySearchTree::~BinarySearchTree() {
//
clear();
}
template
inline int BinarySearchTree::size() {
//
return size_;
}
template
inline bool BinarySearchTree::isEmpty() {
//
return size_ == 0;
}
#endif /* SRC_BINARYSEARCHTREE_H_ */ mainメソッド
/*
* main.cpp
*
* Created on: 2020 1 29
* Author: LuYonglei
*/
#include "BinarySearchTree.h"
#include
#include
using namespace std;
template
int compare(Element e1, Element e2) {
// , 0,e1e2 1
return e1 == e2 ? 0 : (e1 < e2 ? -1 : 1);
}
template
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 <// cout << a.isComplete() << endl;
// a.remove(7);
// a.clear();
// a.levelOrderTraversal(visitor);
// cout << endl;
// cout<
}