keep coding
0%

avl平衡树

发表于 更新于 分类于 Disqus：
本文字数： 8.9k 阅读时长 ≈ 8 分钟

avl树是自带有平衡条件的二叉树，平常的二叉树在插入数据的很可能造成树的左子树或者右子树过长。造成查询是线性。avl要保持树的深度是logN。最简单的想法是要求左右紫薯具有相同的高度。一颗avl树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。

当我们插入的时候必须保证avl树的特性，即是左右子树的高度差最多是1，分析插入的特性我们发现有以下四种情况

当我们插入的时候必须保证avl树的特性，即是左右子树的高度差最多是1，分析插入的特性我们发现有以下四种情况：

基于二叉树的定义可以发现，发生不满足的【不平衡的时候】存在以下四种情况

  • 1.当前节点的左子树的左子树在进行一次插入。熟称LL。

  • 2.当前节点的左子树的右子树在进行一次插入。熟称LR。

  • 3.当前节点的右子树的右子树在进行一次插入。熟称RR。

  • 4.当前节点的右子树的左子树在进行一次插入。熟称RL

操作avl时候一些特性:

当我们定义节点的时候，每个节点保存自己的高度因子：高度因子：空节点 是 -1，因子只能在 0，-1，1之间取值。新插入的节点默认高度因子是0;计算高度因子：节点的高度因子 = max(左子树的高度因子 , 右子树的高度因子) 加 1.当一个节点新插入子节点后需要重新 计算该节点的高度因子，用来检查是否符合平衡条件在失去平衡的时候，可以看出 1，4是镜像问题，2，3是镜像问题.

下图是LL失去平衡的例子:

此时我们需要作出反转:

代码如下：

1
2
3
4
5
6
7
 public function leftSigon(Node node) {          $k1 = node->left;//也即是 4 节点             $node->left = $k1->right;//
             $k1->right  = $node;//4节点的右子树为
             $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;//重新计算右子树的高度
             $k1->height = max($this->getHeight($k1->left),$this->getHeight($k1->right)) + 1;//重新计算高度因子
//因为4节点的左子树没动所以不用重新计算高度
             return $k1;
         }

当出现RR插入的时候，也就是 右右插入的时候其实和LL的镜像问题:

所以RR的代码是:

1
2
3
4
5
6
7
8
9
public function rightSigon(Node node) {
             $k1 = node->right                ;//也即是 8 节点
             $node->right = $k1->left;//父节点的右节点为子节点的做节点【二叉树定义可知 右子树大于父节点，所以右子树下的左节点作为父节点的右子树】
             $k1->left  = $node;//右子树的做节点为父节点，转换完毕
             //重新计算 高度因子值
             $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;
             $k1->height = max($this->getHeight($k1->left),$this->getHeight($k1->right)) + 1;
             return $k1;
         }

当出现RL的时候：

1
2
3
4
5
6
//RL代码
public function RLSigon(Node $node)
      {
          $node->right = $this->leftSigon($node->right); //LL情况下旋转
          return $this->rightSigon($node);//RR情况下旋转
      }

LR是和RL镜像问题：

1
2
3
4
5
public function LRSigon(Node $node)
      {
          $node->left = $this->rightSigon($node->left);//先处理RR情况
          return $this->leftSigon($node);//在处理LL情况
      }

删除分析：当删除的元素只有右子树或者左子树，且右子树或左子树是叶子节点，也就是说右子树，左子树他们没有相应的子树时候就会失去平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public function delRecursion(Node $node, $value)
{
    if ($value > $node->value) {
        $node->right = $this->delRecursion($node->right, $value);
        $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;
        if ($this->getHeight($node->left) - $this->getHeight($node->right) == 2) {
            $node = $this->leftSigon($node);
        }
    } else if ($value < $node->value) {
        $node->left = $this->delRecursion($node->left, $value);
        $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;
        if ($this->getHeight($node->right) - $this->getHeight($node->left) == 2) {
            $node = $this->rightSigon($node);
        }
    } else {
        if ($node->left && $node->right) {
            $tmp = $this->findMin($node->right);
            $node->value = $tmp->value;
            $node->right = $this->delRecursion($node->right, $tmp->value);
            $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;
        } else if ($node->left || $node->right) {
            $node = $node->left ? $node->left : $node->right;
            $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;
        } else {
            $node = null;
        }

    }

    return $node;
}

/**
 * @param Node $node
 * @return Node|null
 */
public function findMin(Node $node)
{
    while ($node->left) {
        $node = $node->left;
    }
    return $node;
}

完整代码:

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
<?php
/**
 * Created by PhpStorm.
 * User: lhs
 * Date: 2019-07-05
 * Time: 13:21
 */

/**
 * AVL平衡树
 *
 */
class Node
{
    public $value = null;//值

    /**
     * @var Node
     */
    public $left = null;//左子结点

    /**
     * @var Node
     */
    public $right = null;//右子结点

    /**
     * @var Node
     */
    public $parent;

    /**
     * @var int
     */
    public $height = 0;//高度

    public function __construct($value)
    {
        $this->value = $value;
    }


}


/**
 * Class AvlTree
 */
