JavaScript数据结构——树的实现

时间:2019-11-26 23:44:10
浏览: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来模拟树的节点吗？）下面是前序遍历的执行结果：

　　让让我们让让我们参照前序遍历的定义，借住下面的示意图来理解整个遍历过程：

　　在前序遍历函数preOrderTraverseNode()中，先执行callback(node.element)，日后再依次递归左子树和右子树。让让我们让让我们将树的根节点作为第一另五个节点传入，首先打印的就说根节点11，日后结束了了英语遍历左子树，这将依次打印左子树中的所有左子节点，依次是7、5、3。当节点3的prev为null时，递归返回，继续查找节点3的右子节点，此时段点3的next值也为null，于是继续向上返回到节点5，结束了了英语遍历节点5的右子节点，于是打印节点6......最终所有的节点就按照你什儿递归顺序进行遍历。

　　日后让让我们让让我们再来看看中序遍历的情况报告。

tree.inOrderTraverse((value) => console.log(value));

　　在中序遍历函数inOrderTraverseNode()中，先递归左子树，日后执行callback(node.element)，最后再递归右子树。同样的，让让我们让让我们将根节点作为第一另五个节点传入，递归到左子树的最后一另五个左子节点3，由于节点3的prev为null，所以递归返回，打印节点3，日后继续查找节点3的右子节点，节点3的next值也为null，递归返回到上一层节点5，结束了了英语打印节点5，日后再查找节点5的右子节点......最终整棵树按照你什儿顺序完成遍历。

　　最后再来看看到序遍历的情况报告。

tree.postOrderTraverse((value) => console.log(value));

　　在后序遍历函数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) {
 400         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;
 400     }
 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;
 400 };
 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         // 第二种情况报告：只涵盖一另五个

子节点
 400         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;
400     }
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 
1400     // 返回树中的最小节点
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 }

BinarySearchTree

自平衡树

　　上方的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来实现图你什儿非线性数据内外部。

上一篇
【方正圆明MT100 2200报价】怎么样
下一篇
【沁河之魂】美丽乡村——沁河庄