树形数据结构小结
一、 说明
小结中包括Binary Tree、Binary search tree、buildable tree、AVL tree、Splay tree、Tries、B-trees。主要对这些学过的树形数据结构做一个简单的总结概括，可能不是很全面，但可作为复习参考。（还没写完，这两天尽量更完吧）
二、 正文
1） Binary_trees:
① 定义：空树或者父节点具有之多两个孩子节点的树
② 概念：
· 完全二叉树：除最后一层外，其它层中节点树均达到最大，最后一层叶子节点由左向右排列。
· 满二叉树：每一层节点数均达到最大值
· 深度（depth）：二叉树的层数（一般越矮越好）
③ 性质：以下记二叉树的根节点所在层数为第一层
· 第i层的节点不超过2^(i-1)个
· 深度为h的二叉树至多有2^h-1个节点（h>=1）
· 具有n个节点的完全二叉树depth=log2n+1
④ 二叉树的三种遍历形式：
· VLR 前序遍历（preorder）：根->左->右
· LVR 中序遍历（inorder）：左->根->右
· LRV后序遍历（postorder）：左->右->根
⑤ 重要算法描述：
· 层序遍历：要求对树进行逐层遍历
算法描述：利用辅助队列存储待访问的节点指针
1)、将根节点放入队列
2)、对队列的队首进行访问，同时对当前访问节点的左右孩子进行检测，若非空，对其进行入队操作
3)、将已访问的队首pop出来
4)、重复上述操作，直至辅助队列中为空
实现代码：
template<class Entry>
void Binary_tree<Entry>::level_tranverse(void(*visit)(Entry &))
{
if (!root)return;
queue<Binary_node<Entry> *> wait_queue;
wait_queue.push(root);
do {
Binary_node<Entry> *tmp = wait_queue.front();
(*visit)(tmp->data);
if (tmp->left_child)wait_queue.push(tmp->left_child);
if (tmp->right_child)wait_queue.push(tmp->right_child);
wait_queue.pop();
} while (!wait_queue.empty());
}
算法描述：利用递归实现
1）base case：当传入根节点为空时，结束递归
2）general case：sub_root->left=sub_root->right
Sub_root->right=sub_root->left
对左右子树分别进行上述递归
实现代码：
template<class Entry>
void Binary_tree<Entry>::interchange()
{
recursive_interchange(root);
}
template<class Entry>
void Binary_tree<Entry>::recursive_interchange(Binary_node<Entry>* sub_root)
{
if (!sub_root) {
Binary_node<Entry> *tmp = sub_root->left_child;
sub_root->left_child = sub_root->right_child;
sub_root->right_child = tmp;
recursive_interchange(sub_root->left_child);
recursive_interchange(sub_root->right_child);
}
}
· 深度检测（depth计算）：对任意树的depth进行计算
算法描述：利用递归实现
1）、base case：当传入根节点为空时，返回depth=0，结束递归
2）、general case：拿到左右子树的depth（通过递归，记为 left、right）
若右子树深度大于左子树，则返回（right+1）；
若左子树深度大于右子树，则返回（left+1）；
其中+1表示根节点的深度1.
实现代码：
template<class Entry>
int Binary_tree<Entry>::height()
{
return recursive_height(root);
}
template<class Entry>
int Binary_tree<Entry>::recursive_height(Binary_node<Entry>* sub_root)
{
if (!sub_root)return 0;
int left = recursive_height(sub_root->left_child);
int right = recursive_height(sub_root->right_child);
if (left > right) return (left + 1);
else return (right + 1);
}
· 节点数计算（size计算）：
算法描述：利用递归实现
1）、base case：当传入根节点为空时，返回size=0，结束递归
2）、general case：取得左右子树的size（通过递归，记为left、right），返回（left+right+1）。
其中+1表示当前根节点。
实现代码：
template<class Entry>
int Binary_tree<Entry>::size()
{
return recursive_size(root);
}
template<class Entry>
int Binary_tree<Entry>::recursive_size(Binary_node<Entry>* sub_root)
{
if (!sub_root)return 0;
int left = recursive_size(sub_root->left_child);
int right = recursive_size(sub_root->right_child);
return (left + right + 1);
}
· 前序遍历（preorder）:
算法描述：利用递归实现
1）base case：当传入根节点为空时，结束递归
2）general case：对根节点进行访问；
然后对左孩子进行访问（递归进行）；
最后对右孩子进行访问（递归进行）；
实现代码：
template<class Entry>
void Binary_tree<Entry>::preorder(void(*visit)(Entry &))
{
recursive_preorder(root, visit);
}
template<class Entry>
void Binary_tree<Entry>::recursive_preorder(Binary_node<Entry>* sub_root, void(*visit)(Entry &))
{
if (sub_root) {
(*visit)(sub_root->data);
recursive_preorder(sub_root->left_child, visit);
recursive_preorder(sub_root->right_child, visit);
}
}
· 中序遍历和后序遍历与前序遍历类似就不再赘述。
-----------------------------------------华丽丽的分割线-------------------------------------------
2) Binary_Search_Tree:
①定义：空树或是一棵具有如下性质的树：
1） 左子树上的节点值均小于根节点的值
2） 右子树上的节点值均大于根节点的值
3） 树上不存在节点值相同的两个节点
4） 左右子树也是一棵二叉查找树
②重要算法描述：
· 查找算法（search）
算法描述：利用递归实现
1）、base case：若当前根节点值等于待查找的值返回sub_root指针，或当前根节点为空，返回NULL
2）、general case：若当前根节点值大于待查找节点值，则对当前节点的左子树进行查找（递归进行）
若当前节点值小于待查找节点值，则对当前节点的右子树进行查找（递归进行）
实现代码：
template<class Record>
Error_code Binary_search_tree<Record>::search(Record & item)
{
Binary_node<Record> *p = recursive_search(root, item);
if (p == NULL)return not_present;
else {
item = p->data;
return success;
}
}
template<class Record>
Binary_node<Record> * Binary_search_tree<Record>::recursive_search(Binary_node<Record>*& sub_root, const Record & item)
{
if (sub_root == NULL || sub_root->data == item)return sub_root;
else if (sub_root->data > item)return recursive_search(sub_root->left_child, item);
else if (sub_root->data < item)return recursive_search(sub_root->right_child, item);
}
· 插入算法（insert）
算法描述：利用递归实现，下附循环实现代码
1）base case：若当前根节点为空，则sub_root=new node；
或当前根节点的值与待插入节点值相等，返回duplicate error
2）general case：若当前根节点值大于待插入节点值，则转化为
对当前节点的左子树进行插入（递归进行）
若当前根节点值小于待插入节点值，则转化为对当前节点的右子树进行插入（递归进行）
实现代码：
//递归版本
template<class Record>
Error_code Binary_search_tree<Record>::insert(const Record & item)
{
if (recursive_insert(root, item) == success) {
count++;
return success;
}
else return duplicate_error;
}
template<class Record>
Error_code Binary_search_tree<Record>::recursive_insert(Binary_node<Record>*& sub_root, const Record & item)
{
if (!sub_root) {
sub_root = new Binary_node<Record>(item);
return success;
}
else if (sub_root->data > item)return recursive_insert(sub_root->left_child, item);
else if (sub_root->data < item)return recursive_insert(sub_root->right_child, item);
else return duplicate_error;
}
//循环版本
template<class Record>
Error_code Binary_search_tree<Record>::c_insert(const Record & item)
{
Binary_node<Record> *current=root, *previous=root;
if(!current)root = new Binary_node<Record>(item);
else {
while (current != NULL) {
previous = current;
if (current->data > item)current = current->left_child;
else if (current->data < item)current = current->right_child;
else return duplicate_error;
}
if (previous->data > item)
previous->left_child = new Binary_node<Record>(item);
else
previous->right_child = new Binary_node<Record>(item);
return success;
}
}
· 删除算法（remove）
算法描述：利用递归实现，下附循环实现代码
1）、base case：若传入根节点为空，则返回not presen
若当前根节点的值等于待删除节点的值，则对当前根节点进行删除操作（删除操作在下面进行详述）
2）、general case：若当前根节点的值大于待删除节点的值，则转化为对当前节点的左子树进行删除操作（递归进行）
若当前根节点的值小于待删除节点的值，则转化为对当前节点的右子树进行删除操作（递归进行）
删除操作（destroy）：
/*precondition：传入指针指向待删除节点*/
1）若传入待删除节点为空，则返回not present
2）若传入待删除节点的左子树为空，则将传入指针修改为sub_root->right
3) 若传入待删除节点的右子树为空，则将传入指针修改为sub_root->left
4）若传入待删除节点的左右指针均不为空，则寻找待删除节点的前驱（左子树中最大值），将待删除节点值修改为前驱值，转化为删除前驱节点（右子树必为空）
ATTENTION：要注意若待删除节点的左子树有且仅有一个节点的情况。
代码实现：
//递归版本
template<class Record>
Error_code Binary_search_tree<Record>::remove(const Record & item)
{
if (search_and_destroy(root, item) == success) {
count--;
return success;
}
else return not_present;
}
template<class Record>
Error_code Binary_search_tree<Record>::search_and_destroy(Binary_node<Record>*& sub_root, const Record & item)
{
if (sub_root == NULL || sub_root->data == item)
return destroy(sub_root);
else if (sub_root->data > item)return destory(sub_root->left_child);
else if (sub_root->data < item)return destory(sub_root->right_child);
}
template<class Record>
Error_code Binary_search_tree<Record>::destroy(Binary_node<Record>*& sub_root)
{
if (sub_root == NULL)return not_present;
Binary_node<Entry> *to_delete = sub_root;
if (sub_root->left_child == NULL) sub_root = sub_root->right_child;
else if (sub_root->right_child == NULL) sub_root = sub_root->left_child;
else {
to_delete = sub_root->left_child;
Binary_node<Entry> *parent = sub_root;
while (!to_delete->right_child) {
parent = to_delete;
to_delete = to_delete->right_child;
}
sub_root->data = to_delete->data;
if (parent == sub_root)sub_root->left_child = to_delete->left_child; //Special condition:no right_child under to_delete
else parent->right_child = to_delete->right_child;
}
delete to_delete;
return success;
}
//循环版本
template<class Record>
Error_code Binary_search_tree<Record>::c_remove(const Record & item)
{
if (root == NULL || root->data == item)
return destroy(root);
else {
Binary_node<Record> *&tmp = root;
while (tmp != NULL) {
if (tmp->data > item)tmp = tmp->left_child;
else if (tmp->data < item)tmp = tmp->right_child;
else return destroy(tmp);
}
return not_present;
}
}
-----------------------------------------华丽丽的分割线-------------------------------------------
以下描述的各个树实际上是在对Binary Search Tree的insert进行各种环境下的优化操作。
3）Bulidable tree：/*precondition：待插入节点为顺序时方可使用该算法*/
算法描述：
1)、 判断该节点位于的层数。X%2k=0 ，K为满足条件的最大值。在10.3节，层数从叶子节点开始计算。叶子节点位第0层。
2)、 节点的右孩子默认为空（该节点为树中的最大值）。节点如果为叶子节点，左孩子为空。节点如果为非叶子节点，找到k-1层的最后一个节点为左孩子。
3)、 关于增加节点的父节点判断，如果K+1层存在，K+1层的最后一个节点的右孩子为空，当前点为K+1最后一个节点的右孩子。
在最后一个节点插入成功之后，需要进行右孩子的处理：
4）、从最高层n依次向叶子节点方向查找，如果当前第k层的最后一个节点node的右孩子为空。
依次查找第K-1层到1层的最后一个节点，如果当前层i的最后一个节点比K层的最后一个节点node大，则找到它的右孩子。
继续从第i层向第3层搜索，处理右孩子的链接。直到搜索到第3层为止。（叶子节点为第1层）
ATTENTION：完成插入操作的关键，记住每一层最后一个节点的位置（指针）。
因此，为了完成插入操作，引入一个辅助队列：
List<Binary_node<entry>* > last_node;
last_node为List的对象，其中的每一个元素用来记录插入过程中每一个层最后一个节点的指针。 last_node的第0个元素初始化为空，叶子节点层记录在last_node的第1个元素中，依次类推。
构建方法简述：
1）从有序序列中依次取出每个节点，按照Buildable Tree的构建方法在树中插入该节点。
2）全部节点插入成功之后，分析每层最后一个节点的右孩子是否链接成功，依次处理每一层右孩子的连接。
3）右孩子的链接处理之后，获取当前二叉查找树的根，构建结束。
当前二叉查找树根的地址存放于last_node的最后一个元素中。
实现代码：
template <class Record>
Error_code Buildable_tree<Record> ::build_tree(const List<Record> &supply)
{
Error_code ordered_data = success;
//remove it for our Binary_tree int count
//int count = 0; // number of entries inserted so far
Record x, last_x;
List < Binary_node<Record> * > last_node;
// pointers to last nodes on each level
Binary_node<Record> *none = NULL;
last_node.insert(0, none); // permanently NULL (for children of leaves)
while (supply.retrieve(count, x) == success) {
if (count > 0 && x <= last_x) {
ordered_data = fail;
break;
}
build_insert(++count, x, last_node);
last_x = x;
}
root = find_root(last_node);
connect_trees(last_node);
return ordered_data; // Report any data-ordering problems back to client.
}
template <class Record>
Error_code Buildable_tree<Record> ::build_tree(const List<Record> &supply)
{
Error_code ordered_data = success;
//remove it for our Binary_tree int count
//int count = 0; // number of entries inserted so far
Record x, last_x;
List < Binary_node<Record> * > last_node;
// pointers to last nodes on each level
Binary_node<Record> *none = NULL;
last_node.insert(0, none); // permanently NULL (for children of leaves)
while (supply.retrieve(count, x) == success) {
if (count > 0 && x <= last_x) {
ordered_data = fail;
break;
}
build_insert(++count, x, last_node);
last_x = x;
}
root = find_root(last_node);
connect_trees(last_node);
return ordered_data; // Report any data-ordering problems back to client.
}
template <class Record>
Binary_node<Record> *Buildable_tree<Record> ::find_root(
const List < Binary_node<Record>* > &last_node)
/* Pre: The list last node contains pointers to the last node on each occupied level of the binary search tree.
Post: A pointer to the root of the newly created binary search tree is returned.
Uses: Methods of classList */
{
Binary_node<Record> *high_node;
last_node.retrieve(last_node.size() - 1, high_node);
// Find root in the highest occupied level in last node .
return high_node;
}
template <class Record>
void Buildable_tree<Record> :: (
const List < Binary_node<Record>* > &last_node)
{
Binary_node<Record>
*high_node, // from last node with NULL right child
*low_node; // candidate for right child of high node
int high_level = last_node.size() - 1, low_level;
while (high_level > 2) { // Nodes on levels 1 and 2 are already OK.
last_node.retrieve(high_level, high_node);
if (high_node->right != NULL)
high_level--; // Search down for highest dangling node.
else { // Case: undefined right tree
low_level = high_level;
do { // Find the highest entry not in the left subtree.
last_node.retrieve(--low_level, low_node);
} while (low_node != NULL && low_node->data < high_node->data);
high_node->right = low_node;
high_level = low_level;
}
}
}
4）AVL Tree：
①定义：在AVL树中任何节点的两个子树的高度最大差别为一的一棵二分查找树
②实现原理：在原有的节点中加入平衡因子（balance factor）：左高（left_higher），右高（right_higher），等高（equal_height）.若出现破坏平衡的情况，则立即进行对应情况的旋转进行调整，以维持平衡（减小高度）。使得最终的AVL树各个节点的左右子树高度差不超过1.
③四种操作使用情况及其效果（感谢@collonn提供的AVL图解CSDN）：
· LL
当前节点为左高，且当前节点的左孩子也为左高
操作：对当前节点进行一次右旋
效果：高度--，当前节点与左孩子平衡因子调整为等高
· RR
当前节点为右高，且当前节点的右孩子也为右高
操作：对当前节点进行一次左旋
效果：高度--，当前节点与右孩子的平衡因子调整为等高
· LR
当前结点为左高，且左孩子为右高
操作：先对左孩子进行一次左旋，再对当前节点进行一次右旋
效果： 高度--，当前节点的平衡因子调整为等高，左孩子的平衡因子由左孩子的右孩子确定
· RL
当前节点为右高，且当前节点的有孩子为左高
操作：先对右孩子进行一次右旋，在对当前节点进行一次左旋
效果：高度--，当前节点的平衡因子调整为等高，右孩子的平衡因子由右孩子的左孩子确定
④操作：
1）单一旋转：
· 左旋：
实现代码：
template<class Record>
void AVL_tree<Record>::rotate_left(Binary_node<Record>*& sub_root)
{
if (sub_root == nullptr || sub_root->right_child == nullptr)
cout << "WARNING:program error detected in rotate left" << endl;
else {
Binary_node<Record> *right_tree = sub_root->right_child;
sub_root->right_child = right_tree->left_child;
right_tree->left_child = sub_root;
sub_root = right_tree;
}
}
· 右旋：
实现代码：
template<class Record>
void AVL_tree<Record>::rotate_right(Binary_node<Record>*& sub_root)
{
if (sub_root == nullptr || sub_root->left_child == nullptr)
cout << "WARNING:program error detected in rotate right" << endl;
else {
Binary_node<Record> *left_tree = sub_root->left_child;
sub_root->left_child = left_tree->right_child;
left_tree->right_child = sub_root;
sub_root = left_tree;
}
}
2）组合旋转：
· LR/LL
实现代码：
template<class Record>//先调整平衡因子，然后进行对应的旋转
void AVL_tree<Record>::left_balance(Binary_node<Record>*& sub_root)
{
Binary_node<Record> *&left_tree = sub_root->left_child;
switch (left_tree->get_balance()){
case left_higher: //LL
sub_root->set_balance(equal_height);
left_tree->set_balance(equal_height);
rotate_right(sub_root);
break;
case equal_height:
cout << "WARNING:program error detected in left balance" << endl;
break;
case right_higher: //LR: Pay attention to the balance_facor
Binary_node<Record> *sub_tree = left_tree->right_child;
switch (sub_tree->get_balance())
{
case equal_height:
sub_root->set_balance(equal_height);
left_tree->set_balance(equal_height);
break;
case right_higher:
sub_root->set_balance(equal_height);
left_tree->set_balance(left_higher);
break;
case left_higher:
sub_root->set_balance(right_higher);
left_tree->set_balance(equal_height);
break;
}
sub_tree->set_balance(equal_height);
rotate_left(left_tree);
rotate_right(sub_root);
break;
}
}
· RL/RR
template<class Record>
void AVL_tree<Record>::right_balance(Binary_node<Record>*& sub_root)
{
Binary_node<Record> *&right_tree = sub_root->right_child;
switch (right_tree->get_balance())
{
case right_higher: //RR：对sub_root左旋
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
rotate_left(sub_root);
break;
case equal_height:
cout << "WARNING:program error detected in right balance" << endl;
break;
case left_higher: //RL：右旋后左旋，注意平衡因子的判断
Binary_node<Record> *sub_tree = right_tree->left_child;
switch (sub_tree->get_balance())
{
case equal_height:
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
break;
case left_higher:
sub_root->set_balance(equal_height);
right_tree->set_balance(right_higher);
break;
case right_higher:
sub_root->set_balance(left_higher);
right_tree->set_balance(equal_height);
break;
}
sub_tree->set_balance(equal_height);
rotate_right(right_tree);
rotate_left(sub_root);
break;
}
}
⑤重要算法描述;
· 插入操作：
算法描述：递归实现
1）base case：当前节点为空时，sub_root=new node，返回success
或当前节点值的待插入节点值返回duplicate error
2）general case：若当前节点值大于待插入节点值，则转化为对当前节点的左子树进行插入操作（递归进行），若左子树taller=true，判断是否破坏了平衡，如果破坏了平衡，寻找对应操作，并调整平衡因子；
若当前节点值小于待插入节点值，则转化为对当前节点的右子树进行插入操作（递归进行），同样进行上述判断、操作。
实现代码;
template<class Record>
Error_code AVL_tree<Record>::insert(const Record & new_data)
{
bool taller;
return avl_insert(root, new_data, taller);
}
template<class Record>
Error_code AVL_tree<Record>::avl_insert(Binary_node<Record>*& sub_root, const Record & new_data, bool & taller)
{
if (sub_root == NULL) {
sub_root = new AVL_node<Record>(new_data);
taller = true;
return success;
}
else if (sub_root->data == new_data) {
taller = false;
return duplicate_error;
}
else if (sub_root->data > new_data) {
Error_code result = avl_insert(sub_root->left_child, new_data, taller);
if (taller == true) {
switch (sub_root->get_balance())
{
case left_higher:
left_balance(sub_root);
taller = false;
break;
case equal_height:
sub_root->set_balance(left_higher);
break;
case right_higher:
sub_root->set_balance(equal_height);
taller = false;
break;
}
}
return result;
}
else {
Error_code result = avl_insert(sub_root->right_child, new_data, taller);
if (taller == true) {
switch (sub_root->get_balance())
{
case left_higher:
sub_root->set_balance(equal_height);
taller = false;
break;
case equal_height:
sub_root->set_balance(right_higher);
break;
case right_higher:
right_balance(sub_root);
taller = false;
break;
}
}
return result;
}
}
· 删除操作：
算法描述：递归实现
1）base case：若当前节点为空，说明不存在。返回not present
或当前节点值等于待删除节点值，则进行删除操作（下方细讲）
2）general case：若当前节点值大于待删除节点值，则转化为对当 前节点的左子树进行删除操作，若 shorter==true，则寻找对应的 操作，并对平衡因子进行修改；若当前节点值小于待删除节点
值，则转化为对当前节点的右子树进行删除操作，若 shorter==true，同上述操作。
删除操作：
若待删除节点的左子树为空，则 sub_root=sub_root->right
若待删除节点的右子树为空，则 sub_root=sub_root->left
若待删除节点的左右子树均不为空，则寻找待删除节点的前驱， 并记录前驱的值，转化为对左子树删除前驱的操作
实现代码：
template<class Record>
Error_code AVL_tree<Record>::remove(Record & old_data)
{
bool shorter = true;
return avl_remove(root, old_data, shorter);
}
template<class Record>
Error_code AVL_tree<Record>::avl_remove(Binary_node<Record>*& sub_root, Record & new_data, bool & shorter)
{
Error_code result;
Record sub_record;
if (sub_root == NULL) {
shorter = false;
return not_present;
}
else if (new_data == sub_root->data) {
Binary_node<Record>*to_delete = sub_root;
if (sub_root->right_child == NULL) {
sub_root = sub_root->left_child;
shorter = true;
delete to_delete;
return success;
}
else if (sub_root->left_child == NULL) {
sub_root = sub_root->right_child;
shorter = true;
delete to_delete;
return success;
}
else {
to_delete = sub_root->left_child;
Binary_node<Record> *parent = sub_root;
while (!to_delete->right_child) {
parent = to_delete;
to_delete = to_delete->left_child;
}
new_data = to_delete->data; //转化为对前驱的删除
sub_record = new_data;
}
}
if (new_data < sub_root->data) {
result = avl_remove(sub_root->left_child, new_data, shorter);
if (sub_record.the_key() != 0)sub_root->data = sub_record;
if (shorter == true) {
switch (sub_root->get_balance())
{
case left_higher:
sub_root->set_balance(equal_height);
break;
case equal_height:
sub_root->set_balance(right_higher);
break;
case right_higher:
shorter = right_balance2(sub_root);
break;
}
}
}
if (new_data > sub_root->data) {
result = avl_remove(sub_root->right_child, new_data, shorter);
if (shorter == true) {
switch (sub_root->get_balance())
{
case left_higher:
shorter=left_balance2(sub_root);
break;
case equal_height:
break;
sub_root->set_balance(left_higher);
case right_higher:
sub_root->set_balance(equal_height);
break;
}
}
}
return result;
}
由于删除操作出现的情况多于插入操作（5种），会出现R-，L-两种不同情况，所以左调整（left_balance）和右调整（right_balance)函数需要做修改。
代码如下：
template<class Record>
bool AVL_tree<Record>::right_balance2(Binary_node<Record>*& sub_root)
{
bool shorter;
Binary_node<Record> *&right_tree = sub_root->right_child;
switch (right_tree->get_balance()) {
case right_higher: //RR height--
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
rotate_left(sub_root);
shorter = true;
break;
case equal_height: //R- height doesn't change
right_tree->set_balance(left_higher);
rotate_left(sub_root);
shorter = false;
break;
case left_higher: //RL height--
Binary_node<Record> *sub_tree = right_tree->left_child;
switch (sub_tree->get_balance()) {
case equal_height:
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
break;
case left_higher:
sub_root->set_balance(equal_height);
right_tree->set_balance(right_higher);
break;
case right_higher:
sub_root->set_balance(left_higher);
right_tree->set_balance(equal_height);
break;
}
sub_tree->set_balance(equal_height);
rotate_right(right_tree);
rotate_left(sub_root);
shorter = true;
break;
}
return shorter;
}
template<class Record>
bool AVL_tree<Record>::left_balance2(Binary_node<Record>*& sub_root)
{
bool shorter;
Binary_node<Record> *&left_tree = sub_root->left_child;
switch (left_tree->get_balance()) {
case left_higher: //LL height--
sub_root->set_balance(equal_height);
left_tree->set_balance(equal_height);
rotate_right(sub_root);
shorter = true;
break;
case equal_height: //L- height doesn't change
left_tree->set_balance(right_higher);
rotate_right(sub_root);
shorter = false;
break;
case right_higher: //LR height--
Binary_node<Record> *sub_tree = left_tree->left_child;
switch (sub_tree->get_balance()) {
case equal_height:
sub_root->set_balance(equal_height);
left_tree->set_balance(equal_height);
break;
case left_higher:
left_tree->set_balance(equal_height);
sub_root->set_balance(right_higher);
break;
case right_higher:
sub_root->set_balance(equal_height);
left_tree->set_balance(left_higher);
break;
}
sub_tree->set_balance(equal_height);
rotate_left(left_tree);
rotate_right(sub_root);
shorter = true;
break;
}
return shorter;
}
tree-form data structure summary
原文：http://blog.csdn.net/yuchenchenyi/article/details/51571108