构建二叉树进行数值数组的去重及优化

sarva 发布于2019-08-26 11:45 / 437人阅读

摘要：构建二叉树进行数值数组的去重及优化常见两层循环实现数组去重构建二叉树实现去重仅适用于数值类型的数组将先前遍历过的元素，构建成二叉树，树中每个结点都满足左子结点的值当前结点的值右子结点的值这样优化了判断元素是否之前出现过的过程若元素比当前结点

构建二叉树进行数值数组的去重及优化 常见两层循环实现数组去重

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
let newArr = []
for (let i = 0; i < arr.length; i++) {
    let unique = true
    for (let j = 0; j < newArr.length; j++) {
        if (newArr[j] === arr[i]) {
            unique = false
            break
        }
    }
    if (unique) {
        newArr.push(arr[i])
    }
}
console.log(newArr)

构建二叉树实现去重（仅适用于数值类型的数组）

将先前遍历过的元素，构建成二叉树，树中每个结点都满足：左子结点的值 < 当前结点的值 < 右子结点的值

这样优化了判断元素是否之前出现过的过程

若元素比当前结点大，只需要判断元素是否在结点的右子树中出现过即可

若元素比当前结点小，只需要判断元素是否在结点的左子树中出现过即可

let arr = [0, 1, 2, 2, 5, 7, 11, 7, 6, 4,5, 2, 2]
class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}
class BinaryTree {
    constructor() {
        this.root = null
        this.arr = []
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            this.root = node
            this.arr.push(value)
            return this.arr
        }
        let current = this.root
        while (true) {
            if (value > current.value) {
                if (current.right) {
                    current = current.right
                } else {
                    current.right = node
                    this.arr.push(value)
                    break
                }
            }
            if (value < current.value) {
                if (current.left) {
                    current = current.left
                } else {
                    current.left = node
                    this.arr.push(value)
                    break
                }
            }
            if (value === current.value) {
                break
            }
        }
        return this.arr
    }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
    binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路一，记录最大最小值

记录已经插入元素的最大最小值，若比最大元素大，或最小元素小，则直接插入

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}
class BinaryTree {
    constructor() {
        this.root = null
        this.arr = []
        this.max = null
        this.min = null
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            this.root = node
            this.arr.push(value)
            this.max = value
            this.min = value
            return this.arr
        }
        if (value > this.max) {
            this.arr.push(value)
            this.max = value
            this.findMax().right = node
            return this.arr
        }
        if (value < this.min) {
            this.arr.push(value)
            this.min = value
            this.findMin().left = node
            return this.arr
        }
        let current = this.root
        while (true) {
            if (value > current.value) {
                if (current.right) {
                    current = current.right
                } else {
                    current.right = node
                    this.arr.push(value)
                    break
                }
            }
            if (value < current.value) {
                if (current.left) {
                    current = current.left
                } else {
                    current.left = node
                    this.arr.push(value)
                    break
                }
            }
            if (value === current.value) {
                break
            }
        }
        return this.arr
    }

    findMax() {
        let current = this.root
        while (current.right) {
            current = current.right
        }
        return current
    }

    findMin() {
        let current = this.root
        while (current.left) {
            current = current.left
        }
        return current
    }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
    binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路二，构建红黑树

构建红黑树，平衡树的高度

有关红黑树的部分，请见红黑树的插入

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
console.log(Array.from(new Set(arr)))

class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
        this.parent = null
        this.color = "red"
    }
}

class RedBlackTree {
    constructor() {
        this.root = null
        this.arr = []
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            node.color = "black"
            this.root = node
            this.arr.push(value)
            return this
        }
        let cur = this.root
        let inserted = false
        while (true) {
            if (value > cur.value) {
                if (cur.right) {
                    cur = cur.right
                } else {
                    cur.right = node
                    this.arr.push(value)
                    node.parent = cur
                    inserted = true
                    break
                }
            }

            if (value < cur.value) {
                if (cur.left) {
                    cur = cur.left
                } else {
                    cur.left = node
                    this.arr.push(value)
                    node.parent = cur
                    inserted = true
                    break
                }
            }

            if (value === cur.value) {
                break
            }
        }
        // 调整树的结构
        if(inserted){
            this.fixTree(node)
        }
        return this
    }

    fixTree(node) {
        if (!node.parent) {
            node.color = "black"
            this.root = node
            return
        }
        if (node.parent.color === "black") {
            return
        }
        let son = node
        let father = node.parent
        let grandFather = father.parent
        let directionFtoG = father === grandFather.left ? "left" : "right"
        let uncle = grandFather[directionFtoG === "left" ? "right" : "left"]
        let directionStoF = son === father.left ? "left" : "right"
        if (!uncle || uncle.color === "black") {
            if (directionFtoG === directionStoF) {
                if (grandFather.parent) {
                    grandFather.parent[grandFather.parent.left === grandFather ? "left" : "right"] = father
                    father.parent = grandFather.parent
                } else {
                    this.root = father
                    father.parent = null
                }
                father.color = "black"
                grandFather.color = "red"

                father[father.left === son ? "right" : "left"] && (father[father.left === son ? "right" : "left"].parent = grandFather)
                grandFather[grandFather.left === father ? "left" : "right"] = father[father.left === son ? "right" : "left"]

                father[father.left === son ? "right" : "left"] = grandFather
                grandFather.parent = father
                return
            } else {
                grandFather[directionFtoG] = son
                son.parent = grandFather

                son[directionFtoG] && (son[directionFtoG].parent = father)
                father[directionStoF] = son[directionFtoG]

                father.parent = son
                son[directionFtoG] = father
                this.fixTree(father)
            }
        } else {
            father.color = "black"
            uncle.color = "black"
            grandFather.color = "red"
            this.fixTree(grandFather)
        }
    }
}

