自己动手实现java数据结构（六）二叉搜索树

二叉搜索树ADT接口:

 1 /**
 2  * Map ADT接口
 3  */
 4 {
 5      6      * 存入键值对
 7      *  key   key值
 8  value value
 9  被覆盖的的value值
10      11     V put(K key,V value);
12 
13     14      * 移除键值对
15 16  被删除的value的值
17      18     V remove(K key);
19 
20     21      * 获取key对应的value值
22 23       对应的value值
24      25     V get(K key);
26 
27     28      * 是否包含当前key值
29 30       true：包含 false：不包含
31      32      containsKey(K key);
33 
34     35      * 是否包含当前value值
36  value   value值
37         true：包含 false：不包含
38      39      containsValue(V value);
40 
41     42      * 获得当前map存储的键值对数量
43  键值对数量
44      * 45      size();
46 
47     48      * 当前map是否为空
49   true：为空 false：不为空
50      51      isEmpty();
52 
53     54      * 清空当前map
55      56      clear();
57 
58     59      * 获得迭代器
60  迭代器对象
61      62     Iterator<EntryNode<K,1)"> iterator();
63 
64     65      * entry 键值对节点接口
66 67     68         69          * 获得key值
70          * 71         K getKey();
72 
73         74          * 获得value值
75 76         V getValue();
77 
78         79          * 设置value值
80 81          setValue(V value);
82     }
83 }

二叉搜索树实现:

 * 二叉搜索树实现
  comparator;
    }

    
        CURRENT;
    }

    
        K key;

        
        V value;

         value;
        }
    }

    
                    同时存在左右孩子的节点删除时会和直接后继(nextNode)进行交换
                    因此nextNode指向当前节点
                 ;
        }
    }

     relativePosition;
        }
    }

    @Override
    ;
        }
    }

    @Override
                deleteEntryNode(targetEntryNode.target);

             targetEntryNode.target.value;
        }
    }

    @Override
     Itr();
    }

    @Override
    );
            }
        }
    }

     target.parent;
        RelativePosition relativePosition = target.left : target.right);
        
             RelativePosition.LEFT){
                parent.left = {
                parent.right = ;
            }

            target.parent = :::只有左孩子或者右孩子
            replacement.parent = target.parent;

            :::被删除节点的双亲节点指向被代替的节点
             RelativePosition.LEFT){
                parent.left ={
                parent.right = replacement;
            }
        }
    }

    :::不是左孩子，是右孩子，继续向上寻找
                child = parent;
        }
    }

    ;
        }

        EntryNode<K,1)"> entryNode.left;
        }

         entryNode;
    }
}

　　我们已经实现了一个二叉搜索树，遗憾的是，实现的并不是更强大的平衡二叉搜索树。

　　平衡二叉搜索树的实现远比普通二叉搜索树复杂，难理解。但凡事不能一蹴而就，要想理解更复杂的平衡二叉搜索树，理解普通的、非平衡的二叉搜索树是基础的一步。希望大家能更好的理解二叉搜索树，更好的理解自己所使用的数据结构，写出更高效，易维护的程序。

　　本系列博客的代码在我的 github上：https://github.com/1399852153/DataStructures?，存在许多不足之处，请多多指教。

（编辑：常州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!