heap树的每一个父节点的都比它的两个子节点要大或者要小，父节点比子节点大的称之为大堆树，反之父节点比子节点小的称之为小堆树。
举例子构造一个heap树就什么都明白了，以大堆树为例
用这样(24,49,13,20,59,23,90,35)的一组数据来构造一个大堆树
如何构造呢
1. 24根节点
24
2. 49,挂在24左子节点，但49比24大，交换
49 49
/ \
24
3. 13,挂在49的右子节点,同时13又比49小，不交换
49
/ \
24 13
4. 20，挂在24左子节点，同时20又比24小，不交换
49
/ \
24 13
/
20
5. 59,挂在24的右子节点，59比24大，交换，59比49大，交换
59
/ \
49 13
/ \
20 24
6. 23,挂在13的左子节点，23比13大，交换，23比59小，不交换
59
/ \
49 23
/ \ / \
20 24 13
7. 90,挂在23的右子节点，但90比23大,交换,90比59大，交换
90
/ \
49 59
/ \ / \
20 24 13 23
8. 35，挂在20左子节点，但35比20大,交换,35比49小，不交换
90
/ \
49 23
/ \ / \
35 24 13 23
/
20
AVL树，自平衡二叉查找树，它的每一个父节点的左子树都比父节点要小，右子树都比父节点要大。这里涉及到一个左旋和右旋的问题，先来讲讲什么是左旋，什么是右旋。以下面树为例，下面的书是一个最小不平衡二叉树，我们看到b1子节点到a节点的深度为3，a1到a的深度为1，两者深度差了2，所以称为不平衡。我们看看右旋后得到的树
a c
/ \ / \
c a1 右旋 b a
/ \ / / \
b c1 b1 c1 a1
/
b1
我们来总结下右旋的法则：将c的父节点和右子节点断开，将a作为c的右子节点，c1为a的左子节点
同理，我们看下左旋
a c
/ \ / \
a1 c a c1
/ \ / \ \
b c1 左旋 a1 b b1
\
b1
最小不平衡2叉树发生自旋的四种情况：
单向右旋平衡处理RR：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；
单向左旋平衡处理LL：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；
双向旋转（先左后右）平衡处理LR：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
双向旋转（先右后左）平衡处理RL：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。
最后举个例子什么都明白了，还是用(24,49,13,20,59,23,90,35)，我们来构造一个AVL树,来看看结果
24
/ \
20 59
/ \ / \
13 23 49 90
/
35
阅读(2351) | 评论(0) | 转发(0) |
