26 avl树（下）

#define _CRT_SECURE_NO_WARNINGS 1 #include<vector> #include"AVLTree.h" void TestAVLTree1() { AVLTree<int, int> t; // 常规的测试用例 int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // 特殊的带有双旋场景的测试用例 //int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) { t.Insert({ e, e }); } t.InOrder(); } int main() { TestAVLTree2(); return 0; }

中序没毛病

怎么检查是不是avl树

这也要套一层

就没问题。

插入logN 很快，

void InOrder() { _InOrder(_root); cout << endl; } int Height() { return _Height(_root); } int Size() { return _Size(_root); } bool IsBalanceTree() { return _IsBalanceTree(_root); } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return nullptr; } private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } int _Size(Node* root) { if (root == nullptr) return 0; return _Size(root->_left) + _Size(root->_right) + 1; } bool _IsBalanceTree(Node* root) { // 空树也是AVL树 if (nullptr == root) return true; // 计算pRoot结点的平衡因子：即pRoot左右子树的高度差 int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); int diff = rightHeight - leftHeight; // 如果计算出的平衡因子与pRoot的平衡因子不相等，或者 // pRoot平衡因子的绝对值超过1，则一定不是AVL树 if (abs(diff) >= 2) { cout << root->_kv.first << "高度差异常" << endl; return false; } if (root->_bf != diff) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } // pRoot的左和右如果都是AVL树，则该树一定是AVL树 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); } private: Node* _root = nullptr; };

删除节点一定是左为空或者右为空，

现在是0.说明之前是1或者-1，就要往上更新

变成1 -1 不用更新，高度不变，再删10 ，就要旋转了，