JS实现平衡二叉树
2020-12-25 07:27
标签：span 代码 ref mat 今天 高度 https htm blog 今天试着实现了一个平衡二叉树，平衡二叉树和二叉树其实只差平衡二字，但其实最难的便是这两步。导致不平衡的情况有很多，大家可以参考一下这篇博客。https://www.cnblogs.com/li-ningning/p/12358460.html 博客中博主把导致不平衡的结点分成了八类，但我们是否需要为8种情况设置8种调整方法呢？事实上是不需要的。通过观察我们可以发现所有调整方法都可以总结为两种情况： 写代码的时候有几个点必须要时刻注意，旋转是对于哪个结点来说的，同时如果旋转的结点是根节点还需要特别处理。在代码中使用了双指针，这样子节点和父节点就能实现互访。 同时左右旋转的时候还需要判断某些特殊结点是否存在，即代码中的grandsonNode，这些结点在左右旋转后的变化都是比较大的。 博主在写代码时候还发现一个问题，就是总觉得会有很多特殊的情况没有处理到，然后平衡处理逻辑越写越复杂。最后其实发现也不过就是上面两种方法的子集。这些情况也是上面博主引用那篇博客所述情况的子集。所以总结规律很重要，emmm，如果不擅长，那不如就记住吧，hhh。 有问题的话欢迎在评论区与博主讨论哦。 JS实现平衡二叉树 标签：span 代码 ref mat 今天 高度 https htm blog 原文地址：https://www.cnblogs.com/AwenJS/p/13934030.html 1 class TreeNode {
2 constructor(key) {
3 this.key = key;
4 this.leftChild = null;
5 this.rightChild = null;
6 this.parent = null;
7 }
8 rightRotate() {
9 const sonNode = this.leftChild;
10 const grandsonNode = sonNode.rightChild;
11 sonNode.rightChild = this;
12 sonNode.parent = null;
13 this.parent = sonNode;
14 this.leftChild = null;
15 if (grandsonNode) {
16 grandsonNode.parent = this;
17 }
18 this.leftChild = grandsonNode;
19 return sonNode;
20 }
21 leftRotate() {
22 const sonNode = this.rightChild;
23 const grandsonNode = sonNode.leftChild;
24 sonNode.leftChild = this;
25 sonNode.parent = null;
26 if (grandsonNode) {
27 grandsonNode.parent = this;
28 }
29 this.rightChild = grandsonNode;
30 return sonNode;
31 }
32 }
33
34 class AVLTree {
35 constructor(keys) {
36 this.root = new TreeNode(keys[0]);
37 const restKeys = keys.slice(1);
38 restKeys.forEach((value) => {
39 this.insertNode(new TreeNode(value), this.root);
40 });
41 }
42 insertNode(newNode, parent) {
43 if (newNode.key > parent.key) {
44 if (parent.rightChild === null) {
45 parent.rightChild = newNode;
46 newNode.parent = parent;
47 } else {
48 this.insertNode(newNode, parent.rightChild);
49 }
50 } else if (newNode.key parent.key) {
51 if (parent.leftChild === null) {
52 parent.leftChild = newNode;
53 newNode.parent = parent;
54 } else {
55 this.insertNode(newNode, parent.leftChild);
56 }
57 }
58 //当添加完一个节点后，如果右子树的高度-左子树的高度>1，左旋转
59 if (
60 this.getHeight(parent.rightChild) -
61 this.getHeight(parent.leftChild) >
62 1
63 ) {
64 //如果它的右子树的左子树大于它的右子树的右子树的高度
65 if (
66 this.getHeight(parent.rightChild.leftChild) >
67 this.getHeight(parent.rightChild.rightChild)
68 ) {
69 parent.rightChild = parent.rightChild.rightRotate();
70 }
71 //当前节点左旋转
72 if (parent.parent) {
73 parent.parent.rightChild = parent.leftRotate();
74 } else {
75 this.root = parent.leftRotate();
76 }
77 return;
78 }
79
80 //当添加完后，如果左子树的高度-右子树的高度>1,右旋转
81 if (
82 this.getHeight(parent.leftChild) -
83 this.getHeight(parent.rightChild) >
84 1
85 ) {
86 //如果它的左子树的右子树大于它的左子树的左子树的高度
87 if (
88 this.getHeight(parent.leftChild.rightChild) >
89 this.getHeight(parent.leftChild.leftChild)
90 ) {
91 //先对其当前节点的左节点进行左旋转
92 parent.leftChild = parent.leftChild.leftRotate();
93 }
94 //对当前节点进行右旋转
95 if (parent.parent) {
96 parent.parent.leftChild = parent.rightRotate();
97 } else {
98 this.root = parent.rightRotate();
99 }
100 }
101 }
102 getHeight(node) {
103 if (!node) {
104 return 0;
105 } else {
106 return (
107 Math.max(
108 node.leftChild === null ? 0 : this.getHeight(node.leftChild),
109 node.rightChild === null ? 0 : this.getHeight(node.rightChild)
110 ) + 1
111 );
112 }
113 }
114 }
115
116 //测试数据
117 // console.log(new AVLTree([1, 2, 3]));
118 // console.log(new AVLTree([1, 2, 3, 4]));
119 // console.log(new AVLTree([4, 3, 2, 1]));
120 // console.log(new AVLTree([3, 2, 4, 5, 1, 0]));
121 // console.log(new AVLTree([10, 11, 7, 6, 8, 9]));
122 // console.log(new AVLTree([2, 1, 5, 3, 6, 4]));
123 // console.log(new AVLTree([6, 2, 9, 1, 8, 12, 7, 11, 13, 10]));
124
125 // console.log(new AVLTree([3, 2, 1]));
126 // console.log(new AVLTree([1, 2, 3]));
127 // console.log(new AVLTree([5, 2, 6, 1, 4, 3]));
128 // console.log(new AVLTree([5, 2, 6, 1, 3, 4]));
129 // console.log(new AVLTree([4, 2, 3]));
130 // console.log(new AVLTree([2, 1, 5, 3, 6, 4]));
131 // console.log(new AVLTree([2, 1, 5, 4, 6, 3]));
132 // console.log(new AVLTree([2, 3, 4]));