AVL树问题

来源:1-2 计算节点的高度和平衡因子

404_

2023-12-27 23:50:02

我看了老师的代码,里面有K 和 V。因为我是看了二分查找树后直接看的AVL。那么我在构造一颗AVL树的时候,是不是可以不加 <K extends Comparable, V> ,不加public K key; 不加 public V value; 这些内容呢?只构建一颗朴素的平衡二叉树 或者 判断一个二叉树是否平衡,要K和V没什么用吧?

public class AVLTree<K extends Comparable<K>, V> {

    private class Node{
        public K key;
        public V value;
        public Node left, right;
        public int height;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            height = 1;
        }
    }

写回答

1回答

liuyubobobo

2023-12-28

基于 AVL 可以创建一个 map,也可以创建一个 set。引入 K 和 V 可以创建一个 map,没有 K 和 V 只能创建一个 set。如果你需要的是一个 set,可以不加入 K 和 V。


另外,set 可以基于 map 实现,而 map 不能基于 set 实现。所以从实现一个数据结构库的角度,应该从底层实现一个支持 map 的 AVL,然后复用这个 AVL 实现 set。可以参考这里 https://class.imooc.com/course/1584 第二章的内容。


继续加油!:)


0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2636 学习 · 1090 问题

查看课程