AVL可以保证搜索达到O(lgn)的时间效率,因为两边的树高都差不多。不会出现搜索是线性的最坏情况。
但是AVL在插入和删除节点的时候需要做较多的旋转操作,所以如果修改节点多的时候,最好使用红黑树,但是如果搜索多的时候,就最好使用AVL了。
参考:http://www.geeksforgeeks.org/avl-tree-set-1-insertion/
注意点:
1 判断关键字和节点的孩子节点的大小判断应该是左转还是右转
2 利用递归就不需要记录父母节点了
3 注意更新balance和判断balance的顺序
#pragma once #include <stdio.h> #include <algorithm> using std::max; class AVL { struct Node { int key; Node *left, *right; int h; Node(int k) : key(k) { left = right = NULL; h = 1; } ~Node() { if (left) delete left; if (right) delete right; } }; inline int getHeight(Node *n) { if (!n) return 0; return n->h; } inline void updateHeight(Node *y) { y->h = max(getHeight(y->left), getHeight(y->right)) + 1; } Node *rightRotate(Node *y) { Node *x = y->left; y->left = x->right; x->right = y; updateHeight(y); updateHeight(x); return x; } Node *leftRotate(Node *y) { Node *x = y->right; y->right = x->left; x->left = y; updateHeight(y); updateHeight(x); return x; } inline int getBalance(Node *n) { if (!n) return 0; return getHeight(n->left) - getHeight(n->right); } Node *insert(Node *node, int key) { if (!node) return new Node(key); if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); updateHeight(node); int balance = getBalance(node); if (balance > 1 && key < node->left->key) return rightRotate(node); else if (balance < -1 && node->right->key < key) return leftRotate(node); else if (balance > 1 && node->left->key < key) { node->left = leftRotate(node->left); return rightRotate(node); } else if (balance < -1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } //unchanged node pointer return node; } void preOrder(Node *root) { if(root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); } } public: AVL() { Node *root = NULL; /* Constructing tree given in the above figure */ root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); root = insert(root, 50); root = insert(root, 25); /* The constructed AVL Tree would be 30 / 20 40 / \ 10 25 50 */ printf("Pre order traversal of the constructed AVL tree is \n"); preOrder(root); } };
Geeks - AVL Tree Insertion 平衡二叉树,布布扣,bubuko.com
Geeks - AVL Tree Insertion 平衡二叉树
原文:http://blog.csdn.net/kenden23/article/details/27105763