Shulou(Shulou.com)06/03 Report--

How to solve the problem that AVLTree does not have a unified rotation operation, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail for you, people with this need can come to learn, I hope you can gain something.

Recently, the epidemic is quite serious, so I can only rest at home. After taking a rest, I use C++ to implement the AVL tree again.

University teachers only talk about some relatively simple data structures and algorithms, but these advanced data structures still need to be actively studied and implemented by themselves.

I have only heard of AVLTree before. I spent about 3 days debugging from reading to writing it bit by bit. It should have been a long time.

Normally, we don't have to write the AVL tree by ourselves, but in order to have a copy of the implemented code as the basis for me to review the algorithm implementation later, I decided to be tough on myself and implement it again.

The following codes are based on the Clear11 standard.

Compiled and debugged on ubuntu 18.04

/ * * BinarySearchTree.h * 1. When you add an element, you need to judge whether the element is legal or not * 2. Except for sequence traversal, this source code uses recursive traversal. In order to reduce stack consumption, recursive traversal * 3. The AVL tree realized by this code does not have a unified rotation operation. It uses case-by-case discussion LL,LR,RR,RL to balance the tree * Created on: January 29th, 2020 * Author: LuYonglei * / # ifndef SRC_BINARYSEARCHTREE_H_#define SRC_BINARYSEARCHTREE_H_#include templateclass BinarySearchTree {public: BinarySearchTree (int (* cmp) (Element e1, Element e2)); / / comparison function pointer virtual ~ BinarySearchTree (); int size (); / / number of elements bool isEmpty () / whether void clear () {/ / clear all elements 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 element add (e, cmp_);} void remove (Element e) {/ / delete element remove (Node (e, cmp_));} bool contains (Element e) {/ / contains an element return Node (e, cmp_)! = nullptr;} void preorderTraversal (bool (* visitor) (Element & e)) {/ / preorder traversal if (visitor = nullptr) return; bool stop = false / / stop flag, if stop is true, stop traversing preorderTraversal (root_, stop, visitor);} void inorderTraversal (bool (* visitor) (Element & e)) {/ / Central order traversal if (visitor = = nullptr) return; bool stop = false; / / stop flag, if stop is true, stop traversing inorderTraversal (root_, stop, visitor);} void postorderTraversal (bool (* visitor) (Element & e)) {/ Post-order traversal if (visitor = = nullptr) return; bool stop = false / / stop flag. If stop is true, stop traversing postorderTraversal (root_, stop, visitor);} void levelOrderTraversal (bool (* visitor) (Element & e)) {/ / sequence traversal, iteratively implement if (visitor = = nullptr) return; levelOrderTraversal (root_, visitor);} int height () {/ / height return height (root_) of the tree;} bool isComplete () {/ / determine whether it is a complete binary tree return isComplete (root_);} private: int size_ Typedef struct _ Node {Element e; _ Node * parent; _ Node * left; _ Node * right; int height; / / height of the node _ Node (Element eigenvalues, _ Node * parent_): e (e_), parent (parent_), left (nullptr), right (nullptr), height (1) {/ / Node constructor} inline bool isLeaf () {return (left = = nullptr & & right = = nullptr) } inline bool hasTwoChildren () {return (left! = nullptr & & right! = nullptr);} inline int balanceFactor () {/ / get the balance factor of the node int leftHeight = = nullptr? 0: left- > height; / / obtain the height of the left subtree int rightHeight = right = = nullptr? 0: right- > height; / / obtain the height of the right subtree return leftHeight-rightHeight;} inline bool isBalanced () {/ / determine whether node balances int balanceFactor_ = balanceFactor () Return balanceFactor_ > =-1 & & balanceFactor_ height; / / get the height of the left subtree int rightHeight = = nullptr? 0: right- > height; / / get the height of the right subtree height = 1 + (leftHeight > rightHeight? LeftHeight: rightHeight); / / update the node height to the maximum height of the left and right subtree + 1} inline bool isLeftChild () {/ / determine whether the node is the left child node of the parent node return parent! = nullptr & & parent- > left = = this;} inline bool isRightChild () {/ / determine whether the node is the right child node of the parent node return parent! = nullptr & parent- > right = = this } inline _ Node* tallerChild () {/ / get a higher subtree int leftHeight = left = = nullptr? 0: left- > height; / / get the height of the left subtree int rightHeight = right = = nullptr? 0: right- > height; / / get the height of the right subtree 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) / / found the element return node; if (cmp > 0) {/ / the element to be looked for is larger than the element stored by the node node = node- > right;} else {/ / the element to be searched is smaller than the element stored by the node node = node- > left;}} return nullptr;} NODE* predecessor (NODE* node) {/ / returns the precursor node if (node = = nullptr) return nullptr of node / / the precursor node is in the left child tree NODE* tmp = node- > left; if (tmp! = nullptr) {while (tmp- > right! = nullptr) tmp = tmp- > right; return tmp;} / / from the parent node and grandfather node to find the precursor node while (node- > parent! = nullptr & & node = = node- > parent- > left) {node = node- > parent;} return node- > parent;} NODE* successor (NODE* node) {/ / return node's successor if (node = = nullptr) return nullptr / / the successor node is in the right child tree NODE * tmp = node- > right; if (tmp! = nullptr) {while (tmp- > left! = nullptr) tmp = tmp- > left; return tmp;} / / from the parent node and grandfather node to find the successor node while (node- > parent! = nullptr & node = = node- > parent- > right) {node = node- > parent;} return node- > parent } void afterRotate (NODE * gNode, NODE * pNode, NODE * child) {/ / call pNode- > parent = gNode- > parent; if (gNode- > isLeftChild () gNode- > parent- > left = pNode; else if (gNode- > isRightChild () gNode- > parent- > right = pNode; else / / at this time gNode- > parent is nullptr,gNode for root node root_ = pNode; if (child! = nullptr) child- > parent = gNode; gNode- > parent = pNode / / the left and right subtrees have changed, so update height gNode- > updateHeight (); pNode- > updateHeight ();} void rotateLeft (NODE * gNode) {/ / a pair of gNode rotate left NODE * pNode = gNode- > right; NODE * child = pNode- > left; gNode- > right = child; pNode- > left = gNode; afterRotate (gNode, pNode, child);} void rotateRight (NODE * gNode) {/ / a pair of gNode rotate NODE * pNode = gNode- > left; NODE * child = pNode- > right; gNode- > left = child PNode- > right = gNode; afterRotate (gNode, pNode, child);} void rebalance (NODE * gNode) {/ / restore balance, grand is the lowest unbalanced node NODE * pNode = gNode- > tallerChild (); NODE * nNode = pNode- > tallerChild (); if (pNode- > isLeftChild ()) {if (nNode- > isLeftChild ()) {/ / LL / * gNode * / a pair of gNode right-handed * pNode = > pNode * /\ * nNode nNode gNode * / rotateRight (gNode) } else {/ / LR / * * gNode gNode * / a pair of pNode left-handed / a pair of gNode right-handed * pNode = = > nNode = = > nNode * / /\ * nNode pNode pNode gNode * / rotateLeft (pNode); rotateRight (gNode) }} else {if (nNode- > isLeftChild ()) {/ / RL / * * gNode gNode *\ to pNode right\ to gNode left * pNode = = > nNode = = > nNode * /\ /\ * nNode pNode gNode pNode * / rotateRight (pNode); rotateLeft (gNode);} else {/ / RR / * * gNode *\ to gNode left-handed * pNode = = > pNode * /\ * nNode gNode nNode * / rotateLeft (gNode) } void afterAdd (NODE * node) {/ / adjust if (node = = nullptr) return; node = node- > parent; while (node! = nullptr) {if (node- > isBalanced ()) {/ / if the node is balanced, its update height node- > updateHeight ();} else {/ / operates on the first unbalanced node to balance rebalance (node); / / after the whole tree is balanced, jump out of the cycle break } node = node- > parent;}} void add (Element e, int (* cmp_) (Element E1, Element e2)) {/ / when the tree is empty, the added node is the root node of the tree if (root_ = = nullptr) {root_ = new NODE (e, nullptr); size_++; / / adjusts afterAdd (root_) after inserting a root node; return;} / / when the added node is not the first node NODE * parent = root_ NODE * node = root_; int cmp = 0; / compare result while (node! = nullptr) {parent = node; / / Save parent cmp = cmp_ (e, node- > e); / / compare if (cmp > 0) {node = node- > right; / / the element added is larger than the element in the node} else if (cmp)