let redBlackTree = new RedBlackTree()
for (let i = 0; i < arr.length; i++) {
    redBlackTree.insert(arr[i])
}
console.log(redBlackTree.arr)

其他去重方法 通过 Set 对象去重

[...new Set(arr)]

通过 sort() + reduce() 方法去重

排序后比较相邻元素是否相同，若不同则添加至返回的数组中

值得注意的是，排序的时候，默认 compare(2, "2") 返回 0；而 reduce() 时，进行全等比较

let arr = [0, 1, 2, "2", 2, 5, 7, 11, 7, 5, 2, "2", 2]
let newArr = []
arr.sort((a, b) => {
    let res = a - b
    if (res !== 0) {
        return res
    } else {
        if (a === b) {
            return 0
        } else {
            if (typeof a === "number") {
                return -1
            } else {
                return 1
            }
        }
    }
}).reduce((pre, cur) => {
    if (pre !== cur) {
        newArr.push(cur)
        return cur
    }
    return pre
}, null)

通过 includes() + map() 方法去重

let arr = [0, 1, 2, "2", 2, 5, 7, 11, 7, 5, 2, "2", 2]
let newArr = []
arr.map(a => !newArr.includes(a) && newArr.push(a))

通过 includes() + reduce() 方法去重

let arr = [0, 1, 2, "2", 2, 5, 7, 11, 7, 5, 2, "2", 2]
let newArr = arr.reduce((pre, cur) => {
    !pre.includes(cur) && pre.push(cur)
    return pre
}, [])

通过对象的键值对 + JSON 对象方法去重

let arr = [0, 1, 2, "2", 2, 5, 7, 11, 7, 5, 2, "2", 2]
let obj = {}
arr.map(a => {
    if(!obj[JSON.stringify(a)]){
        obj[JSON.stringify(a)] = 1
    }
})

console.log(Object.keys(obj).map(a => JSON.parse(a)))

私有云服务器托管 java二叉树的构建二叉树 python二叉树平衡二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/107499.html

数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

wuyumin 2019-07-30 15:33 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

Carson 2019-08-26 11:32 评论0 收藏0
js数据结构-二叉树（二叉堆）

摘要：二叉树二叉树是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。二叉树二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。 showImg(https://segmentfault.com/img/bVbmEd...

ningwang 2019-08-23 14:29 评论0 收藏0
初级前端开发面试总结

摘要：前端面试总结先说背景，本人年月毕业，去年十月校招到今年月一直在做前端开发工作，年前打算换工作，就重新梳理下面试考点总结包含基础，基础，常见算法和数据结构，框架，计算机网络相关知识，可能有的点很细，有的点很大，参考个人情况进行总结，方便对知识前端面试总结先说背景，本人2018年7月毕业，去年十月校招到今年10月一直在做前端开发工作，年前打算换工作，就重新梳理下面试考点总结包含： ...

jifei 2019-08-30 15:54 评论0 收藏0
初级前端开发面试总结

摘要：前端面试总结先说背景，本人年月毕业，去年十月校招到今年月一直在做前端开发工作，年前打算换工作，就重新梳理下面试考点总结包含基础，基础，常见算法和数据结构，框架，计算机网络相关知识，可能有的点很细，有的点很大，参考个人情况进行总结，方便对知识前端面试总结先说背景，本人2018年7月毕业，去年十月校招到今年10月一直在做前端开发工作，年前打算换工作，就重新梳理下面试考点总结包含： ...

tigerZH 2019-08-23 14:07 评论0 收藏0