介绍
二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树或排序二叉树，是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
通常采取二叉链表作为二叉查找树的存储结构。
复杂度
| 算法 | 平均 | 最差 |
|---|---|---|
| 空间 | O(n) | O(n) |
| 搜索 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
查找步骤
在二叉搜索树b中查找x的过程为：
- 若b是空树，则搜索失败，否则：
- 若x等于b的根节点的数据域之值，则查找成功；否则：
- 若x小于b的根节点的数据域之值，则搜索左子树；否则：
- 查找右子树。
插入步骤
向一个二叉搜索树b中插入一个节点s的算法，过程为：
- 若b是空树，则将s所指节点作为根节点插入，否则：
- 若s->data等于b的根节点的数据域之值，则返回，否则：
- 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
- 把s所指节点插入到右子树中。（新插入节点总是叶子节点）
删除步骤
从 BST 中删除节点比插入节点难度更大。因为删除一个非叶子节点，就必须选择其他节点来填补因删除节点所造成的树的断裂。如果不选择节点来填补这个断裂，那么就违背了 BST 的性质要求。
删除节点算法的第一步是定位要被删除的节点，这可以使用前面介绍的查找算法，因此运行时间为 O(log2n)。接着应该选择合适的节点来代替删除节点的位置，它共有三种情况需要考虑。
情况 1：若被删除结点为叶子结点，即该节点的左子树和右子树均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
情况 2：若被删除结点只有左子树或右子树，此时只要令左子树或右子树直接成为其双亲结点的左子树或右子树即可，作此修改也不破坏二叉查找树的特性。
情况 3：若被删除结点的左子树和右子树均不空，如果被删除节点的右孩子没有左孩子，那么这个右孩子被用来替换被删除节点。因为被删除节点的右孩子都大于被删除节点左子树的所有节点，同时也大于或小于被删除节点的父节点，这同样取决于被删除节点是左孩子还是右孩子。因此，用右孩子来替换被删除节点，符合二叉查找树的性质。如果被删除节点的右孩子有左孩子，就需要用被删除节点右孩子的左子树中的最下面的节点来替换它，就是说，我们用被删除节点的右子树中最小值的节点来替换。
遍历步骤
先序遍历，中序遍历，后序遍历
python
class BinarySearchTree(object):
def __init__(self, data, left=None, right=None, parent=None):
self.data = data
self.left = left
self.right = right
self.parent = parent
class BST(object):
def __init__(self):
self.root = None
self.size = 0
def lenght(self):
return self.size
def find(self, key):
if self.root:
result = self._find(key, self.root)
if result:
return result
else:
return None
else:
None
def _find(self, key, node):
if not node:
return None
elif node.data == key:
return node
elif key < node.data:
return self._find(key, node.left)
else:
return self._find(key, node.right)
def insert(self, key):
node = BinarySearchTree(key)
if not self.root:
self.root = node
self.size += 1
else:
currentNode = self.root
while True:
if key < currentNode.data:
if currentNode.left:
currentNode = currentNode.left
else:
currentNode.left = node
node.parent = currentNode
self.size += 1
break
elif key > currentNode.data:
if currentNode.right:
currentNode = currentNode.right
else:
currentNode.right = node
node.parent = currentNode
self.size += 1
break
else:
break
def findMin(self):
if self.root:
return self._findMin(self.root)
else:
return None
def findMax(self):
if self.root:
currentNode = self.root
while currentNode.right:
currentNode = currentNode.right
return currentNode
else:
return None
def _findMin(self, node):
if node:
currentNode = node
while currentNode.left:
currentNode = currentNode.left
return currentNode
def delete(self, key):
if self.size > 1:
nodeToDelete = self.find(key)
if nodeToDelete:
self._delete(nodeToDelete)
self.size -= 1
else:
raise KeyError('Error, key not in tree')
elif self.size == 1 and self.root.data == key:
self.root = BinarySearchTree(None)
self.size = 0
else:
raise KeyError('Error, key not in tree')
def _delete(self, node):
if not node.left and node.right: #node为树叶
if node == node.parent.left: #node为父节点的左子树
node.parent.left = None
else:
node.parent.right = None
elif node.right and node.left: #node有两个儿子
minNone = self._findMin(node.right)
node.data = minNone.data
self._delete(minNone)
else: #node有一个儿子
if node.left: #node有左儿子
if node.parent and node.parent.left == node: #node为父节点的左子树
node.left.parent = node.parent
node.parent.left = node.left
elif node.parent and node.parent.right == node: #node为父节点的右子树
node.left.parent = node.parent
node.parent.right = node.left
else: # node为根
self.root = node.left
node.left.parent = None
node.left = None
else:
if node.parent and node.parent.left == node:
node.right.parent = node.parent
node.parent.left = node.right
elif node.parent and node.parent.right == node:
node.right.parent = node.parent
node.parent.right = node.right
else:
self.root = node.right
node.right.parent = None
node.right = None
def printTree(self):
if self.size == 0:
print("Empty Tree")
else:
self._printTree(self.root)
def _printTree(self, node):
if node: #中序遍历
self._printTree(node.left)
print(node.data)
self._printTree(node.right)
网友评论