1+ // 定义节点
2+ class Node {
3+ constructor ( key , value ) {
4+ this . key = key ;
5+ this . value = value ;
6+ this . left = null ;
7+ this . right = null ;
8+ this . height = 1 ;
9+ }
10+ }
11+
12+ // 定义AVL树
13+ module . exports = class AVLTree {
14+ constructor ( ) {
15+ this . root = null ;
16+ this . size = 0 ;
17+ }
18+ // 判断该二叉树是否是一课二分搜索树
19+ isBST ( ) {
20+ let keys = [ ] ;
21+ this . inOrder ( this . root , keys ) ;
22+ for ( let i = 1 ; i < keys . length ; i ++ ) {
23+ if ( keys [ i - 1 ] > keys [ i ] ) {
24+ return false ;
25+ }
26+ }
27+ return true ;
28+ }
29+ inOrder ( node , keys ) {
30+ if ( node === null )
31+ return ;
32+ this . inOrder ( node . left , keys ) ;
33+ keys . push ( node . key ) ;
34+ this . inOrder ( node . right , keys ) ;
35+ }
36+ // 判断该二叉树是否是一棵平衡二叉树,递归算法
37+ isBalanced ( ) {
38+ return this . _isBalanced ( this . root ) ;
39+ }
40+ _isBalanced ( node ) {
41+ if ( node === null )
42+ return true ;
43+ let balanceFactor = this . getBalanceFactor ( node ) ;
44+ if ( Math . abs ( balanceFactor ) > 1 )
45+ return false ;
46+ return this . _isBalanced ( node . left ) && this . _isBalanced ( node . right ) ;
47+ }
48+ // 获得节点node的高度
49+ getHeight ( node ) {
50+ if ( node === null )
51+ return 0 ;
52+ return node . height ;
53+ }
54+ // 获得节点node的平衡因子
55+ getBalanceFactor ( node ) {
56+ if ( node === null )
57+ return 0 ;
58+ return this . getHeight ( node . left ) - this . getHeight ( node . right ) ;
59+ }
60+ // 向二分搜索树添加新的元素(key, value)
61+ add ( key , value ) {
62+ this . root = this . _add ( this . root , key , value ) ;
63+ }
64+ // 向以node为根的二分搜索树中插入元素(key, value),递归算法
65+ // 返回插入新节点后二分搜索树的根
66+ _add ( node , key , value ) {
67+ if ( node === null ) {
68+ this . size ++ ;
69+ return new Node ( key , value ) ;
70+ }
71+ // 如果key小于节点的key，则插入到节点的左子树中
72+ if ( key < node . key ) {
73+ node . left = this . _add ( node . left , key , value ) ;
74+ } else if ( key > node . key ) {
75+ // 如果key大于节点的key，则插入到节点的右子树中
76+ node . right = this . _add ( node . right , key , value ) ;
77+ } else {
78+ // 更新操作
79+ node . value = value ;
80+ }
81+
82+ // 更新height
83+ node . height = 1 + Math . max ( this . getHeight ( node . left ) , this . getHeight ( node . right ) ) ;
84+
85+ // 计算平衡因子
86+ let balanceFactor = this . getBalanceFactor ( node ) ;
87+ // 在II的代码中添加调节平衡的方法
88+ if ( Math . abs ( balanceFactor ) > 1 ) {
89+ console . log ( 'unbalanced:' + balanceFactor ) ;
90+ }
91+ return node ;
92+ }
93+ // 返回以node为根节点的二分搜索树中，key所在节点
94+ getNode ( node , key ) {
95+ if ( node === null )
96+ return null ;
97+ if ( key . equals ( node . key ) )
98+ return node ;
99+ else if ( key < node . key )
100+ return this . getNode ( node . left , key ) ;
101+ else
102+ return this . getNode ( node . right , key ) ;
103+ }
104+ // 判断是否包含该node
105+ contains ( key ) {
106+ return this . getNode ( this . root , key ) !== null ;
107+ }
108+ // 根据key值获取节点
109+ get ( key ) {
110+ let node = this . getNode ( this . root , key ) ;
111+ return node === null ? null : node . value ;
112+ }
113+ // 设置node的值
114+ set ( key , value ) {
115+ let node = this . getNode ( this . root , key ) ;
116+ return node === null ? null : node . value ;
117+ }
118+ // 返回以node为根的二分搜索树的最小值所在节点
119+ minimun ( node ) {
120+ if ( node . left === null )
121+ return node ;
122+ return this . minimun ( node ) ;
123+ }
124+ // 删除掉以node为根的二分搜索树中的最小节点
125+ // 返回删除节点后新的二分搜索树的根
126+ removeMin ( node ) {
127+ if ( node . left === null ) {
128+ let rightNode = node . right ;
129+ node . right = null ;
130+ this . size -- ;
131+ return rightNode ;
132+ }
133+ node . left = this . removeMin ( node . left ) ;
134+ return node ;
135+ }
136+ // 从二分搜索树中删除键为key的节点
137+ remove ( key ) {
138+ let node = this . getNode ( this . root , key ) ;
139+ if ( node !== null ) {
140+ this . root = this . _remove ( this . root , key ) ;
141+ return node . value ;
142+ }
143+ return null ;
144+ }
145+ _remove ( node , key ) {
146+ if ( node === null ) {
147+ return null ;
148+ }
149+
150+ if ( key < node . key ) {
151+ node . left = this . _remove ( node . left , key ) ;
152+ return node ;
153+ } else if ( key > node . key ) {
154+ node . right = this . _remove ( node . right , key ) ;
155+ return node ;
156+ }
157+ else {
158+ // 待删除节点左子树为空的情况
159+ if ( node . left === null ) {
160+ let rightNode = node . right ;
161+ node . right = null ;
162+ this . size -- ;
163+ return rightNode ;
164+ }
165+ // 待删除节点右子树为空的情况
166+ if ( node . right === null ) {
167+ let leftNode = node . left ;
168+ node . left = null ;
169+ this . size -- ;
170+ return leftNode ;
171+ }
172+
173+ // 待删除节点左右子树均不为空的情况
174+
175+ // 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
176+ // 用这个节点替换待删除节点的位置
177+ let successor = this . minimun ( node . right ) ;
178+ successor . right = this . removeMin ( ndoe . right ) ;
179+ successor . left = node . left ;
180+
181+ node . left = node . right = null ;
182+
183+ return successor ;
184+ }
185+ }
186+ // 获取树的大小
187+ getSize ( ) {
188+ return this . size ;
189+ }
190+ // 判断树是否为空
191+ isEmpty ( ) {
192+ return this . size === 0 ;
193+ }
194+ }
0 commit comments