class AvlTree
{

    /**
     * 空节点-1，如果是节点返回节点的高度。
     * @param Node $node
     * @return int
     */
    public function getHeight($node)
    {
        if ($node == null) {
            return -1;
        } else {
            return $node->height;
        }
    }

    /**
     * 左
     * @param Node $node
     * @return Node
     */
    public function leftSigon(Node $node)
    {
        /**
         * @var Node $k1 ;
         */
        $k1           = $node->left;//也即是 4 节点
        $node->left   = $k1->right;
        $k1->right    = $node;
        $node->height = max($this->getHeight($node->left), $this->getHeight($node->right)) + 1;
        $k1->height   = max($this->getHeight($k1->left), $this->getHeight($k1->right)) + 1;
        return $k1;
    }

    /**
     * 右
     * @param Node $node
     * @return Node
     */
    public function rightSigon(Node $node)
    {
        /**
         * @var Node $k1 ;
         */
        $k1          = $node->right;//也即是 8 节点
        $node->right = $k1->left;//父节点的右节点为子节点的做节点【二叉树定义可知 右子树大于父节点，所以右子树下的左节点作为父节点的右子树】
        $k1->left    = $node;//右子树的做节点为父节点，转换完毕
        //重新计算 高度因子值
        $node->height = max($this->getHeight($node->left), $this->getHeight($node->right)) + 1;
        $k1->height   = max($this->getHeight($k1->left), $this->getHeight($k1->right)) + 1;
        return $k1;
    }


    /**
     * @param Node $node
     * @return Node
     */
    public function LRSigon(Node $node)
    {
        $node->left = $this->rightSigon($node->left);
        return $this->leftSigon($node);
    }


    
    /**
     * @param Node $node
     * @return mixed
     */
    public function RLSigon(Node $node)
    {
        $node->right = $this->leftSigon($node->right);
        return $this->rightSigon($node);
    }


    /**
     * @param $x
     * @param Node $node
     * @return Node
     */
    public function insert($x, $node)
    {
        if ($node == null) {
            $node         = new Node($x);
            $node->left   = $node->right = null;
            $node->height = 0;
        } else if ($x < $node->value) {
            $node->left = $this->insert($x, $node->left);
            if ($this->getHeight($node->left) - $this->getHeight($node->right) == 2) {
                if ($x < $node->left->value) {//LL情况
                    $node = $this->leftSigon($node);
                } else {
                    $node = $this->LRSigon($node);//LR情况
                }
            }
        } else if ($x > $node->value) {
            $node->right = $this->insert($x, $node->right);
            if ($this->getHeight($node->right) - $this->getHeight($node->left) == 2) {
                if ($x > $node->right->value) {//RR情况
                    $node = $this->rightSigon($node);
                } else {
                    $node = $this->RLSigon($node);//RL情况
                }
            }
        }

        $node->height = max($this->getHeight($node->left), $this->getHeight($node->right)) + 1;//重新计算高度因子
        return $node;
    }

    /**
     * @param $node
     * @param $space
     */
    public function printTree($node, $space = '')
    {
        if ($node) {
            echo $space . $node->value . "[" . $node->height . "]" . PHP_EOL;
            $this->printTree($node->left, $space . "   ");
            $this->printTree($node->right, $space . "   ");
        }


    }


    /**
     * @param Node $node
     * @param $value
     * @return Node|null
     */
    public function delRecursion(Node $node, $value)
    {
        if ($value > $node->value) {
            $node->right = $this->delRecursion($node->right, $value);
            $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;
            if ($this->getHeight($node->left) - $this->getHeight($node->right) == 2) {
                $node = $this->leftSigon($node);
            }
        } else if ($value < $node->value) {
            $node->left = $this->delRecursion($node->left, $value);
            $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;
            if ($this->getHeight($node->right) - $this->getHeight($node->left) == 2) {
                $node = $this->rightSigon($node);
            }
        } else {
            if ($node->left && $node->right) {
                $tmp = $this->findMin($node->right);
                $node->value = $tmp->value;
                $node->right = $this->delRecursion($node->right, $tmp->value);
                $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;
            } else if ($node->left || $node->right) {
                $node = $node->left ? $node->left : $node->right;
                $node->height = max($this->getHeight($node->left),$this->getHeight($node->right)) + 1;
            } else {
                $node = null;
            }

        }

        return $node;
    }

    /**
     * @param Node $node
     * @return Node|null
     */
    public function findMin(Node $node)
    {
        while ($node->left) {
            $node = $node->left;
        }
        return $node;
    }
}

$node = null;

$arr = [3,2,1,4,5,6,7,16,15,14,13];
//$arr = [6,5,7,4];
//$arr = [6,5,7];
//$arr = [6,7];
$avl = new AvlTree();
foreach ($arr as $val) {
    echo $val . ':::::' . PHP_EOL;
    $node = $avl->insert($val, $node);
   // $avl->printTree($node);
    echo $node->value . ':::::' . PHP_EOL;
    echo "*****************" . PHP_EOL;
}

$avl->printTree($node);
$node = $avl->delRecursion($node,  '7');
$avl->printTree($node);