【数据结构】二叉树、AVL树

AVL树得名于其发明者G.M.Adelson-Velsky和E.M.Landis。AVL树是一个各结点具有平衡高度的扩展的二叉搜索树。在AVL树中，任一结点的两个子树的高度差最多为1，AVL树的高度不会超过1，AVL树既有二叉搜索树的搜索效率又可以避免二叉搜索树的最坏情况（退化树）出现。

AVL树的表示与二叉搜索树类似，其操作基本相同，但插入和删除方法除外，因为它们必须不断监控结点的左右子树的相对高度，这也正是AVL树的优势所在。

实现AVL树的相关运算

1、首先我们修改结构Binary_node，增加Balance_factor用以表示节点平衡情况

2、从二叉搜索树中派生出AVL树，编写其关键的插入和删除成员函数。

Error_code insert(const Record &new_data);
Error_code remove(const Record &old_data);

3、入和删除函数我们都用递归实现
编写递归函数：

Error_code avl_insert(Binary_node<Record>* &sub_root,const Record &new_data,bool &taller);
Error_code avl_remove(Binary_node<Record>* &sub_root,const Record &target,bool &shorter);

以及几个重要的调用函数：
左旋右旋函数：

void rotate_left(Binary_node<Record>* &sub_root);
void rotate_right(Binary_node<Record>* &sub_root);

（编辑：网站开发网_马鞍山站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!