概述

二叉搜索樹，它具有以下的特性，樹節(jié)點(diǎn)具有一個(gè)key屬性，不同節(jié)點(diǎn)之間key是不能重復(fù)的，對(duì)于任意一個(gè)節(jié)點(diǎn)，它的key都要比左子樹的key大，比右子樹的key小

實(shí)現(xiàn)

創(chuàng)建節(jié)點(diǎn)

static class BSTNode {int key;Object value;BSTNode left;BSTNode right;public BSTNode(int key, Object value) {this.key = key;this.value = value;}public BSTNode(int key, Object value, BSTNode left, BSTNode right) {this.key = key;this.value = value;this.left = left;this.right = right;}}

查找節(jié)點(diǎn)

利用二叉樹的性質(zhì)

public Object get(int key) {BSTNode node = root;while (node != null) {if (node.key < key) {node = node.right;} else if (node.key > key) {node = node.left;} else {return node.value;}}return null;}

增加節(jié)點(diǎn)

同樣利用二叉樹的性質(zhì)，但是需要記錄要增加的節(jié)點(diǎn)的父節(jié)點(diǎn)

public void put(int key, Object value) {BSTNode node = root;BSTNode parent = null;while (node != null) {parent = node;if (key < node.key) {node = node.left;} else if (key > node.key) {node = node.right;} else {//直接修改node.value = value;return;}}if (parent == null) {root = new BSTNode(key, value);} else if (key > parent.key) {parent.right = new BSTNode(key, value);} else {parent.left = new BSTNode(key, value);}}

查找后驅(qū)值

在后面的AVL，以及紅黑樹中刪除節(jié)點(diǎn)是，我們經(jīng)常會(huì)需要求一個(gè)節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)

分類討論，分成兩種情況
若節(jié)點(diǎn)有右子樹，那么右子樹的最小值就是前驅(qū)
若沒有右子樹，則去尋找是否存在從右而來的祖先節(jié)點(diǎn)，最近的這個(gè)祖先節(jié)點(diǎn)就是后驅(qū)
兩種情況都不滿足，則該節(jié)點(diǎn)沒有后驅(qū)

public Object predecessor(int key) {BSTNode ancestorFromRight = null;BSTNode node = root;while (node != null) {if (key < node.key) {ancestorFromRight = node;node = node.left;} else if (key > node.key) {node = node.right;} else {break;}}//沒有該節(jié)點(diǎn)if (node == null) {return null;}if (node.right != null) {return min(node.right);}return ancestorFromRight == null ? null : ancestorFromRight.value;}public Object min(BSTNode node) {if (node == null) {return null;}while (node.left != null) {node = node.left;}return node.value;}

根據(jù)關(guān)鍵詞刪除

根據(jù)關(guān)鍵字刪除
刪除有一下幾種情況
第一種：刪除節(jié)點(diǎn)沒有右孩子，將左孩子掛過去
第二種：刪除節(jié)點(diǎn)沒有左孩子，將右孩子掛過去
第三種：都沒有，掛過去null
第四種：左右孩子都有，可以將后繼節(jié)點(diǎn)掛在parent后面，后繼節(jié)點(diǎn)為s，后繼節(jié)點(diǎn)的父親為sp
??1.將如果sp就是要?jiǎng)h除的節(jié)點(diǎn)
??2.sp不是刪除節(jié)點(diǎn)，需要將s的后代給sp

public Object delete(int key) {BSTNode node = root;BSTNode parent = null;while (node != null) {if (key < node.key) {parent = node;node = node.left;} else if (key > node.key) {parent = node;node = node.right;} else {break;}}if (node == null) {return null;}if (node.left == null) {//情況1shift(parent, node, node.right);//情況2} else if (node.right == null) {shift(parent, node, node.left);} else {BSTNode s = node.right;BSTNode sParent = node;while (s.left != null) {sParent = s;s = s.left;}if (sParent != node) {//將后驅(qū)節(jié)點(diǎn)的孩子掛在后驅(qū)節(jié)點(diǎn)父親的后面shift(sParent, s, s.right);s.right = node.right;}//后驅(qū)節(jié)點(diǎn)一定沒有左孩子，所以可以直接的掛靠shift(parent, node, s);s.left = node.left;}return node.value;}/** 托孤方法** */private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {if (parent == null) {root = child;} else if (deleted == parent.left) {parent.left = child;} else {parent.right = child;}}

找到樹中所有小于key的節(jié)點(diǎn)的value

我們可以通過一個(gè)中序遍歷實(shí)現(xiàn)，對(duì)于一個(gè)二叉搜索樹來說，中序遍歷的結(jié)果，恰好是從小到大排序的

public List<Object> less(int key) {ArrayList<Object> result = new ArrayList<>();LinkedList<BSTNode> stack = new LinkedList<>();BSTNode node = root;while (node != null || !stack.isEmpty()) {if (node != null) {stack.push(node);node = node.left;} else {BSTNode min = stack.pop();if (min.key < key) {result.add(min.value);} else {break;}node = min.right;}}return result;}