数据结构与算法-树（Tree）-JS

数组优点：

1.根据下表中访问效率很高；

2.倘若希望根据元素查找对应的位置，比较好的方式是先对数组进行排序，在进行二分查找

数组缺点：

1.需要先对数组进行排序，生成有序数组，才能提高查找效率；

2.另外数组在插入和删除数据时，需要有大量的位移操作，效率很低

链表优点：

插入和删除操作效率都很高

链表缺点：

1.查找效率很低，需要从头开始依次访问查找；

2.而且即使插入和删除效率很高，但是如果插入和删除中间位置的数据，还是需要从头先找到对应的数据

哈希表优点：

插入、查询、删除效率都是非常高的

哈希表缺点：

1.空间利用率不高，需要设置总长度二倍的空间，底层使用的是数据，并且某些单元没有被利用；

2.哈希表中的元素时无序的，不能按照固定的顺序来遍历哈希表中的元素；

3.不嫩快速找出哈希表中的最大者或者最小者这些特殊值。

树优点：

不能说明树结构比其他结构都要好，因为每种数据结构都有自己特定的应用场景。

1.空间利用率是非常高的；

2.相对于哈希表来说，利用率高，而且所有元素都是有序的，可以按照某些顺序进行遍历的，可以非常快速地查找到最大值、最小值;

3.某些场景，使用树结构跟家方便，因为树结构是非线性的，可以表示一对多的关系

树缺点：

查找某个值的效率比列表要快，但比哈希表慢；

树的术语：

节点的度（Degree）：节点的子树个数；

树的度：树的所有节点中最大的度数；

叶节点/叶子节点（Leaf）：度为0的节点；

父节点（Parent）；子节点（Child）；

兄弟节点（Sibling）:具有同一个父节点的各节点彼此是兄弟节点；

路径和路径长度：一个节点到另一个节点的路径，路径长度取决于路径中的边的个数；

节点的层次（Level）：规定根节点在1层，其他节点的层数依次加一；树的深度（Depth）：树中所有节点中的最大层次是这棵树的深度。

其实所有的树本质上都可以使用二叉树模拟出来

二叉树有五种形态：

空（没有任何节点）；只有根节点；根节点和左子节点；根节点和右节点、根节点和左右子节点

二叉树的特性：

1.一个二叉树第i层的最大节点数为2^(i-1)，i>=1;

2.深度为k的二叉树的节点总数的最大值为:2^k-1,k>=1;

3.对任何非空二叉树T，若n0表示叶节点的个数，n2表示度为2的非叶节点个数，那么二者关系为n0=n2+1.

满二叉树（完美二叉树Perfect Binary Tree）：

除了最下层的叶节点外，每层节点都有两个子节点；且刚好完全铺满

完全二叉树（Complete Binary Tree）：

除了最后一层外，其他各层都达到了最大个数，且最后一层从左向右的叶节点连续存在，不能跳着有节点，完美二叉树是特殊的完全二叉树

完全二叉树才可以使用数组进行存储，如果是一般的二叉树，使用数组存储的话会浪费空间；

二叉树最常见的方式是使用链表存储

二叉搜索树（BST，Binary Search Tree），也叫二叉排序树或二叉查找树

二叉搜索树是一颗二叉树，可以为空；

如果不为空，满足以下性质：

1.非空左子树的所有键值小于其根节点的键值；

2.非空右子树的所有键值大于其根节点的键值；

3.左、右子树本身也都是二叉搜索树。

二叉搜索树的特点：

相对较小的值总是保存在左节点上，相对较大的值总是保存在右节点上，这个特点可以使查找效率非常高，这也是二叉搜索树中搜索的来源。