< 0) { node = node->

Left; / / the added element is less than the element in the node} else {node- > e = e; / / overrides return; / / if the added element is equal to the element in the node, directly return}} / / to determine where to insert the parent node NODE * newNode = new NODE (e, parent); / / create a node if (cmp > 0) {parent- > right = newNode for the new element / / the added element is larger than the element in the node} else {parent- > left = newNode; / / the added element is smaller than the element in the node} size_++; / / adjust afterAdd (newNode) after adding a new node;} void afterRemove (NODE * node) {/ / adjust if (node = = nullptr) return; node = node- > parent after deleting node While (node! = nullptr) {if (node- > isBalanced ()) {/ / if the node is balanced, update height node- > updateHeight ();} else {/ / operates on unbalanced nodes to balance rebalance (node);} node = node- > parent;}} void remove (NODE * node_) {/ / Delete a node if (node_ = = nullptr) return; size_-- / / Node if (node_- > hasTwoChildren ()) {NODE * pre = successor (node_); / / find the successor node of node_ node_- > e = pre- > e; / / overwrite the value of the node with degree 2 with the value of the successor node / / delete the successor node (the degree of the successor node can only be 1 or 0) node_ = pre;} / / then the degree of node_ must be 0 or 1 NODE * replacement = node_- > left! = nullptr? Node_- > left: node_- > right; if (replacement! = nullptr) {/ / node_ is 1 replacement- > parent = node_- > parent; if (node_- > parent = = nullptr) / / the root node with degree 1 root_ = replacement; else if (node_- > parent- > left = = node_) node_- > parent- > left = replacement; else node_- > parent- > right = replacement; / / all deletion operations are ready to be completed, and afterRemove (node_) is balanced before releasing the node memory; delete node_ } else if (node_- > parent = = nullptr) {/ / node_ is the leaf node and root node root_ = nullptr; / / all deletion operations are ready to complete and balance operation afterRemove (node_) before preparing to release the memory of the node; delete node_;} else {/ / node_ is the leaf node, but not the root node if (node_- > parent- > left = = node_) node_- > parent- > left = nullptr; else node_- > parent- > right = nullptr / / all deletion operations are ready to be completed, afterRemove (node_) is ready to release node memory; delete node_;}} void preorderTraversal (NODE * node, bool & stop, bool (* visitor) (Element & e)) {/ / Recursive implementation of preorder traversal 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)) {/ / Recursive implementation of traversing 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)) {/ / Recursive implementation of post-order traversal of 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 (if = = node) node (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) {/ / height of a node return node- > height;} bool isComplete (NODE * node) {if (node = nullptr) return false; using namespace std; queue q Q.push (node); bool leaf = false; / / determine whether the next node is a leaf node while (! q.empty ()) {NODE * node = q.front (); if (leaf & &! node- > isLeaf ()) / / determine the leaf node 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;}}; templateBinarySearchTree::BinarySearchTree (int (* cmp) (Element e1, Element e2)): size_ (0), root_ (nullptr), cmp_ (cmp) {/ / the constructor of tree} templateBinarySearchTree::~BinarySearchTree () {/ / destructor clear () } templateinline int BinarySearchTree::size () {/ / return the number of elements return size_;} templateinline bool BinarySearchTree::isEmpty () {/ / determine whether the tree is empty return size_ = = 0;} # endif / * SRC_BINARYSEARCHTREE_H_ * / main method / * * main.cpp * * Created on: January 29th, 2020 * Author: LuYonglei * / # include "BinarySearchTree.h" # include # include using namespace std Templateint compare (Element e1, Element e2) {/ / comparison function, the same returns 0 return e1e2 returns 1 return e1 = = e2? 0: (E1 < e2?-1: 1);} templatebool visitor (Elemnet & e) {cout

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.