JavaScript数据结构——树的实现
- 时间:
- 浏览:0
在计算机科学中,树是五种十分重要的数据形态。树被描述为五种分层数据抽象模型,常用来描述数据间的层级关系和组织形态。树也是五种非顺序的数据形态。下图展示了树的定义:
在介绍怎么都可以 用JavaScript实现树前一天,大伙儿儿先介绍某些和树相关的术语。
如上图所示,一棵完整的树中含一个 多处在树顶部的节点,称之为根节点(11),它这麼父节点。树中的每一个 多元素都叫做一个 多节点,节点分为内部管理节点(图中显示为黄色的节点)和内部管理节点(图中显示为灰色的节点),合适一个 多子节点的节点称为内部管理节点,这麼子元素的节点称为内部管理节点或叶子节点。一个 多节点可需要有祖先(根节点除外)和后代。子树由节点五种和它的后代组成,如上图中三角虚框中的次责好多好多 一棵子树。节点拥有的子树的个数称之为节点的度,如上图中除叶子节点的度为0外,其余节点的度都为2。从根节点结速英语 ,根为第1层,第一级子节点为第2层,第二级子节点为第3层,以此类推。树的强度(强度)由树中节点的最大层级决定(上图中树的强度为4)。
在一棵树中,具有相同父节点的一组节点称为兄弟节点,如上图中的3和6、5和9等都会兄弟节点。
二叉树
二叉树中的节点最多非要一个 多子节点,一个 多是左子节点,一个 多是右子节点。左右子节点的顺序非要颠倒。或者,二叉树中不处在度大于2的节点。
二叉搜索树(BST——Binary Search Tree)是二叉树的五种,它规定在左子节点上存储小(比父节点)的值,在右子节点上(比父节点)存储大(或等于)的值。上图好多好多 一个 多二叉搜索树。
下面大伙儿儿重点来看一下二叉搜索树的实现。
根据二叉树的描述,一个 多节点最多只一个 多子节点,大伙儿儿可需要使用《JavaScript数据形态——链表的实现与应用》一文中的双向链表来实现二叉搜索树中的每一个 多节点。下面是二叉搜索树的数据形态示意图:
以下是大伙儿儿要实现的BinarySearchTree类的骨架次责:
class BinarySearchTree { constructor () { this.root = null; } // 向树中插入一个 多节点 insert (key) {} // 在树中查找一个 多节点 search (key) {} // 通过中序遍历辦法 遍历树中的所有节点 inOrderTraverse () {} // 通过先序遍历辦法 遍历树中的所有节点 preOrderTraverse () {} // 通前一天序遍历辦法 遍历树中的所有节点 postOrderTraverse () {} // 返回树中的最小节点 min () {} // 返回树中的最大节点 max () {} // 从树中移除一个 多节点 remove (key) {} }
先来看看向树中加在一个 多节点。大伙儿儿借用《JavaScript数据形态——链表的实现与应用》一文中的双向链表DoubleLinkedList类来模拟树中的节点,在DoubleLinkedList类中,每一个 多节点一个 多属性:element、next和prev。大伙儿儿在这里用element表示树中节点的key,用next表示树中节点的右子节点(right),用prev表示树中节点的左子节点(left)。
insert (key) { let newNode = new Node(key); if (this.root === null) this.root = newNode; else insertNode(this.root, newNode); }
当树的root为null时,表示树为空,这时直接将新加在的节点作为树的根节点。或者,大伙儿儿需要借助于私有函数insertNode()来完成节点的加在。在insertNode()函数中,大伙儿儿需要根据新加在节点的key的大小来递归查找树的左侧子节点机会右侧子节点,机会根据大伙儿儿的二叉搜索树的定义,值小的节点永远保处在左侧子节点上,值大的节点(包括值相等的请况)永远保处在右侧子节点上。下面是insertNode()函数的实现代码:
let insertNode = function (node, newNode) { if (newNode.element < node.element) { if (node.prev === null) node.prev = newNode; else insertNode(node.prev, newNode); } else { if (node.next === null) node.next = newNode; else insertNode(node.next, newNode); } };
所有新节点非要作为叶子节点被加在到树中。在本文一结速英语 给出的树的形态图中,机会要加在节点2,对应的操作步骤如下:
大伙儿儿传入树的根节点,依次进行递归,找到对应的叶子节点,或者修改节点的prev(左子节点)或next(右子节点)指针,使其指向新加在的节点。在上例中,机会要加在节点4,它对应的位置应该是节点3的右子节点,机会4比3大。机会要加在节点21,对应的位置应该是节点25的左子节点......
下面大伙儿儿来看看树的五种遍历辦法 :
- 前序遍历(NLR——Preorder Traversal)也叫先序遍历,访问根节点的操作处在在遍历其左右子树前一天。
- 中序遍历(LNR——Inorder Traversal),访问根节点的操作处在在遍历其左右子树之间。
- 后序遍历(LRN——Postorder Traversal),访问根节点的操作处在在遍历其左右子树前一天。
下面的一个 多辦法 对应树的五种遍历辦法 :
// 前序遍历 let preOrderTraverseNode = function (node, callback) { if (node !== null) { callback(node.element); preOrderTraverseNode(node.prev, callback); preOrderTraverseNode(node.next, callback); } }; // 中序遍历 let inOrderTraverseNode = function (node, callback) { if (node !== null) { inOrderTraverseNode(node.prev, callback); callback(node.element); inOrderTraverseNode(node.next, callback); } }; // 后续遍历 let postOrderTraverseNode = function (node, callback) { if (node !== null) { postOrderTraverseNode(node.prev, callback); postOrderTraverseNode(node.next, callback); callback(node.element); } };
可需要就看,这些 个 多函数的内容很同类,好多好多 调整了左右子树和根节点的遍历顺序。这里的callback是一个 多回调函数,可需要传入任何你想执行的函数,这里大伙儿儿传入的函数内容是打印树的节点的key值。大伙儿儿将BinarySearchTree类的这些 个 多遍历辦法 的内容补充完整:
preOrderTraverse (callback) { preOrderTraverseNode(this.root, callback); } inOrderTraverse (callback) { inOrderTraverseNode(this.root, callback); } postOrderTraverse (callback) { postOrderTraverseNode(this.root, callback); }
为了构建本文一结速英语 的那棵树,大伙儿儿执行下面的代码,或者测试preOrderTraverse()辦法 :
let tree = new BinarySearchTree(); tree.insert(11); tree.insert(7); tree.insert(15); tree.insert(5); tree.insert(9); tree.insert(13); tree.insert(20); tree.insert(3); tree.insert(6); tree.insert(8); tree.insert(10); tree.insert(12); tree.insert(14); tree.insert(18); tree.insert(25); tree.preOrderTraverse((value) => console.log(value));
注意节点插入的顺序,顺序不同,你机会会得到不一样的树。preOrderTraverse()辦法 采用ES6的语法传入了一个 多匿名函数作为参数callback的值,这些 匿名函数的主要作用好多好多 打印树中节点的key值,可需要对照上边一个 多遍历树节点的函数中的callback(node.element)语录,这里的callback好多好多 这些 匿名函数,node.element好多好多 节点的key值(还记得前面大伙儿儿说过,借用双向链表类DoubleLinkedList来模拟树的节点吗?)下面是前序遍历的执行结果:
11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
大伙儿儿参照前序遍历的定义,借住下面的示意图来理解整个遍历过程:
在前序遍历函数preOrderTraverseNode()中,先执行callback(node.element),或者再依次递归左子树和右子树。大伙儿儿将树的根节点作为第一个 多节点传入,首先打印的好多好多 根节点11,或者结速英语 遍历左子树,这将依次打印左子树中的所有左子节点,依次是7、5、3。当节点3的prev为null时,递归返回,继续查找节点3的右子节点,此下午英语 点3的next值也为null,于是继续向上返回到节点5,结速英语 遍历节点5的右子节点,于是打印节点6......最终所有的节点就按照这些 递归顺序进行遍历。
或者大伙儿儿再来看看中序遍历的请况。
tree.inOrderTraverse((value) => console.log(value));
3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
在中序遍历函数inOrderTraverseNode()中,先递归左子树,或者执行callback(node.element),最后再递归右子树。同样的,大伙儿儿将根节点作为第一个 多节点传入,递归到左子树的最后一个 多左子节点3,机会节点3的prev为null,好多好多 递归返回,打印节点3,或者继续查找节点3的右子节点,节点3的next值也为null,递归返回到上一层节点5,结速英语 打印节点5,前一天再查找节点5的右子节点......最终整棵树按照这些 顺序完成遍历。
最后再来看就看序遍历的请况。
tree.postOrderTraverse((value) => console.log(value));
3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
在后序遍历函数postOrderTraverseNode()中,先递归左子树,或者再递归右子树,最后执行callback(node.element)。同样的,大伙儿儿将根节点作为第一个 多节点传入,递归到左子树的最后一个 多左子节点3,机会节点3的prev为null,好多好多 递归返回,此时继续查找节点3的右子节点,节点3的next值也为null,递归返回并打印节点3,前一天递归返回到上一层节点5,结速英语 查找节点5的右子节点,节点5的右子节点是节点6,机会节点6是叶子节点,好多好多 直接打印节点6,或者递归返回并打印节点5。前一天递归再向上返回到节点7并递归节点7的右子节点......按照这些 顺序最终完成对整棵树的遍历。
接下来大伙儿儿再来看看对树的搜索。有五种要经常执行的搜索辦法 :
- 搜索树中的最小值
- 搜索树中的最大值
- 搜索树中的特定值
搜索树中的最小值和最大值比较简单,机会大伙儿儿的二叉搜索树规定了值小的节点永远在左子树(左子节点)中,值大(或相等)的节点永远在右子树(右子节点)中,好多好多 ,搜索最大值大伙儿儿只需要递归查找树的右子树直到叶子节点,就能找到值最大的节点。搜索最小值只需要递归查找树的左子树直到叶子节点,就能找到值最小的节点。下面是这些 个 多函数的实现:
let minNode = function (node) { if (node === null) return null; while (node && node.prev !== null) { node = node.prev; } return node; }; let maxNode = function (node) { if (node === null) return null; while (node && node.next !== null) { node = node.next; } return node; };
第五种辦法 是搜索特定的值,大伙儿儿需要比较要搜索的值与当前节点的值,机会要搜索的值小于当前节点的值,则从当前节点结速英语 递归查找左子数(左子节点)。机会要搜索的值大于当前节点的值,则从当前节点结速英语 递归查找右子树(右子节点)。按照这些 逻辑,大伙儿儿的searchNode()函数实现如下:
let searchNode = function (node, key) { if (node === null) return null; if (key < node.element) return searchNode(node.prev, key); else if (key > node.element) return searchNode(node.next, key); else return node; };
机会找到了对应的节点,就返回该节点,或者就返回null。大伙儿儿将BinarySearchTree类的这些 个 多搜索辦法 的内容补充完整:
search (key) { return searchNode(this.root, key); } min () { return minNode(this.root); } max () { return maxNode(this.root); }
下面是某些测试用例及结果:
console.log(tree.min().element); // 3 console.log(tree.max().element); // 25 console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.'); // Key 1 not found. console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.'); // Key 8 found.
让大伙儿儿来看一下search()辦法 的执行过程是怎么都可以 的。
搜索key=1的节点,首先大伙儿儿传入树的根节点和key=1,机会1小于根节点的值11,递归查找根节点的左子节点7,1<7,继续查找节点7的左子节点,直到找到叶子节点3,1仍然小于3,或者节点3这麼左子节点了,好多好多 返回false,整个递归结速英语 向上返回,最终返回的结果是false,表示树中这麼key=1的节点。
相应地,对于搜索key=8的节点,也是先遍历根节点的左子节点7,机会8>7,好多好多 会遍历节点7的右子节点,找到节点9,8<9,遍历节点9的左子节点,此时找到节点9的左子节点正好是8,好多好多 返回true,或者整个递归向上返回,最终的返回结果好多好多 true,表示树中找到了key=8的节点。
最后大伙儿儿再来看一下从树中移除一个 多节点的过程,这些 过程要稍微错综复杂某些。先来看看删除树节点的函数removeNode()的代码,稍后大伙儿儿再来完整讲解整个执行过程。
let removeNode = function (node, key) { if (node === null) return null; if (key < node.element) { node.prev = removeNode(node.prev, key); return node; } else if (key > node.element) { node.next = removeNode(node.next, key); return node; } else { // 第五种请况:一个 多叶子节点(这麼子节点) if (node.prev === null && node.next === null) { node = null; return node; } // 第二种请况:只中含一个 多子节点 if (node.prev === null) { node = node.next; return node; } else if (node.next === null) { node = node.prev; return node; } // 第五种请况:一个 多子节点 let aux = minNode(node.next); node.element = aux.element; node.next = removeNode(node.next, aux.element); return node; } };
首很难找到树中待删除的节点,这需要进行递归遍历,从根节点结速英语 ,机会key值小于当前节点的值,则遍历左子树,机会key值大于当前节点的值,则遍历右子树。注意,在递归遍历的过程中,大伙儿儿将node(这里的node传入的是树的根节点)的prev指针或next指针逐级指向下一级节点,或者返回整个node。当找到要删除的节点后,大伙儿儿要解决五种请况:
- 该节点为叶子节点(这麼子节点)
- 该节点只一个 多子节点(左子节点或右子节点)
- 该节点一个 多子节点(左右子节点都处在)
大伙儿儿先看第五种请况:
假设大伙儿儿要删除节点6,传入根节点11,整个执行过程如下:
- node=11,key=6,6<11,递归执行removeNode(7, 6)
- node=7,key=6,6<7,递归执行removeNode(5, 6)
- node=5,key=6,6>5,递归执行removeNode(6, 6)
- node=6,key=6,6=6,或者节点6的prev和next都为null,好多好多 大伙儿儿将节点6设置为null,或者返回null
- 递归返回到步骤3,节点5的next将获取步骤4的返回值null
- 递归返回到步骤2,节点7的prev依然指向节点5,保持不变
- 递归返回到步骤1,节点11的prev依然指向节点7,保持不变
- 最后返回节点11
或者大伙儿儿来看只一个 多子节点的请况:
前面机会删除了节点6,假设大伙儿儿现在要删除节点5,它一个 多左子节点3,大伙儿儿依然传入根节点11,来看看整个执行过程:
- node=11,key=5,5<11,递归执行removeNode(7, 5)
- node=7,key=5,5<7,递归执行removeNode(5, 5)
- node=5,key=5,5=5,或者节点5的prev=3,next=null,好多好多 大伙儿儿将节点5替加在它的左子节点3,并返回节点3
- 递归返回到步骤2,节点7的next将获取步骤3的返回值3
- 递归返回到步骤1,节点11的prev依然指向节点7,保持不变
- 最后返回节点11
大伙儿儿需要将节点5从内存中删除,它会自动被JavaScript的垃圾回收器清理掉,这些 在《JavaScript数据形态——链表的实现与应用》一文中机会介绍过。以上步骤是针对目标节点有左子节点的请况,对于有右子节点请况,执行过程是同类的。
最后再来看第五种请况:
前面机会删除了节点6和节点5,现在大伙儿儿要删除节点15,它有左右子树,大伙儿儿传入根节点11,来看下具体执行过程:
- node=11,key=15,15>11,递归执行removeNode(15, 15)
- node=15,key=15,15=15,此时大伙儿儿需要找到节点15的右子树中的最小节点18,将节点15的key替加在节点18的key,或者将节点15的next节点(即节点20)作为起始节点进行遍历,找到并删除节点18,最后再将节点15(此时它的key是18)的next指针指向节点20,并返回节点15
- 递归返回到步骤1,节点11的next依然指向节点15,但此下午英语 点15的key机会变成18了
- 最后返回节点11
试想一下,当删除节点15前一天,为了保证大伙儿儿的二叉搜索树形态稳定,需要用节点15的右子树中的最小节点来替换节点15,机会直接将11的next指向20,则20机会一个 多子节点13、18、25,这显然机会不符合大伙儿儿二叉树的定义了。机会将节点25用来替换节点15,节点20的值比节点25的值小,不应该经常冒出在右子节点,这好多好多 符合大伙儿儿的二叉搜索树的定义。好多好多 ,非要按照上述过程还都可以 既保证不破坏树的形态,又能删除节点。
大伙儿儿机会完成了一结速英语 大伙儿儿定义的二叉搜索树BinarySearchTree类的所有辦法 ,下面是它的完整代码:
1 let insertNode = function (node, newNode) { 2 if (newNode.element < node.element) { 3 if (node.prev === null) node.prev = newNode; 4 else insertNode(node.prev, newNode); 5 } 6 else { 7 if (node.next === null) node.next = newNode; 8 else insertNode(node.next, newNode); 9 } 10 }; 11 12 let preOrderTraverseNode = function (node, callback) { 13 if (node !== null) { 14 callback(node.element); 15 preOrderTraverseNode(node.prev, callback); 16 preOrderTraverseNode(node.next, callback); 17 } 18 }; 19 20 let inOrderTraverseNode = function (node, callback) { 21 if (node !== null) { 22 inOrderTraverseNode(node.prev, callback); 23 callback(node.element); 24 inOrderTraverseNode(node.next, callback); 25 } 26 }; 27 28 let postOrderTraverseNode = function (node, callback) { 29 if (node !== null) { 60 postOrderTraverseNode(node.prev, callback); 31 postOrderTraverseNode(node.next, callback); 32 callback(node.element); 33 } 34 }; 35 36 let minNode = function (node) { 37 if (node === null) return null; 38 39 while (node && node.prev !== null) { 40 node = node.prev; 41 } 42 return node; 43 }; 44 45 let maxNode = function (node) { 46 if (node === null) return null; 47 48 while (node && node.next !== null) { 49 node = node.next; 60 } 51 return node; 52 }; 53 54 let searchNode = function (node, key) { 55 if (node === null) return false; 56 57 if (key < node.element) return searchNode(node.prev, key); 58 else if (key > node.element) return searchNode(node.next, key); 59 else return true; 60 }; 61 62 let removeNode = function (node, key) { 63 if (node === null) return null; 64 65 if (key < node.element) { 66 node.prev = removeNode(node.prev, key); 67 return node; 68 } 69 else if (key > node.element) { 70 node.next = removeNode(node.next, key); 71 return node; 72 } 73 else { 74 // 第五种请况:一个 多叶子节点(这麼子节点) 75 if (node.prev === null && node.next === null) { 76 node = null; 77 return node; 78 } 79 // 第二种请况:只中含一个 多子节点 60 if (node.prev === null) { 81 node = node.next; 82 return node; 83 } 84 else if (node.next === null) { 85 node = node.prev; 86 return node; 87 } 88 89 // 第五种请况:一个 多子节点 90 let aux = minNode(node.next); 91 node.element = aux.element; 92 node.next = removeNode(node.next, aux.element); 93 return node; 94 } 95 }; 96 97 class BinarySearchTree { 98 constructor () { 99 this.root = null; 60 } 101 102 // 向树中插入一个 多节点 103 insert (key) { 104 let newNode = new Node(key); 105 106 if (this.root === null) this.root = newNode; 107 else insertNode(this.root, newNode); 108 } 109 110 // 在树中查找一个 多节点 111 search (key) { 112 return searchNode(this.root, key); 113 } 114 115 // 通过先序遍历辦法 遍历树中的所有节点 116 preOrderTraverse (callback) { 117 preOrderTraverseNode(this.root, callback); 118 } 119 120 // 通过中序遍历辦法 遍历树中的所有节点 121 inOrderTraverse (callback) { 122 inOrderTraverseNode(this.root, callback); 123 } 124 125 // 通前一天序遍历辦法 遍历树中的所有节点 126 postOrderTraverse (callback) { 127 postOrderTraverseNode(this.root, callback); 128 } 129 160 // 返回树中的最小节点 131 min () { 132 return minNode(this.root); 133 } 134 135 // 返回树中的最大节点 136 max () { 137 return maxNode(this.root); 138 } 139 140 // 从树中移除一个 多节点 141 remove (key) { 142 this.root = removeNode(this.root, key); 143 } 144 }
自平衡树
上边的BST树(二叉搜索树)处在一个 多疑问,树的第二根边机会会非常深,而其它边却非要几层,这会在这条太深了的分支加在在、移除和搜索节点时引起某些性能疑问。如下图所示:
为了解决这些 疑问,大伙儿儿引入了自平衡二叉搜索树(AVL——Adelson-Velskii-Landi)。在AVL中,任何一个 多节点左右两棵子树的强度之差最多为1,加在或移除节点时,AVL树会尝试自平衡。对AVL树的操作和对BST树的操作一样,不同点在于大伙儿儿还需要重新平衡AVL树,在讲解对AVL树的平衡操作前一天,大伙儿儿先看一下那此是AVL树的平衡因子。
前面大伙儿儿介绍过那此是树(子树)的强度,对于AVL树来说,每一个 多节点都保存一个 多平衡因子。
节点的平衡因子 = 左子树的强度 - 右子树的强度
观察下面这棵树,大伙儿儿在上边标注了每个节点的平衡因子的值:
所有子节点的平衡因子都为0,机会子节点这麼子树。节点5的左右子树的强度都为1,好多好多 节点5的平衡因子是0。节点9的左子树强度为1,右子树强度为0,好多好多 节点9的平衡因子是+1。节点13的左子树强度为0,右子树强度为1,好多好多 节点13的平衡因子是-1......AVL树的所有节点的平衡因子保持一个 多值:0、+1或-1。一起,大伙儿儿也注意到,当某个节点的平衡因子为+1时,它的子树是向左倾斜的(left-heavy);而当某个节点的平衡因子为-1时,它的子树是向右倾斜的(right-heavy);当节点的平衡因子为0时,该节点是平衡的。一颗子树的根节点的平衡因子代表了该子树的平衡性。
为了使AVL树重新达到平衡请况,大伙儿儿需要对AVL树中的次责节点进行重新排列,使其既符合二叉搜索树的定义,又符合自平衡二叉树的定义,这些 过程叫做AVL树的旋转。
AVL树的旋转一共分为五种:
- LL(left-left)旋转,新加在的节点处在树的根节点的左子树的左子树上。以非平衡因子的节点为中心将整棵树向右旋转。
- LR(left-right)旋转,新加在的节点处在树的根节点的左子树的右子树上。先执行RR旋转,或者再执行LL旋转。
- RR(right-right)旋转,新加在的节点处在树的根节点的右子树的右子树上。以非平衡因子的节点为中心将整棵树向左旋转。
- RL(right-left)旋转,新加在的节点处在树的根节点的右子树的左子树上。先执行LL旋转,或者再执行RR旋转。
下面是这五种旋转的操作示意图,上边大伙儿儿会完整介绍每五种旋转的操作过程:
对于LL旋转,在节点5的右子节点加在在节点4与在左子节点加在在节点3等同。对于LR旋转,在节点9的左子节点加在在节点8与在右子节点加在在节点10等同。对于RR旋转,在节点20的右子节点加在在节点25与在左子节点加在在节点18等同。对于RL旋转,在节点13的右子节点加在在节点14与在左子节点加在在节点12等同。
大伙儿儿的自平衡二叉树AVLTree类将从BinarySearchTree类继承,一起大伙儿儿需要新增一个 多辦法 getNodeHeight()用来获取任意节点的强度。
class AVLTree extends BinarySearchTree { constructor () { super(); } // 计算节点的强度 getNodeHeight (node) { if (node === null) return 0; return Math.max(this.getNodeHeight(node.prev), this.getNodeHeight(node.next)) + 1; }; }
测试一下getNodeHeight()辦法 ,大伙儿儿还是以本文一结速英语 的那棵树为例,或者看一下不同节点的强度。
let tree = new AVLTree(); tree.insert(11); tree.insert(7); tree.insert(15); tree.insert(5); tree.insert(9); tree.insert(13); tree.insert(20); tree.insert(3); tree.insert(6); tree.insert(8); tree.insert(10); tree.insert(12); tree.insert(14); tree.insert(18); tree.insert(25); console.log(tree.getNodeHeight(tree.root)); // 4 console.log(tree.getNodeHeight(tree.search(7))); // 3 console.log(tree.getNodeHeight(tree.search(5))); // 2 console.log(tree.getNodeHeight(tree.min(7))); // 1
根节点的强度为4,最小节点3的强度为1,节点5和节点7的强度分别为2和3。
下面是五种旋转对应的实现代码:
/** * LL旋转: 向右旋转 * * b a * / \ / \ * a e -> rotationLL(b) -> c b * / \ / / \ * c d f d e * / * f * * @param node Node<T> */ rotationLL(node) { let tmp = node.prev; node.prev = tmp.next; tmp.next = node; return tmp; } /** * RR旋转: 向左旋转 * * a b * / \ / \ * c b -> rotationRR(a) -> a e * / \ / \ \ * d e c d f * \ * f * * @param node Node<T> */ rotationRR(node) { let tmp = node.next; node.next = tmp.prev; tmp.prev = node; return tmp; } /** * LR旋转: 先向左旋转,或者再向右旋转 * @param node Node<T> */ rotationLR(node) { node.prev = this.rotationRR(node.prev); return this.rotationLL(node); } /** * RL旋转: 先向右旋转,或者再向左旋转 * @param node Node<T> */ rotationRL(node) { node.next = this.rotationLL(node.next); return this.rotationRR(node); }
对于LL旋转和RR旋转,大伙儿儿可需要按照上边的示意图来看下执行过程。
LL旋转,node=11,node.prev是7,好多好多 tmp=7。或者将node.prev指向tmp.next,即将11的prev指向9。接着将tmp.next指向node,即将7的next指向11。即完成了图中所示的旋转。
RR旋转,node=11,node.next是15,好多好多 tmp=15。或者将node.next指向tmp.prev,即将11的next指向13。接着将tmp.prev指向node,即将15的prev指向11。即完成了图中所示的旋转。
LR旋转是RR旋转和LL旋转的组合:
RL旋转是LL旋转和RR旋转的组合:
按照上边给出的示意图,大伙儿儿的AVLTree类的insert()辦法 的实现如下:
insert (key) { super.insert(key); // 左子树强度大于右子树强度 if (this.getNodeHeight(this.root.prev) - this.getNodeHeight(this.root.next) > 1) { if (key < this.root.prev.element) { this.root = this.rotationLL(this.root); } else { this.root = this.rotationLR(this.root); } } // 右子树强度大于左子树强度 else if (this.getNodeHeight(this.root.next) - this.getNodeHeight(this.root.prev) > 1) { if (key > this.root.next.element) { this.root = this.rotationRR(this.root); } else { this.root = this.rotationRL(this.root); } } }
大伙儿儿依次测试一下这五种请况。按照上边示意图中树的形态加在节点,或者按照前序遍历的辦法 打印节点的key。
LL旋转的结果:
let tree = new AVLTree(); tree.insert(11); tree.insert(7); tree.insert(15); tree.insert(5); tree.insert(9); tree.insert(3); tree.preOrderTraverse((value) => console.log(value));
LR旋转的结果:
let tree = new AVLTree(); tree.insert(11); tree.insert(7); tree.insert(15); tree.insert(5); tree.insert(9); tree.insert(8); tree.preOrderTraverse((value) => console.log(value));
RR旋转的结果:
let tree = new AVLTree(); tree.insert(11); tree.insert(7); tree.insert(15); tree.insert(13); tree.insert(20); tree.insert(25); tree.preOrderTraverse((value) => console.log(value));
RL旋转的结果:
let tree = new AVLTree(); tree.insert(11); tree.insert(7); tree.insert(15); tree.insert(13); tree.insert(20); tree.insert(14); tree.preOrderTraverse((value) => console.log(value));
大伙儿儿用同样的辦法 修改remove()辦法 ,或者测试下面五种请况下的节点删除:
let tree = new AVLTree(); tree.insert(11); tree.insert(7); tree.insert(15); tree.insert(5); tree.insert(9); tree.remove(15); tree.preOrderTraverse((value) => console.log(value));
let tree = new AVLTree(); tree.insert(11); tree.insert(7); tree.insert(15); tree.insert(13); tree.insert(20); tree.remove(7); tree.preOrderTraverse((value) => console.log(value));
完整的自平衡二叉搜索树AVLTree类的代码如下:
尽管自平衡二叉搜索树AVL可需要很有效地帮助大伙儿儿解决某些树节点的操作疑问,或者在插入和移除节点时其性能并都会最好的。更好的取舍是红黑树,红黑树也是五种自平衡二叉搜索树,或者它对其中的节点做了好多好多 特殊的规定,使得在操作树节点的性能上要优于AVL。
下一章大伙儿儿将介绍怎么都可以 用JavaScript来实现图这些 非线性数据形态。