//封装二叉搜索树
function BinarySearchTree() {
    //内部类节点
    function Node(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    //属性
    this.root = null;
    //方法
    //插入数据：对外给用户调用的方法
    BinarySearchTree.prototype.insert = function (key) {
        //根据key创建节点
        var newNode = new Node(key);
        //判断根节点是否有值
        if (this.root == null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        } 
    }
    //内部使用的插入方法，用于比较两个节点值的大小
    BinarySearchTree.prototype.insertNode = function (node, newNode) {
        if (newNode.key < node.key) { //向左查找
            if (node.left == null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else { //向右查找
            if (node.right == null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }
    //二叉树的遍历常见有三种方式：先序遍历、中序遍历、后序遍历，还有层序遍历，从第一层开始一层一层从左到右进行遍历，这个使用较少，可以使用队列来完成。
    //先序遍历：1.访问根节点2.先序遍历其左子树3.先序遍历其右子树
    BinarySearchTree.prototype.preOrderTraversal = function (handler) {
        this.preOrderTraversalNode(this.root, handler);
    }
    //如果理解费劲可以画个二叉树的图
    BinarySearchTree.prototype.preOrderTraversalNode = function (node, handler) {
        if (node != null) {
            //处理经过的节点
            //这也是叫先序的原因，是先对node进行处理，处理完之后再去找其他节点
            //先序还可以理解为啥时候处理根节点，在最最前面处理根节点叫做先序
            handler(node.key);
            //查找经过节点的左子节点
            this.preOrderTraversalNode(node.left, handler);
            //查找经过节点的右子节点
            this.preOrderTraversalNode(node.right, handler);
        }
    }
    //中序遍历：1.中序遍历其左子树2.访问根节点3.中序遍历其右子树
    BinarySearchTree.prototype.midOrderTraversal = function (handler) {
        this.midOrderTraversalNode(this.root, handler);
    }
    BinarySearchTree.prototype.midOrderTraversalNode = function (node, handler) {
        if (node != null) {
            //查找左子树中的节点，最开始递归后找到左子树最左边那个节点
            this.midOrderTraversalNode(node.left, handler);
            //处理节点
            handler(node.key);
            //查找右子树中的节点
            this.midOrderTraversalNode(node.right, handler);
        }
    }
    //后序遍历：1.后序遍历其左子树2.后序遍历其右子树3.访问根节点
    BinarySearchTree.prototype.postOrderTraversal = function (handler) {
        this.postOrderTraversalNode(this.root, handler);
    }
    BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {
        if (node != null) {
            //查找左子树中的节点
            this.postOrderTraversalNode(node.left, handler) ;
            //查找右子树中的节点
            this.postOrderTraversalNode(node.right, handler);
            //处理节点
            handler(node.key);
        }
    }
    //寻找最值
    //寻找最大值
    BinarySearchTree.prototype.max = function () {
        //获取根节点
        var node = this.root;
        //一次向右不断地查找，直到节点为null
        while (node.right != null) {
            node = node.right;
        }
        return node.key;
    }
    //寻找最小值
    BinarySearchTree.prototype.min = function () {
        //获取根节点
        var node = this.root;
        //一次向右不断地查找，直到节点为null
        while (node.left != null) {
            node = node.left;
        }
        return node.key;
    }
    //搜索特定值，搜索到了返回true
    // //采用递归算法
    // BinarySearchTree.prototype.search = function (key) {
    //     return this.searchNode(this.root, key);
    // }
    // BinarySearchTree.prototype.searchNode = function (node, key) {
    //     //如果传入的node为null，那么就退出递归
    //     if (node == null) {
    //         return false;
    //     }
    //     //判断node节点的值和传入的key大小
    //     if (key < node.key) {
    //         return this.searchNode(node.left, key);
    //     } else if (key > node.key) {
    //         return this.searchNode(node.right, key);
    //     } else {
    //         return true;
    //     }
    // }
    //使用循环实现
    BinarySearchTree.prototype.search = function (key) {
        //获取根节点
        var node = this.root;
        //循环key
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                return true;
            }
        }
        return false;
    }
    //二叉搜索树的节点的删除
    //1.先找到要删除的节点，如果没有找到，不需要删除2.找到要删除的节点，分三种情况讨论
    //1删除叶子节点2删除只有一个子节点的节点3删除有两个子节点的节点
    //删除节点
    BinarySearchTree.prototype.remove = function (key) {
        //寻找要删除的节点
        var current = this.root;
        var parent = null;
        var isLeftChild = true; //是否是左节点
        //开始寻找删除的节点
        while (current.key != key) {
            parent = current;
            if (key < current.key) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            //已经找到最后的节点，依然没有找到等于key的节点
            if (current == null) return false;
        }
        //根据对应的情况删除节点
        //删除的节点时叶子节点（没有子节点）
        if (current.left == null && current.right == null) {
            if (current == this.root) { //根节点且为叶子节点
                this.root = null;
            } else if (isLeftChild) { //不是根节点且是左子节点
                parent.left = null;
            } else { //不是根节点且是右子节点
                parent.right = null;
            }
        //删除的节点有一个子节点，只删除这一个节点，下面的节点还保留，需要考虑六种情况，其中两个是根节点的情况
        //比较难理解，需要画图理解
        } else if (current.right == null) { //删除的节点只有左子节点
            if (current == this.root) {
                this.root = current.left;
            } else if (isLeftChild) { //删除的节点时父节点左子节点
                parent.left = current.left;
            } else { //删除的节点时父节点右子节点
                parent.right = current.left;
            }
        } else if (current.left == null) { //删除的节点只有右子节点
            if (current == this.root) {
                this.root = current.right;
            } else if (isLeftChild) { //删除的节点时父节点右子节点
                parent.left = current.right;
            } else { //删除的节点时父节点右子节点
                parent.right = current.right;
            }
        //删除的节点有两个子节点
        } else {
            //比较难理解，需要画图理解
            //如果我们要删除的节点有两个子节点，甚至子节点还有子节点，我们需要从下面的子节点中找到一个节点来替换当前的节点
            //这个节点的特征就是current节点下面所有的节点中最接近current的节点
            //比current小一点点的节点，一定是current左子树的最大值；臂current大一点点的节点，一定是current右子树的最小值
            //前驱和后继
            //比current小一点点的节点，称为current节点的前驱；比current大一点点的节点，称为current节点的后继
            //在这里实现找后继
            //获取后继节点
            var successor = this.getSuccssor(current);
            //判断是否为根节点
            if (current == this.root) {
                this.root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            //将删除节点的左子树 = current.left
            successor.left = current.left;
        }
    }
    BinarySearchTree.prototype.getSuccssor = function (delNode) {
        //定义变量，保存找到的后继
        var successor = delNode;
        var current = delNode.right;
        var successorParent = null;
        //循环查找
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }
        //判断寻找的后继节点是否直接就是delNode的right节点
        if (successor != delNode.right) {
            successorParent.left = successor.right;
            successor.right = delNode.right;
        }
        return successor;
    }
}


//测试代码
//创建BinarySearchTree
var bst = new BinarySearchTree();
//插入数据
bst.insert(11);       
bst.insert(7);       
bst.insert(15);       
bst.insert(5);       
bst.insert(3);     
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(6);
//测试先序遍历
var resultString = '';
bst.preOrderTraversal(function (key) {
    resultString += key + " ";
})
// alert(resultString); //11 7 5 3 6 9 8 10 15 13 12 14 20 18 25 
//测试中序遍历
resultString = '';
bst.midOrderTraversal(function (key) {
    resultString += key + " ";
})
// alert(resultString); //3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
//测试后序遍历
resultString = '';
bst.postOrderTraversal(function (key) {
    resultString += key + " ";
})
// alert(resultString); //3 6 5 8 10 9 7 12 14 13 18 25 20 15 11 
// //测试最值
// alert(bst.max());
// alert(bst.min());
// //测试搜索方法
// alert(bst.search(25));
// alert(bst.search(2));
//测试删除代码
bst.remove(9);
bst.remove(7);
bst.remove(15);
resultString = '';
bst.postOrderTraversal(function (key) {
    resultString += key + " ";
})
alert(resultString); //3 6 5 10 8 12 14 13 25 20 18 11 

非平衡树：

比较好的二叉搜索树数据应该是左右均匀分布的，如果插入的数据是有序的数据，分布不均匀，就叫做非平衡树。

平衡二叉树的插入或查找的效率是O(logN)，和深度有关系；非平衡二叉树，相当于编写了一个链表，查找效率变成了O(N)

所以需要保证树总是平衡的，即每个节点左边的子孙节点个数尽可能等于右边的子孙节点的个数

常见的平衡树有AVL树和红黑树

AVL树是最早的一种平衡树，使用每个节点多存储一个额外的数据的方法保持树的平衡，时间复杂度为为O(logN)，但是每次插入或删除操作的效率相对于红黑树来说不高，所以整体效率不如红黑树

红黑树的时间复杂度也是O(logN)，现在平衡树的应用基本都是红黑树

红黑树的规则：

1.节点时红色或黑色

2.根节点是黑色

3.每个叶子节点都是黑色的空节点（NIL节点）

4.每个红色节点的两个子节点都是黑色（从每个叶子节点到根节点的所有路径上不能有两个连续的红色节点）

5.从任一节点到其每个叶子的所有路径都包含相同数据的黑色节点

前面的约束确保了红黑树的关键特性：从根到叶子的最长可能路径，不会超过最短可能路径的两倍长，结果就是这个树基本是平衡的，虽然没有做到绝对的平衡，但是可以保证在最坏的情况下，依然是高效的。

为什么可以做到最长路径不超过最短路径的二倍？性质4决定了路径不能有两个相连的红色节点，最短的可能路径都是黑色的节点，最长的可能路径是红色和黑色交替，性质5所有路径都有相同数目的黑色节点，这就表明了最长的路径只能是红黑一直相互交替，表明了没有路径能多于任何其他路径的两倍长。

插入一个新节点时，有可能树不再平衡，可以通过三种方式的变换，让树保持平衡：换色；左旋转；有旋转

变色：

为了重新复核红黑树的规则，尝试吧红色节点变为黑色，或者把黑色节点变为红色。

首先，需要知道插入的新节点通常都是红色节点，因为在插入节点为红色的时候，有可能插入一次是不违反红黑树任何规则的，而插入黑色节点，必然会导致一条路径上多了黑色节点，这是很难调整的，插入红色节点可能导致红红相连的情况，但是这种情况可以通过颜色调换和旋转来调整。

左旋转：

逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子；右旋转：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。

插入一个新节点会有五种情况：设要插入的节点为N，其父节点为P，其祖父节点为G，其父亲的兄弟节点为U。

情况一：新节点N位于树的根上，没有父节点，这种情况下，直接将红色编程黑色即可，这样满足性质2。

情况二：新节点的父节点P是黑色，性质4没有失效，性质5也没有问题，尽管新节点N有两个黑色的叶子结点NIL，但是新节点N是红色的，所以通过它的路径中黑色节点的个数依然相同，满足性质5。

情况三：P为红色，U为红色，G为黑色，将P和U变换为黑色，并且将G变换为红色，每条路径上的黑色节点的数目没有改变。可能出现的问题：N的祖父节点G的父节点也可能是红色，这就违反了性质3，可以递归地调整颜色，但是如果递归调整颜色到了根节点，就需要进行旋转了，下面会有例子讲到。

情况四：P红U黑G黑，N为左儿子，方案，P黑，G红，GP进行右旋转，也可以将旋转与变色的顺序互换。

情况五：P红U黑G黑，N是右儿子，方案，PN进行左旋转，形成情况四的结果，最祖父节点G进行一次右旋转，并且改变颜色即可。

案例：依次插入10 9 8 7 6 5 4 3 2 1

插入10（将节点10的颜色变为黑色）=>插入9（不需要用任何变换）=>插入8（情况四，父变黑，祖变红，父和祖有旋转）=>插入7（符合情况三，父变黑，叔变黑，祖变红，不满足性质2，只需要把根节点变为黑色就可以了）=>插入6（情况四，父变黑，祖变红，父和祖进行右旋转）=>插入5（情况三，父和叔变黑，祖变红）=>插入4（情况四，父变黑，祖变红，父和祖进行右旋转）=>插入3（情况三，父变黑，叔变黑，祖变红，此时5和7是挨着的红色，是情况四，7变黑，9变红，7和9进行右旋转）=>插入2（情况四，父3变黑，祖4变红，父3祖4进行右旋转）=>插入1（情况三，父2变黑，叔4变黑，祖3变红，此时3和5是挨着的红色，把3以下看做新插入的红色节点，父5变黑，叔9变黑，祖7变红，根节点不满足性质2，将根节点7变黑）

红黑树的删除，需要将二叉搜索树的删除操作和红黑树的插入规则结合起来，难度非常大，需要考虑删除中间节点的话会不会对后序的子节点产生影响，而且一旦删除后会不会对红黑树的整个规则产生影响。

红黑树的插入和删除的代码，需要按照之前分析的不同情况进行分析。前端就先了解到这里，如果需要学习和了解其他后端语言以及其源码，比如Java、Python、Go等，可以再深入了解代码实现。